利用者:Flightbridge/sandbox/互いに素

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

例えば $14$ と $15$ を共に割り切る正の整数は $1$ に限られるから、これらは互いに素である。一方で $14$ と $21$ は共に $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$ 以上の約数と互いに素でない。
$a$ と $b 1$ 、 $a$ と $b 2$ がそれぞれ互いに素ならば、 $a$ と $b 1 b 2$ も互いに素である。

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

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

互いに素である確率

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

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

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

$a$ が $p$ の倍数である確率は $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/p$ である。（ $b$ についても同様）

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

\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.

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

性質

互いに素である確率

関連項目