二つの整数 が互いに素（たがいにそ、）であるとは、 を共に割り切る正の整数が のみであることをいう。このことは の最大公約数 が であることと同値である。 が互いに素であることを、記号で と表すこともある。例えば と を共に割り切る正の整数は に限られるから、これらは互いに素である。一方で と は共に で割り切れるから、これらは互いに素でない。互いに素であることの判定は素因数分解を用いて行うこともできるが、二つの整数のうち少なくとも一方が巨大である場合など一般には困難である。素因数分解によって公約数を調べる方法よりも、ユークリッドの互除法によって最大公約数を調べる方法のほうが遥かに高速である。正の整数 と互いに素となる（ から の間の）整数の個数は、オイラー関数 によって与えられる。三つの整数 が互いに素であるとは、 が成り立つことをいう。また、、、 がすべて に等しいとき、 は対ごとに素（）またはどの二つも互いに素であるという。一般に、互いに素であるからといって対ごとに素であるとは限らない（例：）。一般の 個の整数についても同様に定義される。以下は、整数 が互いに素であることと同値な条件である。整数の中から任意に選んだ2つの数 と が互いに素である確率を、ナイーブには、以下のように求めることができる。各 に対して、これらの試行は独立だから、求める確率は、ここで、 はリーマンのゼータ関数を表す。の値はレオンハルト・オイラーによって求められた。一般に、任意に選んだ 個の整数が互いに素である確率は で表される。

出典:wikipedia