初等整数論では、2つの整数が共通の正の約数として1より大きいものを持たないとき、それらを互いに素または比較的素（relatively prime）と呼びます。形式的には、整数 a と b が互いに素であるとは、その最大公約数が 1 に等しいことを意味します。標準的な入門は数学の参考書で確認でき、対象となるのは通常の整数です。よく使われる記法には gcd(a,b)=1、(a,b)=1、あるいは垂直記号に似た a ⟂ b があります。
定義と記法
互いに素であるというのは、共通の素因数が存在しないことを述べる性質です。符号には依存しません。たとえば −8 と 9 は、絶対値どうしが共通の素因数を持たないので互いに素です。gcd(a,b)=1 であれば、分数 a/b は既約分数であり、a は b に関する乗法逆元を持ちます。この条件は純粋に乗法的なもので、どちらかの数自体が素数である必要はありません。
基本的な性質と重要な帰結
- ユークリッドの補題: gcd(a,b)=1 で a が b·c を割り切るなら、a は c を割り切ります。これは素因数分解の一意性を支える基本結果です。
- 剰余逆元: a が b に関する逆元を持つのは、ちょうど gcd(a,b)=1 のときです。この事実は一次合同式を解くうえで中心的です。
- トーシェント関数と数え上げ: オイラーのトーシェント関数 φ(n) は、n 未満で n と互いに素な整数の個数を数えます。
- 計算の簡約: 分数が既約になるのは、分子と分母が互いに素である場合に限られます。
例と図解
簡単な例で考えると、6 と 35 は互いに素です。6=2·3、35=5·7 であり、共通の素数因子を持たないからです。これに対して 6 と 27 は、どちらも 3 で割り切れるため互いに素ではありません。異なる2つの素数は常に互いに素です。一般的な素数の性質を見れば分かるように、ただし同じ素数の倍数どうしは互いに素ではありません。たとえば 4 と 5 は互いに素ですが、10 と 5 は互いに素ではありません。
歴史と発展
共通の約数を持たない数という考え方は古代の算術にさかのぼり、ユークリッドによる最大公約数や素因数分解の研究にも暗黙に現れています。gcd や相互素性という現代的な言い方は、ユークリッドの互除法のような算法とともに発展しました。歴史上の用語は一定ではありませんでしたが、この概念は何千年にもわたって古典的整数論の中心であり、現代の計算分野でも重要です。
応用、拡張、区別
互いに素性は数学と計算機科学の広い範囲に現れます。合同算術、暗号プロトコル（たとえば公開鍵方式で鍵を選ぶ場面）、そして数え上げ問題で特に重要です。考え方は整数に限らず、たとえば多項式や環の元にも拡張できます。その場合は、2つの元が環全体を生成するときに互いに素とみなされます。関連する区別としては、pairwise coprime（集合の異なる任意の2要素が互いに素）と setwise coprime（集合全体の gcd が 1 だが、ある組は共通因子を持つことがある）があります。最大公約数の計算法については、最大公約数とそのアルゴリズムに関する資料が参考になります。