互たがいに素もと (整数せいすう論ろん)

二ふたつの整数せいすう $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 1$ 、 $a$ と $b 2$ がそれぞれ互たがいに素そならば、 $a$ と $b 1 b 2$ も互たがいに素そである。

以下いかは、整数せいすう $a, b$ が互たがいに素そであることと同値どうちな条件じょうけんである。

$a, b$ を共ともに割わり切きる素数そすうが存在そんざいしない。
$ax + by = 1$ を満みたす整数せいすう $x, y$ が存在そんざいする。（ベズーの等式とうしきを参照さんしょう）
$b$ は $a$ を法ほうとする逆数ぎゃくすうをもつ。即すなわち $by \equiv 1 (mod a)$ を満みたす整数せいすう $y$ が存在そんざいする。別べつのい方いかたをすれば、 $b$ は $a$ を法ほうとする剰余じょうよ類るい環たまき $Z / a Z$ の単元たんげんとなっている。
$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$ の倍数ばいすうである確かく率りつは $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/p$ である。（ $b$ についても同様どうよう）

各かく $p$ に対たいして、これらの試行しこうは独立どくりつだから、求もとめる確かく率りつは、

\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)$ から生成せいせいされる三みっつの子こノードはそれぞれ次じのように表あらわされる。

$(2 m - n, m)$
$(2 m + n, m)$
$(m + 2 n, n)$

以上いじょうにより生成せいせいされる組くみは常つねに互たがいに素そであり、すべての組くみが重複じゅうふくなく網羅もうらされる。

実用じつよう、応用おうよう[編集へんしゅう]

固定こていギアの自転車じてんしゃの理想りそう的てきなスキッドポイントの設計せっけい - 固定こていギアの自転車じてんしゃのチェーンリングとコグの歯は数すうが「互たがいに素もと」であると、スキッドポイントと呼よばれるタイヤが摩耗まもうする点てんはコグの歯は数すうと同おなじになる。

脚注きゃくちゅう[編集へんしゅう]

^ Baker 1984, p. 2.
^ Graham, Knuth & Patashnik 1989.
^ “「 2 整数せいすうが互たがいに素もとになる確かく率りつ」の確率かくりつ論ろん的てき見方みかた一いち数値すうち実験じっけんによる予想よそうの検証けんしょう一いち”. 京都きょうと大学だいがく. 2024年ねん2月がつ11日にち閲覧えつらん。
^ Saunders & Randall 1994.
^ Mitchell 2001.

参考さんこう文献ぶんけん[編集へんしゅう]

Baker, Alan (1984). A Concise Introduction to the Theory of Numbers. Cambridge University Press. ISBN 0-521-28654-9
Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics, Addison-Wesley
Saunders, Robert & Randall, Trevor (July 1994), "The family tree of the Pythagorean triplets revisited", Mathematical Gazette, 78: 190–193, doi:10.2307/3618576。
Mitchell, Douglas W. (July 2001), “An alternative characterisation of all primitive Pythagorean triples”, Mathematical Gazette 85: 273–275, doi:10.2307/3622017

表ひょう話はなし編へん歴れき素数そすうの分類ぶんるい
生成せいせい式しき	フェルマー ( $2 2 n + 1$ ) メルセンヌ ( $2 p - 1$ ) 二に重じゅうメルセンヌ ( $2 2 p -1 - 1$ ) ワグスタッフ ( $(2 p + 1)/3$ ) プロス ( $k \cdot2 n + 1$ ) 階かい乗じょう ( $n! \pm 1$ ) 素数そすう階かい乗じょう ( $p n # \pm 1$ ) ユークリッド ( $p n # + 1$ ) ピタゴラス ( $4 n + 1$ ) ピアポント ( $2 u \cdot3 v + 1$ ) Quartan（英語えいご版ばん） ( $x 4 + y 4$ ) ソリナス（英語えいご版ばん） ( $2 a \pm 2 b \pm 1$ ) カレン ( $n \cdot2 n + 1$ ) ウッダル ( $n \cdot2 n - 1$ ) Cuban（英語えいご版ばん） ( $(x 3 - y 3)/(x - y)$ ) キャロル ( $(2 n - 1) 2 - 2$ ) Kynea ( $(2 n + 1) 2 - 2$ ) レイランド ( $x y + y x$ ) サービト（英語えいご版ばん） ( $3\cdot2 n - 1$ ) ミルズ ( $[A] 3 n$ )
漸やや化か式しき（英語えいご版ばん）	フィボナッチリュカペルニューマン–シャンクス–ウィリアムズペラン分割ぶんかつベルモツキン
各種かくしゅの性質せいしつ	ヴィーフェリッヒ（英語えいご版ばん） (対たい（英語えいご版ばん）) ウォール–孫まご–孫まご（英語えいご版ばん）ウォルステンホルムウィルソン幸運こううんフォーチュンラマヌジャン（英語えいご版ばん）ピライ正則せいそく強つよ（英語えいご版ばん）スターン Supersingular (楕円だえん曲線きょくせん)（英語えいご版ばん） Supersingular (ムーンシャイン理論りろん)（英語えいご版ばん）良よいスーパーヒッグス（英語えいご版ばん）高度こうどコトーティエント（英語えいご版ばん）
基数きすう依存いぞん	ハッピー二に面めん（英語えいご版ばん）回文かいぶんエマープレピュニット ( $(10 n - 1)/9$ ) 置換ちかん可能かのう Circular（英語えいご版ばん）切きり捨すて可能かのう Strobogrammatic（英語えいご版ばん） Minimal（英語えいご版ばん）弱よわいフルサイクルプライム Unique（英語えいご版ばん） Primeval（英語えいご版ばん）自己じこスマランダチェ–ウェラン（英語えいご版ばん）
組くみ	互たがいに素もと双子ふたご ( $p, p + 2$ ) Bi-twin chain ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) 三みつ子ご ( $p, p + 2$ or $p + 4, p + 6$ ) 四よっつ子こ ( $p, p + 2, p + 6, p + 8$ ) k−Tuple いとこ ( $p, p + 4$ ) セクシー ( $p, p + 6$ ) 陳ひねソフィー・ジェルマン ( $p, 2 p + 1$ ) カニンガム鎖くさり ( $p, 2 p \pm 1, \dots$ ) 安全あんぜん ( $p, (p - 1)/2$ ) 算術さんじゅつ数列すうれつ（英語えいご版ばん） ( $p + an; n = 0, 1, \dots$ ) 平衡へいこう ( $p - n, p, p + n$ )
桁数けたすう	タイタニック ( $103$ 桁けた以上いじょう) 巨大きょだい ( $104$ 桁けた以上いじょう) メガ ( $106$ 桁けた以上いじょう)
複素数ふくそすう	アイゼンシュタイン素数そすう（英語えいご版ばん）ガウス素数そすう
合成ごうせい数すう	擬なずらえ素数そすう概がい素数そすう半はん素数そすう楔くさび数すう Interprime（英語えいご版ばん）
関連かんれんする話題わだい	確かく率りつ的てき素数そすう Industrial-grade prime（英語えいご版ばん）違法いほう素数そすう素数そすうの公式こうしき（英語えいご版ばん）素数そすうの間隔かんかく『巨大きょだいな素数そすうの一覧いちらん』
最初さいしょの50個こ	$2$ $3$ $5$ $7$ $11$ $13$ $17$ $19$ $23$ $29$ $31$ $37$ $41$ $43$ $47$ $53$ $59$ $61$ $67$ $71$ $73$ $79$ $83$ $89$ $97$ $101$ $103$ $107$ $109$ $113$ $127$ $131$ $137$ $139$ $149$ $151$ $157$ $163$ $167$ $173$ $179$ $181$ $191$ $193$ $197$ $199$ $211$ $223$ $227$ $229$
素数そすうの一覧いちらん