互いに素 (整数論)

この項目では、2つの整数の関係について説明しています。互いに素な集合については「素集合」をご覧ください。

二つの整数 a, b が互いに素（たがいにそ、英: coprime, relatively prime, prime to^[1]）であるとは、a, b を共に割り切る正の整数が 1 のみであることをいう。このことは a, b の最大公約数 gcd(a, b) が 1 であることと同値である。a, b が互いに素であることを、記号で a ⊥ b と表すこともある^[2]。なお、「互いに素」を意味する英単語には coprime と disjoint があるが、coprime は整数について「互いに素」「共通点を持たない」という意味で使用される。

概要

例えば、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 個の整数についても同様に定義される。

性質

• 0 と互いに素となる整数は 1 と −1 だけであり、また任意の整数と互いに素となる整数も 1 と −1 だけである。
• 異なる二つの素数は互いに素であり、連続する二つの整数も互いに素である。
• 2 以上の整数は、その（自身を含む）倍数や 2 以上の約数と互いに素でない。
• a と b₁、a と b₂ がそれぞれ互いに素ならば、a と b₁b₂ も互いに素である。

以下は、整数 a, b が互いに素であることと同値な条件である。

• a, b を共に割り切る素数が存在しない。
• ax + by = 1 を満たす整数 x, y が存在する。（ベズーの等式を参照）
• b は a を法とする逆数をもつ。即ち by ≡ 1 (mod a) を満たす整数 y が存在する。別の言い方をすれば、b は a を法とする剰余類環 Z/aZ の単元となっている。
• a, b の最小公倍数 lcm(a, b) が積 ab に等しい。
• a, b の最大公約数 gcd(a, b) が 1 に等しい。
• 2^a − 1 と 2^b − 1 が互いに素。

互いに素である確率

整数の中から任意に選んだ2つの数 a と b が互いに素である確率を、ナイーブには、以下のように求めることができる。

a と b が互いに素とは、任意の素数 p に対して、a と b の少なくとも一方が p の倍数でないこと、と言い換える。

p を固定したとき、この事象は、a, b がともに p の倍数である事象の余事象である。

a が p の倍数である確率は 1/p である。（b についても同様）

各 p に対して、これらの試行は独立だから、求める確率は、

${\displaystyle \prod _{p:{\text{ prime}}}\left\{1-\left({\frac {1}{p}}\right)^{2}\right\}=\left(\prod _{p:{\text{ prime}}}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.6079271.}$^[3]

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

互いに素な整数の組の生成

このアルゴリズムによる互いに素な組の生成の順番。最初のノード (2, 1) を赤、その三つの子ノードを橙、さらにその子ノードを黄色で示し、それ以降を虹色の順に色を用いて示した。

すべての互いに素な正の整数の組 (m, n)（ただし m > n）は、二つの互いに素な完全三分木（英語版）を用いて並べることができる。片方の木は (2, 1) から始まり偶数・奇数および奇数・偶数の組を^[4]、もう片方は (3, 1) から始まり奇数・奇数の組を^[5]生成する。このときノード (m, n) から生成される三つの子ノードはそれぞれ次のように表される。

1. (2m − n, m)
2. (2m + n, m)
3. (m + 2n, n)

以上により生成される組は常に互いに素であり、すべての組が重複なく網羅される。

実用、応用

• 固定ギアの自転車の理想的なスキッドポイントの設計 - 固定ギアの自転車のチェーンリングとコグの歯数が「互いに素」であると、スキッドポイントと呼ばれるタイヤが摩耗する点はコグの歯数と同じになる。