互いに素 (整数論)

二つの整数 $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$
素数の一覧

概要

性質

互いに素である確率

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

実用、応用

脚注

参考文献

関連項目