互いに素

互いに素（たがいにそ、英: coprime）は、二つの整数が 1 と -1 以外に共通の約数を持たない場合の二数の関係である。これは二つの整数の最大公約数が 1 であることと同値である。
例えば 35 と 12 は共通の素因数を持たず、それゆえ共通の 1 より大きい約数を持たないので互いに素である。42 と 18 はともに 6 を約数に持つので互いに素ではない。1 と -1 は（0や ±1 自身を含む）全ての整数と互いに素であり、0 は 1 および -1 とのみ互いに素である。一般に、相異なる素数どうしは互いに素であり、連続する2つの整数も互いに素である。2 以上の整数はその（自身を含む）倍数や 2 以上の約数と互いに素ではない。また三つ以上の整数の間でも互いに素の関係は同様に定義できる。例えば 25 と 18 と 15 は互いに素である。「25 と 15」や「18 と 15」は互いに素ではないが、三数に共通する正の約数が 1 のみであるならば、三数は互いに素という。 ある整数 a と b が互いに素であることを a  $\perp$  b と表すこともある。

二数が互いに素であるかどうかを知るために二数の最大公約数を調べる最良のアルゴリズムとしてユークリッドの互除法がある。これによって素因数分解によらずに最大公約数が求まり、それが 1 であれば互いに素、2 以上ならば互いに素ではないことが分かる。

互いに素である数の性質

整数a,bが互いに素であれば ax+by=1 を満たす整数x,yが存在する。またaとb₁が互いに素で、aとb₂も互いに素であればaとb₁b₂は互いに素である。

aとbが互いに素であることと 2^a-1 と2^b-1 が互いに素であることは同値である。

「aとbが互いに素であるなら同じ素数を共通の約数にはもたない」ということを利用して、任意に選んだaとbが互いに素である確率を以下のように求めることができる。まず、ある素数pで任意に選んだ整数が割り切れる確率は 1/p となる。したがってaとbのうち少なくとも一つがpで割り切れない確率（同じ素数pを共通の約数にもたない確率）は 1-(aがpで割り切れる確率 × bがpで割り切れる確率)=1-1/p² となる。さらに全ての素数に関してこの確率の総乗をとった次式がaとbが互いに素である確率である。

$\prod_p^{\infty} \left(1-\frac{1}{p^2}\right) = \left( \prod_p^{\infty} \frac{1}{1-p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2} \approx 0.6079271$

ζはゼータ関数を表す。ζ(2)の値はレオンハルト・オイラーによって求められた。一般にk個の任意に選んだ整数が互いに素である確率は 1/ζ(k) で表される。

関連項目

• 最大公約数
• 素因数分解
• オイラーのφ関数
• 算術の基本定理