互いに素な整数

数論では、2 つの整数aとbは、両方の約数となる唯一の正の整数が 1 である場合、互いに素、相対的に素、または互いに素であると言います。 ^{[ 1 ]}その結果、aを割り切る素数はb を割り切らず、その逆もまた然りです。これは、それらの最大公約数(GCD) が 1 であることと同等です。^{[ 2 ]}また、aはbと素である、またはaはbと互いに素であると言います。

8と9は互いに素である。どちらも単独では素数ではないが、共通の約数が1しかないため、互いに素である。一方、6と9は互いに素ではない。どちらも3で割り切れるからである。既約分数の分子と分母は、定義により互いに素である。

整数aとb が互いに素である場合、この事実を数学的記法で表現する標準的な方法は、それらの最大公約数が 1 であることを示すことであり、公式gcd( a , b ) = 1または( a , b ) = 1で表されます。1989 年の教科書Concrete Mathematicsで、Ronald Graham、Donald Knuth、およびOren Patashnik は、別の記法を提案しました。${\displaystyle a\perp b}$aとbが互いに素であることを示し、互いに素であるという意味ではなく、「素数」という用語を使用する（例：aはbと素数である）。^{[ 3 ]}

2つの数が互いに素であるかどうかを素早く判定する方法としては、ユークリッドの互除法や、バイナリ最大公約数法、レーマーの最大公約数法などのより高速な変種が挙げられます。

1 からnまでの正の整数nと互いに素な整数の数は、オイラーのトーシェント関数、別名オイラーのファイ関数φ ( n )によって与えられます。

整数の集合は、その要素が 1 以外の共通の正の因数を持たない場合、互いに素であるとも呼ばれます。整数の集合に対するより強い条件は、ペアワイズ互いに素であることであり、これは、集合内の異なる整数のすべてのペア( a , b )に対して、 aとbが互いに素であることを意味します。集合{2, 3, 4}は互いに素ですが、2 と 4 は互いに素ではないため、ペアワイズ互いに素ではありません。

1と-1は、すべての整数と互いに素な唯一の整数であり、0と互いに素な唯一の整数でもある。

aとbが互いに素であることと同等の条件はいくつかあります。

• aとbの両方を割り切る素数は存在しない。
• ax + by = 1となるような整数x, yが存在する（ベズーの恒等式を参照）。
• 整数bは法aに関して乗法逆元を持ちます。つまり、ある整数yが存在して、 by ≡ 1 (mod a )となります。環論的な言葉で言えば、bは環 ⁠の単位元です。${\displaystyle \mathbb {Z} /a\mathbb {Z} }$aを法とする整数 の⁠。
• 未知の整数xに対するx ≡ k (mod a )およびx ≡ m (mod b )の形の合同関係のペアはすべて解を持ちます (中国剰余定理)。実際、解はabを法とする単一の合同関係によって記述されます。
• aとbの最小公倍数は、それらの積abに等しい。つまり、lcm( a , b ) = abである。^{[ 4 ]}

3 点の結果として、aとbが互いに素でbr ≡ bs (mod a )ならば、r ≡ s (mod a )となります。^{[ 5 ]}つまり、aを法として計算する場合、「 bで割る」ことができます。さらに、b ₁とb ₂が両方ともaと互いに素であれば、それらの積b ₁ b ₂も a と互いに素です(つまり、a を法として、それは可逆要素の積であり、したがって可逆です)。^{[ 6 ]}これは、素数p が積bcを割り切るならば、p は因数b、cの少なくとも 1 つを割り切るというユークリッドの補題によって、最初の点からも導かれます。

最初の点の結果として、aとbが互いに素であれば、任意のべき乗a ^kとb ^mも互いに素である。

aとbが互いに素で、aが積bcを割り切るならば、aはcを割り切る。^{[ 7 ]}これはユークリッドの補題の一般化と見なすことができる。

2つの整数aとbが互いに素であるのは、デカルト座標系において座標( a , b )を持つ点が原点(0, 0)から遮るもののない視線で「見える」場合、すなわち、原点と( a , b )の間の線分上に整数座標を持つ点が存在しない場合に限る。（図 1 を参照。）

厳密に言えば、ランダムに選ばれた2つの整数が互いに素である確率は6/ π²^で、約61%です（下記の§ 互いに素である確率を参照）。

2つの自然数aとb が互いに素であるのは、 2 ^a − 1と2 ^b − 1が互いに素である場合に限る。^{[ 8 ]}この一般化として、n > 1を基数とするユークリッドの互除法から容易に導かれる。

${\displaystyle \gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1.}$

整数の集合${\displaystyle S=\{a_{1},a_{2},\dots ,a_{n}\}}$集合のすべての要素の最大公約数が1である場合、それらは互いに素である、または集合的に互いに素であるとも呼ばれます。たとえば、整数6、10、15は互いに素です。なぜなら、1はそれらすべてを割り切る唯一の正の整数だからです。

整数の集合内のすべてのペアが互いに素である場合、その集合はペアごとに互いに素である（またはペアごとに相対的に素である、相互に互いに素である、または相互に相対的に素である）と言われます。ペアごとの互いに素であることは、集合ごとの互いに素であることよりも強い条件です。ペアごとに互いに素な有限集合はすべて集合ごとに互いに素ですが、その逆は真ではありません。たとえば、整数 4、5、6 は（集合ごとに）互いに素です（これらすべてを割り切る唯一の正の整数は 1 であるため）が、ペアごとに互いに素ではありません（gcd(4, 6) = 2 であるため）。

ペアワイズ素数性の概念は、中国剰余定理など、数論における多くの結果の仮説として重要である。

無限個の整数の集合が互いに素であるということはあり得る。顕著な例としては、すべての素数の集合、シルベスター数列の要素の集合、すべてのフェルマー数の集合などが挙げられる。

ランダムに選ばれた2つの整数aとbが与えられたとき、 aとbが互いに素である確率はどのくらいかと問うのは妥当である。この判定において、aとbが互いに素であるのは、 aとbの両方を割り切る素数が存在しない場合に限るという特徴付けを用いると便利である（算術の基本定理を参照）。

非公式には、任意の数が素数（または実際には任意の整数） pで割り切れる確率は、${\displaystyle {\tfrac {1}{p}};}$例えば、7番目の整数はすべて7で割り切れます。したがって、2つの数が両方ともpで割り切れる確率は${\displaystyle {\tfrac {1}{p^{2}}},}$そして、少なくとも1つがそうでない確率は${\displaystyle 1-{\tfrac {1}{p^{2}}}.}$異なる素数に関連付けられた有限個の割り算事象の集合は、 互いに独立である。たとえば、2 つの事象の場合、ある数が素数pとqで割り切れるのは、その数がpqで割り切れる場合のみである。後者の事象の確率は である。${\displaystyle {\tfrac {1}{pq}}.}$ このような推論を無限に多くの割り算事象に拡張できるというヒューリスティックな仮定を置くと、2 つの数が互いに素である確率はすべての素数の積で与えられると推測される。

$\displaystyle \prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{{\text{prime }}p}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.607927102\approx 61\%.}$

ここでζはリーマンゼータ関数を指し、素数上の積とζ (2)を関連付ける恒等式はオイラー積の一例であり、 ζ (2)をπ2 ^/ 6と評価することは、1735年にレオンハルト・オイラーによって解決されたバーゼル問題である。

各正の整数が等しい確率で出現するように正の整数をランダムに選択する方法はありませんが、上記のような「ランダムに選択された整数」に関する記述は、自然密度の概念を用いることで形式化できます。各正の整数Nに対して、P _{N を}、ランダムに選択された 2 つの数値が等しい確率とします。${\displaystyle \{1,2,\ldots ,N\}}$互いに素である。PN は決して 6/π 2 と正確に等しくなることはないが、[ a ^]の作業により、^{極限において次}のようになることが示される_。${\displaystyle N\to \infty ,}$確率P _{N は}6/ π ²に近づく。

より一般的には、無作為に選ばれたk 個の整数が互いに素である確率は⁠${\displaystyle {\tfrac {1}{\zeta (k)}}.}$[ ^{9 ]​}

互いに素な正の数のペア( m , n ) ( m > n ) はすべて、互いに素な 2 つの完全三分木に配置できます。1 つの木は(2, 1)から始まり(偶数-奇数および奇数-偶数のペア用)、^{[ 10 ]}もう 1 つの木は(3, 1)から始まり(奇数-奇数のペア用) です。^{[ 11 ]}各頂点( m , n )の子は次のように生成されます。

• 支店1：${\displaystyle (2m-n,m)}$
• 支店2：${\displaystyle (2m+n,m)}$
• ブランチ3：${\displaystyle (m+2n,n)}$

このスキームは網羅的で冗長性がなく、無効なメンバーもありません。これは、もし${\displaystyle (a,b)}$は互いに素なペアである${\displaystyle a>b,}$それから

• もし${\displaystyle a>3b,}$それから ${\displaystyle (a,b)}$の子供です${\displaystyle (m,n)=(a-2b,b)}$3番の分岐に沿って。
• もし${\displaystyle 2b<a<3b,}$それから${\displaystyle (a,b)}$の子供です${\displaystyle (m,n)=(b,a-2b)}$分岐2に沿って。
• もし${\displaystyle b<a<2b,}$それから${\displaystyle (a,b)}$の子供です${\displaystyle (m,n)=(b,2b-a)}$1番の枝に沿って。

すべての場合において${\displaystyle (m,n)}$は「より小さい」互いに素なペアで、${\displaystyle m>n.}$この「父親を計算する」プロセスは、以下のいずれかの場合にのみ停止できます。${\displaystyle a=2b}$または${\displaystyle a=3b.}$これらの場合、共素性は、ペアが以下であることを意味します。${\displaystyle (2,1)}$または${\displaystyle (3,1).}$

正の互いに素なペア( m , n ) ( m > n ) の木を生成する別の (はるかに簡単な) 方法は、2 つのジェネレーターを使用することです。${\displaystyle f:(m,n)\rightarrow (m+n,n)}$そして${\displaystyle g:(m,n)\rightarrow (m+n,m)}$ルートから始める${\displaystyle (2,1)}$結果として得られる二分木、カルキン・ウィルフ木は網羅的かつ非冗長であり、それは次のように見ることができる。互いに素なペアが与えられた場合、再帰的に適用する。${\displaystyle f^{-1}}$または${\displaystyle g^{-1}}$どちらがm > nとなる正の互いに素なペアを生成するかによって、ツリーは非冗長になります。この手順では必ずルートに到達するため、ツリーは網羅的です。

機械設計において、歯車の摩耗を均一にするためには、噛み合う2つの歯車の歯数を互いに素となるように選択する必要がある。1：1の歯車比が必要な場合は、同じサイズの2つの歯車の間に、互いに素となる歯車を挿入すればよい。

コンピュータ以前の暗号では、一部のバーナム暗号機は、長さの異なる複数の鍵テープのループを組み合わせていました。多くのローター式暗号機は、歯数の異なるローターを組み合わせています。このような組み合わせは、長さの全体が互いに素である場合に最も効果的です。^{[ 12 ] [ 13 ] [ 14 ] [ 15 ]}

この概念は、他の代数構造にも拡張できる。${\displaystyle \mathbb {Z}$ ;} ⁠例えば、最大公約数が1 である多項式は互いに素な多項式。

• ユークリッドの果樹園
• スーパーパーティネントナンバー

• Hardy, GH ; Wright, EM (2008) 『数論入門』（第6 版）、オックスフォード大学出版局、ISBN 978-0-19-921986-5
• ニブン、イヴァン；ザッカーマン、ハーバート・S（1966）『数論入門』（第2 版）、ジョン・ワイリー＆サンズ
• オレ、オイスタイン（1988）[1948]、『数論とその歴史』、ドーバー出版、ISBN 978-0-486-65620-5
• ローゼン、ケネス・H. (1992)、初等整数論とその応用（第3 版）、アディソン・ウェスリー、ISBN 978-0-201-57889-8

• ロード、ニック（2008年3月）「いくつかの無限互いに素な数列の均一構成」、Mathematical Gazette、92：66–70。