互いに素

提供: miniwiki
移動先:案内検索


二つの整数 a, b互いに素(たがいにそ、: coprime, co-prime, relatively prime, mutually prime)であるとは、a, b を共に割り切る正の整数が 1 のみであることをいう。このことは a, b最大公約数 gcd(a, b)1 であることと同値である。a, b が互いに素であることを、記号で a b と表すこともある[1]

例えば 1415 を共に割り切る正の整数は 1 に限られるから、これらは互いに素である。一方で 1421 は共に 7 で割り切れるから、これらは互いに素でない。

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

正の整数 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 以上の約数と互いに素でない。
  • abテンプレート:Msubabテンプレート:Msub がそれぞれ互いに素ならば、abテンプレート:Msubbテンプレート:Msub も互いに素である。

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

互いに素である確率

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

ab が互いに素とは、任意の素数 p に対して、ab の少なくとも一方が p の倍数でないこと、と言い換える。

p を固定したとき、この事象は、a, b がともに p の倍数である事象の余事象である。

ap の倍数である確率は 1/p である。(b についても同様)

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]

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

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

ファイル:Coprime8.svg
このアルゴリズムによる互いに素な組の生成の順番。最初のノード (2, 1) を赤、その三つの子ノードを橙、さらにその子ノードを黄色で示し、それ以降を虹色の順に色を用いて示した。

すべての互いに素な正の整数の組 (m, n)(ただし m > n)は、二つの互いに素な完全三分木English版を用いて並べることができる。片方の木は (2, 1) から始まり偶数・奇数および奇数・偶数の組を[2]、もう片方は (3, 1) から始まり奇数・奇数の組を[3]生成する。このときノード (m, n) から生成される三つの子ノードはそれぞれ次のように表される。

  1. (2mn, m)
  2. (2m + n, m)
  3. (m + 2n, n)

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

脚注

  1. Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics, Addison-Wesley 
  2. Saunders, Robert & Randall, Trevor (July 1994), “The family tree of the Pythagorean triplets revisited”, Mathematical Gazette 78: 190–193, doi:10.2307/3618576 .
  3. Mitchell, Douglas W. (July 2001), “An alternative characterisation of all primitive Pythagorean triples”, Mathematical Gazette 85: 273–275, doi:10.2307/3622017 .

関連項目