互いに素

互いに素の最新ニュースをまとめて検索！

この項目では、2つの整数の関係について記述しています。集合については「素集合」をご覧ください。

互いに素（たがいにそ、英: coprime）は、2つの整数が1と-1以外に共通の約数を持たない場合の2数の関係である。これは2つの整数の最大公約数が1であることと同値である。例えば35と12は共通の素因数を持たず、それらの最大公約数は1になるので互いに素である。1と-1は（0や±1自身を含む）全ての整数と互いに素であり、0は1および-1とのみ互いに素である。また3つ以上の整数の間でも互いに素の関係は同様に定義できる。

2数が互いに素であるかどうか、すなわち最大公約数がいくらであるかを調べる最良のアルゴリズムとしてユークリッドの互除法がある。これによって素因数分解によらずに最大公約数が求まり、互いに素であるかどうかを知ることができる。

[編集] 互いに素である数の性質

整数a,bが互いに素であれば ax+by=1 を満たす整数x,yが存在する。またaとb₁が互いに素で、aとb₂も互いに素であればaとb₁b₂は互いに素である。

aとbが互いに素であることと 2^a-1 と2^b-1 が互いに素であることは同値である。

「aとbが互いに素であるなら同じ素数を共通の約数にはもたない」ということを利用して、任意に選んだaとbが互いに素である確率を以下のように求めることができる。まず、ある素数pで任意に選んだ整数が割り切れる確率は 1/p となる。したがってaとbのうち少なくとも一つがpで割り切れない確率（同じ素数pを共通の約数にもたない確率）は 1-(aがpで割り切れる確率 × bがpで割り切れる確率)=1-1/p² となる。さらに全ての素数に関してこの確率の総乗をとった次式がaとbが互いに素である確率である。

$\prod_p^{\infty} \left(1-\frac{1}{p^2}\right) = \left( \prod_p^{\infty} \frac{1}{1-p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2} \approx 0.6079271$

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

最終更新 2009年9月16日 (水) 11:34 （日時は個人設定で未設定ならばUTC）。
【互いに素】変更履歴

互いに素

[編集] 互いに素である数の性質

[編集] 関連項目

もっと調べる！