「互いに素 (整数論)」の版間の差分

{{Otheruses|2二つの整数の関係|集合|素集合}}

'''互いに素'''（たがいにそ、{{lang-en-short|coprime}}）は、2二つの[[整数]]が [[1]] と [[-1]] 以外に共通の[[約数]]を持たない場合の2二数の関係である。これは2二つの整数の[[最大公約数]]が 1 であることと[[同値]]である。</br>
例えば 35 と 12 は共通の[[素因数]]を持たず、それゆえ共通の 1 より大きい約数を持たないので互いに素である。42 と 18ならば、 はともに 6 を約数に持つので互いに素ではない。1 と -1 は（[[0]]や ±1 自身を含む）全ての整数と互いに素であり、0 は 1 および -1 とのみ互いに素である。一般に、相異なる[[素数]]どうしは互いに素である。り、連続する2つの整数はも互いに素である。2 以上の整数はその（自身を含む）[[倍数]]や 2 以上の約数と互いに素ではない。また3三つ以上の整数の間でも互いに素の関係は同様に定義できる。例えば 25 と 18 と 15 は互いに素である。「25 と 15」や「18 と 15」は互いに素ではないが、三数に共通する正の約数が 1 のみであるならば、三数は互いに素という。

2二数が互いに素であるかどうか、すなわちを知るために二数の最大公約数がいくらであるかを調べる最良の[[アルゴリズム]]として[[ユークリッドの互除法]]がある。これによって[[素因数分解]]によらずに最大公約数が求まり、それが 1 であれば互いに素、2 以上ならば互いに素であるかどうかを知るはないことができ分かる。