互いに素 (整数論)
互いに素（たがいにそ、英: coprime）は、2つの整数が1と-1以外に共通の約数を持たない場合の2数の関係である。これは2つの整数の最大公約数が1であることと同値である。例えば35と12は共通の素因数を持たず、それゆえ共通の1より大きい約数を持たないので互いに素である。42と18ならば、ともに6を約数に持つので互いに素ではない。1と-1は（0や±1自身を含む）全ての整数と互いに素であり、0は1および-1とのみ互いに素である。一般に、相異なる素数どうしは互いに素である。連続する2つの整数は互いに素である。2以上の整数はその（自身を含む）倍数や2以上の約数と互いに素ではない。また3つ以上の整数の間でも互いに素の関係は同様に定義できる。 ある整数 a と b が互いに素であることを a b と表すこともある。
2数が互いに素であるかどうか、すなわち最大公約数がいくらであるかを調べる最良のアルゴリズムとしてユークリッドの互除法がある。これによって素因数分解によらずに最大公約数が求まり、互いに素であるかどうかを知ることができる。
互いに素である数の性質
整数a,bが互いに素であれば ax+by=1 を満たす整数x,yが存在する。またaとb1が互いに素で、aとb2も互いに素であればaとb1b2は互いに素である。
aとbが互いに素であることと 2a-1 と2b-1 が互いに素であることは同値である。
「aとbが互いに素であるなら同じ素数を共通の約数にはもたない」ということを利用して、任意に選んだaとbが互いに素である確率を以下のように求めることができる。まず、ある素数pで任意に選んだ整数が割り切れる確率は 1/p となる。したがってaとbのうち少なくとも一つがpで割り切れない確率（同じ素数pを共通の約数にもたない確率）は 1-(aがpで割り切れる確率 × bがpで割り切れる確率)=1-1/p2 となる。さらに全ての素数に関してこの確率の総乗をとった次式がaとbが互いに素である確率である。
ζはゼータ関数を表す。ζ(2)の値はレオンハルト・オイラーによって求められた。一般にk個の任意に選んだ整数が互いに素である確率は 1/ζ(k) で表される。
