互いに素

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

二つの整数 a, b互いに素(たがいにそ、: coprime, co-prime, relatively prime, mutually prime)であるとは、a, b を共に割り切る正の整数が 1 のみであることをいう。このことは a, b最大公約数 gcd(a, b)1 であることと同値である。a, b が互いに素であることを、記号で ab と表すこともある[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 以上の約数と互いに素でない。
  • ab1ab2 がそれぞれ互いに素ならば、ab1b2 も互いに素である。

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

  • a, b を共に割り切る素数が存在しない。
  • ax + by = 1 を満たす整数 x, y が存在する。(ベズーの等式を参照)
  • ba法とする逆数をもつ。即ち by ≡ 1 (mod a) を満たす整数 y が存在する。別の言い方をすれば、ba を法とする剰余類環 Z/aZ単元となっている。
  • a, b最小公倍数 lcm(a, b) が積 ab に等しい。
  • a, b最大公約数 gcd(a, b)1 に等しい。
  • 2a − 12b − 1 が互いに素。

互いに素である確率[編集]

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

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

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

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

p に対して、これらの試行は独立だから、求める確率は、

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

脚注[編集]

  1. ^ Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics, Addison-Wesley 

関連項目[編集]