互いに素 (整数論)

テンプレート:Otheruses テンプレート:出典の明記二つの整数テンプレート:Math が互いに素（たがいにそ、テンプレート:Lang-en-short テンプレート:Sfn）であるとは、テンプレート:Math を共に割り切る正の整数がテンプレート:Math のみであることをいう。このことはテンプレート:Math の最大公約数テンプレート:Math がテンプレート:Math であることと同値である。テンプレート:Math が互いに素であることを、記号でテンプレート:Math と表すこともあるテンプレート:Sfn。なお、「互いに素」を意味する英単語にはテンプレート:En とテンプレート:En があるが、テンプレート:En は整数について「互いに素」「共通点を持たない」という意味で使用される。

概要

例えば、テンプレート:Math とテンプレート:Math を共に割り切る正の整数はテンプレート:Math だけなので、これらは互いに素である。逆に、テンプレート:Math とテンプレート:Math は共にテンプレート:Math で割り切れるので、これらは互いに素ではない。もう少し大きい数だと、テンプレート:Math とテンプレート:Math を共に割り切る正の整数はテンプレート:Math だけなので、これらは互いに素である。逆に、テンプレート:Math とテンプレート:Math はテンプレート:Math、テンプレート:Math、テンプレート:Math、テンプレート:Math の四つで割り切れるので、この二つは互いに素ではない。同じく、テンプレート:Math とテンプレート:Math も、テンプレート:Math、テンプレート:Math、テンプレート:Math の三つで割り切れるので、この二つも互いに素ではない。

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

正の整数テンプレート:Mvar と互いに素となる（テンプレート:Math からテンプレート:Mvar の間の）整数の個数は、オイラー関数テンプレート:Math によって与えられる。

三つの整数テンプレート:Math が互いに素であるとは、テンプレート:Math が成り立つことをいう。また、テンプレート:Math、テンプレート:Math、テンプレート:Math がすべてテンプレート:Math に等しいとき、テンプレート:Math は対ごとに素（テンプレート:Lang-en-short）またはどの二つも互いに素であるという。一般に、互いに素であるからといって対ごとに素であるとは限らない　　（例：テンプレート:Math）。一般のテンプレート:Mvar 個の整数についても同様に定義される。

テンプレート:Math と互いに素となる整数はテンプレート:Math とテンプレート:Math だけであり、また任意の整数と互いに素となる整数もテンプレート:Math とテンプレート:Math だけである。
異なる二つの素数は互いに素であり、連続する二つの整数も互いに素である。
テンプレート:Math 以上の整数は、その（自身を含む）倍数やテンプレート:Math 以上の約数と互いに素でない。
テンプレート:Mvar とテンプレート:Math、テンプレート:Mvar とテンプレート:Math がそれぞれ互いに素ならば、テンプレート:Mvar とテンプレート:Math も互いに素である。

以下は、整数テンプレート:Math が互いに素であることと同値な条件である。

整数の中から任意に選んだ2つの数テンプレート:Mvar とテンプレート:Mvar が互いに素である確率を、ナイーブには、以下のように求めることができる。

テンプレート:Mvar を固定したとき、この事象は、テンプレート:Math がともにテンプレート:Mvar の倍数である事象の余事象である。

各テンプレート:Mvar に対して、これらの試行は独立だから、求める確率は、

\prod_{p : prime} {1 - {(\frac{1}{p})}^{2}} = {(\prod_{p : prime} \frac{1}{1 - p^{- 2}})}^{- 1} = \frac{1}{ζ (2)} = \frac{6}{π^{2}} \approx 0.6079271 .

^[1]

ここで、テンプレート:Mvar はリーマンのゼータ関数を表す。[[バーゼル問題|テンプレート:Math の値]]はレオンハルト・オイラーによって求められた。一般に、任意に選んだテンプレート:Mvar 個の整数が互いに素である確率はテンプレート:Math で表される。

すべての互いに素な正の整数の組テンプレート:Math（ただしテンプレート:Math）は、二つの互いに素な完全テンプレート:仮リンクを用いて並べることができる。片方の木はテンプレート:Math から始まり偶数・奇数および奇数・偶数の組をテンプレート:Sfn、もう片方はテンプレート:Math から始まり奇数・奇数の組をテンプレート:Sfn生成する。このときノードテンプレート:Math から生成される三つの子ノードはそれぞれ次のように表される。

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

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