互いに素 (整数論)
例えば、3 と 10 を共に割り切る正の整数は 1 だけなので、これらは互いに素である。逆に、3 と 6 は共に 3 で割り切れるので、これらは互いに素ではない。もう少し大きい数だと、729 と 1000 を共に割り切る正の整数は 1 だけなので、これらは互いに素である。逆に、729 と 1296 は 3、9、27、81 の四つで割り切れるので、この二つは互いに素ではない。同じく、1000 と 1296 も、2、4、8 の三つで割り切れるので、この二つも互いに素ではない。
互いに素であることの判定は素因数分解を用いて行うこともできるが、二つの整数のうち少なくとも一方が巨大である場合など一般には困難である。素因数分解によって公約数を調べる方法よりも、ユークリッドの互除法によって最大公約数を調べる方法のほうが遥に速い。
正の整数 n と互いに素となる(1 から n の間の)整数の個数は、オイラー関数 φ(n) によって与えられる。
三つの整数 a, b, c が互いに素であるとは、gcd(a, b, c) = 1 が成り立つことをいう。また、gcd(a, b)、gcd(b, c)、gcd(c, a) がすべて 1 に等しいとき、a, b, c は対ごとに素(英: pairwise coprime)またはどの二つも互いに素であるという。一般に、互いに素であるからといって対ごとに素であるとは限らない (例:a = 6, b = 15, c = 10)。一般の n 個の整数についても同様に定義される。