互いに素

互いに素（たがいにそ、テンプレート:Lang-en-short）は、2つの整数が 1 と −1 以外に公約数を持たない場合の2数の関係である。これは2つの整数の最大公約数が 1 であることと同値である。2つの整数 a, b が互いに素であることを、記号で a ⊥ b と表すこともある。

3つの整数 a, b, c について、a　と b、b と c、c と a の公約数がそれぞれ 1 と −1 のみでなくても、a, b, c の公約数としては 1 と −1 のみのときがある（例：a = 6, b =15, c = 10）。このようなとき、a, b, c は互いに素という。一般のn個の整数についても同様に定義される。

2整数の少なくとも1つが大きい場合、互いに素であるかどうかを知るのに、素因数分解による方法では、一般には困難である。素因数分解をせずに最大公約数を求める最良のアルゴリズムである、ユークリッドの互除法がある。これにより、最大公約数が 1 であれば互いに素、2 以上ならば互いに素ではないことが分かる。

例

12 = 2² × 3 と 35 = 5 × 7 は、共通の素因数を持たないから公約数は 1 と分かる。したがって、互いに素である。6 = 2 × 3 と 14 = 2 × 7 は、2 を公約数に持つので、互いに素ではない。

1, −1 はそれぞれ（0 や ±1 自身を含む）全ての整数と互いに素であり、0 は 1 および −1 とのみ互いに素である。一般に、異なる2つの素数は互いに素であり、連続する2つの整数も互いに素である。2 以上の整数は、その（自身を含む）倍数や 2 以上の約数と互いに素でない。

互いに素である数の性質

• 整数 a, b が互いに素ならば、ax + by = 1 を満たす整数 x, y が存在する。（証明は、ユークリッドの互除法による。）
• a と b₁、a と b₂ がそれぞれ互いに素ならば、a と b₁b₂ も互いに素である。
• a と b が互いに素であることと 2^a − 1 と 2^b − 1 が互いに素であることは同値である。

互いに素である確率

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

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

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

a が p の倍数である確率は テンプレート:Sfrac である。（b についても同様）

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

<math>\prod_{p:\text{prime}}^{\infty} \left\{ 1-\left( \frac{1}{p} \right)^2 \right\} =\left( \prod_{p:\text{prime}}^{\infty} \frac{1}{1-p^{-2}} \right)^{-1} =\frac{1}{\zeta (2)} =\frac{6}{\pi^2} \approx 0.6079271</math>

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

関連項目

• 最大公約数
• 素因数分解
• オイラーのφ関数
• 算術の基本定理