互いに素な整数

整数論では、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で、ロナルド・グラハム、ドナルド・クヌース、およびオーレン・パタシュニックは、 $a$ と $b$ が互いに素であることを示す代替表記法を提案し、互いに素である ( $aは$ $b$ と素である)の代わりに「素数」という用語を使用しました。^[3] $a\perp b$

2 つの数が互いに素であるかどうかを判定する高速な方法は、ユークリッドの互除法と、そのより高速な派生アルゴリズムであるバイナリ GCD アルゴリズムやLehmer の GCD アルゴリズムによって提供されます。

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を$ 法とする逆数があります。つまり、 $\equiv 1 (mod$ $a$ $)$ $となる$ 整数 $y が$ 存在するということです。環理論の言語では、 $b は$ $a$ を法とする整数の環⁠ ⁠の単位です。 $\mathbb {Z} /a\mathbb {Z}$
未知の整数 $xに対する、$ $x$ $\equiv$ $k$ $(mod$ $a$ $)$ および $x$ $\equiv$ $m$ $(mod$ $b$ $)$ の形式の合同関係のすべてのペアには解があります (中国剰余定理)。実際、解は $ab を$ 法とする単一の合同関係によって記述されます。
$a$ と $b$ の最小公倍数はそれらの積 $ab$ に等しい、つまり $lcm($ $a$ $,$ $b$ $) =$ $ab$ である。^[4]

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

最初の点の結果として、 $a$ と $b$ が互いに素であれば、任意の累乗 $a k$ と $b m も$ 互いに素になります。

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

図1. 4と9は互いに素である。したがって、4×9格子の対角線は他の格子点と交差しない。

2 つの整数 $a$ と $b$ が互いに素となるのは、直交座標系における座標 $(a, b)の点が原点$ $(0, 0)$ から遮るもののない視線を通じて「見える」場合、つまり原点と $($ $a$ $,$ $b$ $)$ の間の線分上のどこにも整数座標の点が存在しない場合に限ります(図 1 を参照)。

正確に言えば、ランダムに選ばれた 2 つの整数が互いに素である確率は $6/ π 2$ で、約 61% です (以下の「互いに素である確率」を参照)。

2つの $自然$ 数 $a$ と $bが$ 互いに素である場合、かつその場合に限り、 $2a -1$ と $2b - 1$ は互いに素である。^{[8]これを一般化すると、} $n$ $>1を$ 底とするユークリッドの互除法から簡単に次の式が得られる。

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

集合における互いに素なこと

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

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

互いに素であるかどうかという概念は、中国剰余定理など、数論における多くの結果における仮説として重要です。

無限の整数の集合が互いに素である可能性はあります。注目すべき例としては、すべての素数の集合、シルベスター数列の要素の集合、すべてのフェルマー数の集合などがあります。

環イデアルにおける互いに素なこと

可換環 $R$ の2 つのイデアル $A$ と $B が$ 互いに素 (または共最大) であると言われるのは、次の場合です。これはベズーの恒等式を一般化したもので、この定義では、整数環⁠ ⁠の2 つの主イデアル( $a$ ) と ( $b$ )が互いに素であるための必要十分条件は、 $a$ と $bが互いに素である場合です。$ $R$ のイデアル $A$ と $B$ が互いに素である場合、さらに、 $C が$ $Aに$ $BC が$ 含まれるような第 3 のイデアルである場合、 $Aに$ $C が$ 含まれます。中国剰余定理は、互いに素なイデアルを使用して、任意の可換環に一般化できます。 $A+B=R.$ $\mathbb {Z}$ $AB=A\cap B;$

互いに素である確率

ランダムに選ばれた 2 つの整数 $a$ と $b$ が与えられたとき、 $a$ と $bが互いに素である可能性はどれくらいかと問うのは当然です。この判定では、$ $a$ と $b$ が互いに素であるためには、その両方を割り切れる素数が存在しないという特徴付けを使用すると便利です(算術の基本定理を参照)。

非公式には、任意の数が素数（または実際には任意の整数） $pで割り切れる確率は$ ⁠ ⁠ ${\tfrac {1}{p}};$ です。たとえば、7 番目の整数はすべて 7 で割り切れます。したがって、2 つの数が両方とも $pで割り切れる確率は$ ⁠ ⁠ ${\tfrac {1}{p^{2}}},$ であり、少なくとも 1 つが割り切れない確率は⁠ ⁠ $1-{\tfrac {1}{p^{2}}}.$ です。異なる素数に関連付けられた割り切れるイベントの有限のコレクションは、相互に独立しています。たとえば、2 つのイベントの場合、数が素数 $p$ と $qで割り切れるのは、$ $pq$ で割り切れる場合のみです。後者のイベントの確率は⁠ ⁠ ${\tfrac {1}{pq}}.$ です。このような推論を無限に多くの割り切れるイベントに拡張できるという経験的仮定を立てると、2 つの数が互いに素である確率は、すべての素数の積で与えられると推測できます。

\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$ について、でランダムに選択された 2 つの数が互いに素である確率を $P N$ $とします。 P$ $N が$ $6/$ $π$ $2$ と完全に等しくなることはありませんが、^{[9] の}研究により、極限では確率 $P$ $N が$ $6/$ $π$ $2$ に近づくことがわかります。 $\{1,2,\ldots ,N\}$ $N\to \infty ,$

$より一般的には、ランダムに選ばれたk個$ の整数が互いに素である確率は、 ${\tfrac {1}{\zeta (k)}}.$

すべての互いに素なペアを生成する

ツリーのルートは (2, 1) です。ルート (2, 1) は赤でマークされ、その 3 つの子はオレンジ色で表示され、3 世代目は黄色で表示され、以下同様に虹の順序で表示されます。

互いに素な正の数のペア $(m, n)$ (ただし $m > n$ ) はすべて、2つの互いに素な完全三分木に並べることができます。1つは $(2, 1)$ から始まる木(偶数-奇数と奇数-偶数のペア)、^[10]、もう1つは $(3, 1)$ から始まる木(奇数-奇数のペア) です。^{[11]各頂点} $(m, n)$ の子は次のように生成されます。

ブランチ1: $(2m-n,m)$
ブランチ2: $(2m+n,m)$
ブランチ3: $(m+2n,n)$

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

ブランチ 3の子である場合 ; $a>3b,$ $(a,b)$ $(m,n)=(a-2b,b)$
ブランチ 2の子である場合; $2b<a<3b,$ $(a,b)$ $(m,n)=(b,a-2b)$
ブランチ 1の子である場合。 $b<a<2b,$ $(a,b)$ $(m,n)=(b,2b-a)$

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

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

アプリケーション

機械設計では、噛み合う 2 つの歯車の歯数を互いに素となるように選択することで、均等で均一な歯車の摩耗が実現されます。1:1 の歯車比が必要な場合は、2 つの同じサイズの歯車の間に、それらの歯車に互いに素となる歯車を挿入します。

コンピュータ以前の暗号では、いくつかのバーナム暗号機は異なる長さの鍵テープのループをいくつか組み合わせていた。多くのローターマシンは異なる歯数のローターを組み合わせている。このような組み合わせは、長さのセット全体が互いに素である場合に最もうまく機能する。^[12]^[13]^[14]^[15]

一般化

この概念は、 ⁠ ⁠ $\mathbb {Z};$ 以外の代数構造にも拡張できます。たとえば、最大公約数が1 である多項式は互いに素な多項式と呼ばれます。

参照

注記

^ イートン、ジェームズ・S. (1872)。算術に関する論文。ボストン：トンプソン、ビゲロー＆ブラウン。p. 49。2022年1月10日閲覧。2つの数が互いに素数であるのは、それぞれを割り切れる整数が1つしかないときです。
^ ハーディ＆ライト 2008、6ページ
^ Graham, RL; Knuth, DE; Patashnik, O. (1989)、Concrete Mathematics / A Foundation for Computer Science、Addison-Wesley、p. 115、ISBN 0-201-14236-8
^ オレ 1988、47 ページ
^ ニーヴン＆ザッカーマン 1966、p. 22、定理2.3(b)
^ ニーヴン＆ザッカーマン 1966、p. 6、定理1.8
^ ニーヴン＆ザッカーマン 1966、p.7、定理1.10
^ ローゼン 1992、140 ページ
^ この定理は1881年にエルネスト・チェザロによって証明された。証明については、ハーディ＆ライト2008、定理332を参照。
^ サンダース、ロバート & ランドール、トレバー (1994 年 7 月)、「ピタゴラスの三つ子の系図の再考」、数学ガゼット、78 : 190–193、doi :10.2307/3618576。
^ ミッチェル、ダグラス W. (2001 年 7 月)、「すべての原始ピタゴラス数列の代替特性」、Mathematical Gazette、85 : 273–275、doi :10.2307/3622017。
^ Klaus Pommerening. 「暗号学: 長い周期を持つ鍵生成器」
^ David Mowry. 「第二次世界大戦時のドイツの暗号機」 2014年、16ページ、22ページ。
^ Dirk Rijmenants. 「ワンタイムパッドの起源」
^ グスタバス・J・シモンズ。「ヴェルナム・ヴィジュネール暗号」。

参考文献

ハーディ、GH、ライト、EM（2008）、数論入門（第6版）、オックスフォード大学出版局、ISBN 978-0-19-921986-5
ニーヴン、イヴァン、ザッカーマン、ハーバート S. (1966)、数論入門(第 2 版)、ジョンワイリー & サンズ
オーレ、オイステイン（1988）[1948]、数論とその歴史、ドーバー、ISBN 978-0-486-65620-5
ローゼン、ケネス H. (1992)、初等数論とその応用(第 3 版)、Addison-Wesley、ISBN 978-0-201-57889-8

さらに読む

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

[1] イートン、ジェームズ・S. (1872)。算術に関する論文。ボストン：トンプソン、ビゲロー＆ブラウン。p. 49。2022年1月10日閲覧。2つの数が互いに素数であるのは、それぞれを割り切れる整数が1つしかないときです。

[2] ハーディ＆ライト 2008、6ページ

[3] Graham, RL; Knuth, DE; Patashnik, O. (1989)、Concrete Mathematics / A Foundation for Computer Science、Addison-Wesley、p. 115、ISBN 0-201-14236-8

[4] オレ 1988、47 ページ

[5] ニーヴン＆ザッカーマン 1966、p. 22、定理2.3(b)

[6] ニーヴン＆ザッカーマン 1966、p. 6、定理1.8

[7] ニーヴン＆ザッカーマン 1966、p.7、定理1.10

[8] ローゼン 1992、140 ページ

[9] この定理は1881年にエルネスト・チェザロによって証明された。証明については、ハーディ＆ライト2008、定理332を参照。

[10] サンダース、ロバート & ランドール、トレバー (1994 年 7 月)、「ピタゴラスの三つ子の系図の再考」、数学ガゼット、78 : 190–193、doi :10.2307/3618576。

[11] ミッチェル、ダグラス W. (2001 年 7 月)、「すべての原始ピタゴラス数列の代替特性」、Mathematical Gazette、85 : 273–275、doi :10.2307/3622017。

[12] Klaus Pommerening. 「暗号学: 長い周期を持つ鍵生成器」

[13] David Mowry. 「第二次世界大戦時のドイツの暗号機」 2014年、16ページ、22ページ。

[14] Dirk Rijmenants. 「ワンタイムパッドの起源」

[15] グスタバス・J・シモンズ。「ヴェルナム・ヴィジュネール暗号」。