互いに素 (整数論)のソースを表示

{{Otheruses|2つの整数の関係|互いに素な集合|素集合}}
{{出典の明記|date=2016年6月}}
二つの[[整数]] {{math|{{mvar|a}}, {{mvar|b}}}} が'''互いに素'''（たがいにそ、{{lang-en-short|coprime, relatively prime, prime to}}{{sfn|Baker|1984|p={{google books quote|id=hAFfb8BBC0IC|page=2|2}}}}）であるとは、{{math|{{mvar|a}}, {{mvar|b}}}} を共に割り切る正の整数が {{math|1}} のみであることをいう。このことは {{math|{{mvar|a}}, {{mvar|b}}}} の[[最大公約数]] {{math|gcd({{mvar|a}}, {{mvar|b}})}} が {{math|1}} であることと同値である。{{math|{{mvar|a}}, {{mvar|b}}}} が互いに素であることを、記号で {{math|{{mvar|a}} [[垂直記号|⊥]] {{mvar|b}}}} と表すこともある{{sfn|Graham|Knuth|Patashnik|1989|p=}}。なお、「互いに素」を意味する英単語には {{en|coprime}} と {{en|disjoint}} があるが、{{en|coprime}} は整数について「互いに素」「共通点を持たない」という意味で使用される。

==概要==
例えば、{{math|[[3]]}} と {{math|[[10]]}} を共に割り切る正の整数は {{math|1}} だけなので、これらは互いに素である。逆に、{{math|3}} と {{math|[[6]]}} は共に {{math|3}} で割り切れるので、これらは互いに素ではない。もう少し大きい数だと、{{math|[[729]]}} と {{math|[[1000]]}} を共に割り切る正の整数は {{math|1}} だけなので、これらは互いに素である。逆に、{{math|729}} と {{math|[[1296]]}} は {{math|[[3]]}}、{{math|[[9]]}}、{{math|[[27]]}}、{{math|[[81]]}} の四つで割り切れるので、この二つは互いに素ではない。同じく、{{math|1000}} と {{math|1296}} も、{{math|[[2]]}}、{{math|[[4]]}}、{{math|[[8]]}} の三つで割り切れるので、この二つも互いに素ではない。

互いに素であることの判定は[[素因数分解]]を用いて行うこともできるが、二つの整数のうち少なくとも一方が巨大である場合など一般には困難である。素因数分解によって公約数を調べる方法よりも、[[ユークリッドの互除法]]によって最大公約数を調べる方法のほうが遥に速い。

正の整数 {{mvar|n}} と互いに素となる（{{math|1}} から {{mvar|n}} の間の）整数の個数は、[[オイラー関数]] {{math|{{mvar|φ}}({{mvar|n}})}} によって与えられる。

三つの整数 {{math|{{mvar|a}}, {{mvar|b}}, {{mvar|c}}}} が'''互いに素'''であるとは、{{math|gcd({{mvar|a}}, {{mvar|b}}, {{mvar|c}}) {{=}} 1}} が成り立つことをいう。また、{{math|gcd({{mvar|a}}, {{mvar|b}})}}、{{math|gcd({{mvar|b}}, {{mvar|c}})}}、{{math|gcd({{mvar|c}}, {{mvar|a}})}} がすべて {{math|1}} に等しいとき、{{math|{{mvar|a}}, {{mvar|b}}, {{mvar|c}}}} は'''対ごとに素'''（{{lang-en-short|pairwise coprime}}）または'''どの二つも互いに素'''であるという。一般に、互いに素であるからといって対ごとに素であるとは限らない　　（例：{{math|{{mvar|a}} {{=}} 6, {{mvar|b}} {{=}} 15, {{mvar|c}} {{=}} 10}}）。一般の {{mvar|n}} 個の整数についても同様に定義される。

== 性質 ==
* {{math|0}} と互いに素となる整数は {{math|1}} と {{math|&minus;1}} だけであり、また任意の整数と互いに素となる整数も {{math|1}} と {{math|&minus;1}} だけである。
* 異なる二つの[[素数]]は互いに素であり、連続する二つの整数も互いに素である。
* {{math|2}} 以上の整数は、その（自身を含む）[[倍数]]や {{math|2}} 以上の約数と互いに素でない。
* {{mvar|a}} と {{math|{{mvar|b}}{{msub|1}}}}、{{mvar|a}} と {{math|{{mvar|b}}{{msub|2}}}} がそれぞれ互いに素ならば、{{mvar|a}} と {{math|{{mvar|b}}{{msub|1}}{{mvar|b}}{{msub|2}}}} も互いに素である。

以下は、整数 {{math|{{mvar|a}}, {{mvar|b}}}} が互いに素であることと同値な条件である。

* {{math|{{mvar|a}}, {{mvar|b}}}} を共に割り切る[[素数]]が存在しない。
* {{math|{{mvar|ax}} + {{mvar|by}} {{=}} 1}} を満たす整数 {{math|{{mvar|x}}, {{mvar|y}}}} が存在する。（[[ベズーの等式]]を参照）
* {{mvar|b}} は {{mvar|a}} を[[モジュラ逆数|法とする逆数]]をもつ。即ち {{math|{{mvar|by}} ≡ 1 (mod {{mvar|a}})}} を満たす整数 {{mvar|y}} が存在する。別の言い方をすれば、{{mvar|b}} は {{mvar|a}} を法とする[[剰余類環]] {{math|'''Z'''/{{mvar|a}}'''Z'''}} の[[可逆元|単元]]となっている。
* {{math|{{mvar|a}}, {{mvar|b}}}} の[[最小公倍数]] {{math|lcm({{mvar|a}}, {{mvar|b}})}} が積 {{mvar|ab}} に等しい。
* {{math|{{mvar|a}}, {{mvar|b}}}} の[[最大公約数]] {{math|gcd({{mvar|a}}, {{mvar|b}})}} が {{math|1}} に等しい。
* {{math|2{{msup|{{mvar|a}}}} &minus; 1}} と {{math|2{{msup|{{mvar|b}}}} &minus; 1}} が互いに素。

== 互いに素である確率 ==
整数の中から任意に選んだ2つの数 {{mvar|a}} と {{mvar|b}} が互いに素である[[確率]]を、ナイーブには、以下のように求めることができる。

{{mvar|a}} と {{mvar|b}} が互いに素とは、任意の[[素数]] {{mvar|p}} に対して、{{mvar|a}} と {{mvar|b}} の少なくとも一方が {{mvar|p}} の倍数でないこと、と言い換える。

{{mvar|p}} を固定したとき、この[[事象 (確率論)|事象]]は、{{math|{{mvar|a}}, {{mvar|b}}}} がともに {{mvar|p}} の倍数である事象の余事象である。

{{mvar|a}} が {{mvar|p}} の倍数である確率は {{math|{{sfrac|1|{{mvar|p}}}}}} である。（{{mvar|b}} についても同様）

各 {{mvar|p}} に対して、これらの試行は[[独立 (確率論)|独立]]だから、求める確率は、

:<math>\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.</math><ref>{{Cite web |url=https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1240-23.pdf |title=「 2 整数が互いに素になる確率」 の確率論的見方 一数値実験による予想の検証一 |access-date=2024/2/11 |publisher=京都大学}}</ref>

ここで、{{mvar|[[ζ]]}} は[[リーマンゼータ函数|リーマンのゼータ関数]]を表す。[[バーゼル問題|{{math|{{mvar|ζ}}(2)}} の値]]は[[レオンハルト・オイラー]]によって求められた。一般に、任意に選んだ {{mvar|k}} 個の整数が互いに素である確率は {{math|1/{{mvar|ζ}}({{mvar|k}})}} で表される。

== 互いに素な整数の組の生成 ==
[[File:Coprime8.svg|300px|thumb|このアルゴリズムによる互いに素な組の生成の順番。最初のノード {{math|(2, 1)}} を赤、その三つの子ノードを橙、さらにその子ノードを黄色で示し、それ以降を虹色の順に色を用いて示した。]]
すべての互いに素な正の整数の組 {{math|({{mvar|m}}, {{mvar|n}})}}（ただし {{math|{{mvar|m}} &gt; {{mvar|n}}}}）は、二つの[[素集合|互いに素]]な完全{{仮リンク|三分木|en|Ternary tree}}を用いて並べることができる。片方の木は {{math|(2, 1)}} から始まり偶数・奇数および奇数・偶数の組を{{sfn|Saunders|Randall|1994}}、もう片方は {{math|(3, 1)}} から始まり奇数・奇数の組を{{sfn|Mitchell|2001}}生成する。このときノード {{math|({{mvar|m}}, {{mvar|n}})}} から生成される三つの子ノードはそれぞれ次のように表される。

# {{math|(2{{mvar|m}} &minus; {{mvar|n}}, {{mvar|m}})}}
# {{math|(2{{mvar|m}} + {{mvar|n}}, {{mvar|m}})}}
# {{math|({{mvar|m}} + 2{{mvar|n}}, {{mvar|n}})}}

以上により生成される組は常に互いに素であり、すべての組が重複なく網羅される。

== 実用、応用 ==
*[[固定ギア]]の[[自転車]]の理想的なスキッドポイントの設計 - 固定ギアの自転車のチェーンリングとコグの歯数が「互いに素」であると、スキッドポイントと呼ばれるタイヤが摩耗する点はコグの歯数と同じになる。

== 脚注 ==
{{reflist}}

== 参考文献 ==
* {{cite book
|last=Baker
|first=Alan
|authorlink=アラン・ベイカー
|title=A Concise Introduction to the Theory of Numbers
|year=1984
|publisher=Cambridge University Press
|isbn=0-521-28654-9
|ref=harv
}}
* {{citation
|first1=R. L.
|last1=Graham
|first2=D. E.
|last2=Knuth
|first3=O.
|last3=Patashnik
|title=Concrete Mathematics
|publisher=Addison-Wesley
|year=1989
|ref=harv
}}
* {{Citation2
|last=Saunders
|first=Robert
|name-list-style=amp
|last2=Randall
|first2=Trevor
|title=The family tree of the Pythagorean triplets revisited
|journal=Mathematical Gazette
|volume=78
|date=July 1994
|pages=190–193
|doi=10.2307/3618576
}}
* {{Citation
|last=Mitchell
|first=Douglas W.
|title=An alternative characterisation of all primitive Pythagorean triples
|journal=Mathematical Gazette
|volume=85
|date=July 2001
|pages=273–275
|doi=10.2307/3622017
|ref=harv
}}

== 関連項目 ==
{{wiktionary}}
*[[最大公約数]]
*[[素因数分解]]
*[[オイラーのφ関数]]
*[[算術の基本定理]]
*[[分数#規約分数]]（既約分数）

{{素数の分類}}
{{DEFAULTSORT:たかいにそ}}
[[Category:数論]]
[[Category:数学に関する記事]]