互いに素 (整数論)

二つの整数 が互いに素（たがいにそ、）であるとは、 を共に割り切る正の整数が のみであることをいう。このことは の最大公約数 が であることと同値である。 が互いに素であることを、記号で と表すこともある。なお、「互いに素」を意味する英単語には と があるが、 は整数について「互いに素」「共通点を持たない」という意味で使用される。
概要.
例えば、 と を共に割り切る正の整数は だけなので、これらは互いに素である。逆に、 と は共に で割り切れるので、これらは互いに素ではない。もう少し大きい数だと、 と を共に割り切る正の整数は だけなので、これらは互いに素である。逆に、 と は 、、、 の四つで割り切れるので、この二つは互いに素ではない。同じく、 と も、、、 の三つで割り切れるので、この二つも互いに素ではない。
互いに素であることの判定は素因数分解を用いて行うこともできるが、二つの整数のうち少なくとも一方が巨大である場合など一般には困難である。素因数分解によって公約数を調べる方法よりも、ユークリッドの互除法によって最大公約数を調べる方法のほうが遥に速い。
正の整数 と互いに素となる（ から の間の）整数の個数は、オイラー関数 によって与えられる。
三つの整数 が互いに素であるとは、 が成り立つことをいう。また、、、 がすべて に等しいとき、 は対ごとに素（）またはどの二つも互いに素であるという。一般に、互いに素であるからといって対ごとに素であるとは限らない　　（例：）。一般の 個の整数についても同様に定義される。
性質.
以下は、整数 が互いに素であることと同値な条件である。
互いに素である確率.
整数の中から任意に選んだ2つの数 と が互いに素である確率を、ナイーブには、以下のように求めることができる。
 と が互いに素とは、任意の素数 に対して、 と の少なくとも一方が の倍数でないこと、と言い換える。
 を固定したとき、この事象は、 がともに の倍数である事象の余事象である。
 が の倍数である確率は である。（ についても同様）
各 に対して、これらの試行は独立だから、求める確率は、
ここで、 はリーマンのゼータ関数を表す。の値はレオンハルト・オイラーによって求められた。一般に、任意に選んだ 個の整数が互いに素である確率は で表される。
互いに素な整数の組の生成.
すべての互いに素な正の整数の組 （ただし ）は、二つの互いに素な完全を用いて並べることができる。片方の木は から始まり偶数・奇数および奇数・偶数の組を、もう片方は から始まり奇数・奇数の組を生成する。このときノード から生成される三つの子ノードはそれぞれ次のように表される。
以上により生成される組は常に互いに素であり、すべての組が重複なく網羅される。