互いに素な整数

数論において、二つの整数 $a$ と $b$ は、両方の約数となる唯一の正の整数が1である場合、互いに素、互いに素、あるいは互いに素である^。[1]したがって、 $a を$ 割り切る素数は $b を$ 割り切れず、その逆も同様である。これは、それらの最大公約数（GCD）が1であることと等しい^。[2]また、 $aは$ $b$ と素である、あるいは $a は$ $b$ と互いに素である、とも言われる。

記法と検定

[編集]

整数 $a$ と $bが互いに素である場合、この事実を$ 数学表記で表現する標準的な方法は、最大公約数が1であることを示すことです。つまり、 $gcd(a, b)=1$ または $(a, b)=1$ です。1989年の教科書『Concrete Mathematics』の中で、ロナルド・グラハム、ドナルド・クヌース、オーレン・パタシュニクは、 $a$ と $b$ が互いに素であることを示す代替表記を提案し、互いに素である代わりに「素数」という用語を使用するようにしました（例： $aは$ $b$ と素である）。^[3] $a\perp b$

2つの数が互いに素であるかどうかを素早く判断する方法は、ユークリッドの互除法と、そのより高速な派生である2元GCDアルゴリズムやレーマーの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\equivbs$ $(mod a)$ ならば、 $r\equivs (mod a)$ $と$ $なる$ 。^[5]つまり、 $a$ $を$ 法として計算する場合、「 $b$ で割る」ことができる。さらに、b⁻¹、b⁻²が両方ともaと互いに素であれば $、$ $それら$ $の$ $積$ $b⁻¹b⁻²$ も互いに素 $で$ $ある$ （つまり、aを法として、可逆な元の積 $で$ $あり$ 、したがって可逆である）。^{[6]これは、}ユークリッドの補題によって $1$ $番目$ の点からも導かれる。ユークリッドの補題は、素数 $pが積$ $bc$ を割り切る場合、 $pは$ 少なくとも1つの因数 $b、c$ を割り切ると述べている。

1番目の点の結果として、 $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$ が互いに素である場合、かつその場合のみ、 $2 a - 1$ と $2 b - 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である$ ため）。

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

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

互いに素である確率

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

$非公式には、任意の数が素数（または実際には任意の整数） p$ で割り切れる確率は⁠ ${\tfrac {1}{p}};$ ⁠です。例えば、7番目の整数はすべて7で割り切れます。したがって、2つの数が両方とも $p$ で割り切れる確率は⁠ ⁠ ${\tfrac {1}{p^{2}}},$ であり、少なくとも一方が割り切れない確率は⁠ ⁠ $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)を$ $π² / 6$ として評価することはバーゼル問題であり、 1735年にレオンハルト・オイラーによって解決されました

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

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

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

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

互いに素な正の数 $(m, n)$ のペア（ $m > n$ ）はすべて、2つの互いに素な完全3分木に配置できます。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つの生成元とを使用することです。結果として得られる二分木、カルキン・ウィルフ木は網羅的で冗長性がなく、次のように見ることができます。互いに素なペアが与えられた場合、どちらが $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である多項式は互いに素な多項式と呼ばれます。

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

可換環 $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;$

注釈

^ イートン、ジェームズ・S. (1872). 『算術論』ボストン：トンプソン、ビゲロー＆ブラウン、p. 49. 2022年1月10日閲覧。2つの数は互いに素とは、それぞれを割り切れる整数が1つしかない場合を指す。
^ ハーディ＆ライト 2008, p. 6
^ グラハム、RL; クヌース、DE; パタシュニク、O. (1989), 『具体的な数学／コンピュータサイエンスの基礎』アドディソン・ウェスレー、p. 115、ISBN 0-201-14236-8
^ オレ 1988, p. 47
^ ニーヴン＆ザッカーマン 1966, p. 22, 定理2.3(b)
^ ニーヴン＆ザッカーマン 1966, p. 6, 定理1.8
^ Niven & Zuckerman 1966, p.7, 定理1.10
^ Rosen 1992, p.140
^ この定理は1881年にエルネスト・チェザロによって証明されました。証明については、Hardy & Wright 2008, 定理332を参照してください
^ サンダース、ロバート＆ランドール、トレバー（1994年7月）、「ピタゴラスの三つ組の系図再考」、Mathematical Gazette、78 : 190–193、doi :10.2307/3618576。
^ ミッチェル、ダグラス・W（2001年7月）、「すべての原始ピタゴラスの三つ組の代替的な特徴づけ」、Mathematical Gazette、85 : 273–275、doi :10.2307/3622017。
^ クラウス・ポメレニング、「暗号学：長周期の鍵生成器」
^ デイヴィッド・モウリー、「第二次世界大戦のドイツの暗号機」、2014年、16ページ、22ページ
^ Dirk Rijmenants. 「ワンタイムパッドの起源」
^ Gustavus J. Simmons. 「Vernam-Vigenère暗号」

参考文献

Hardy, GH ; Wright, EM (2008), 『数論入門』（第6版）、Oxford University Press、ISBN 978-0-19-921986-5
Niven, Ivan; Zuckerman, Herbert S. (1966), 『数論入門』（第2版）、John Wiley & Sons
Ore, Oystein (1988) [1948], 『数論とその歴史』、Dover、ISBN 978-0-486-65620-5
Rosen, Kenneth H. (1992), 『初等数論とその応用』（第3版）、Addison-Wesley、ISBN 978-0-201-57889-8

さらに詳しく

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