【基本】互いに素

ここでは、「互いに素」な2つの整数について見ていきます。

互いに素

2つの整数 $a,b$ の最大公約数が $1$ であるとき、 $a,b$ は互いに素(coprime) である、といいます。例えば、 $9$ と $14$ は互いに素です。また、 $5$ と $15$ は、最大公約数が $1$ ではないため、互いに素ではありません。なお、「素」とついていますが、素数とは関係ありません。

一般的に、互いに素かどうかをチェックするには、最大公約数を調べることになります。

互いに素となる例

「互いに素」となる数字の組合せの例は、たくさん作れます。

例えば、 $a$ を整数とすると、 $a$, $a+1$ は互いに素になります。具体例でいうと、 $2,3$ とか、 $10,11$ とか、 $99,100$ ですが、たしかに互いに素になっていますね。

なぜそうなるのか、考えてみましょう。 $a,a+1$ の最大公約数を $g$ とおくと、 $a=gm$, $a+1=gn$ を満たす整数 $m,n$ が存在します。2つの式を辺々引けば
\begin{eqnarray} (a+1)-a &=& gn-gm \\[5pt] 1 &=& g(n-m) \\[5pt] \end{eqnarray}となります。ここで、 $g,n-m$ はどちらも整数で、 $g$ は正の整数だから、 $g=1$ となるしかありません。最大公約数が $1$ だから、 $a,a+1$ は互いに素になることがわかります。

他にも、次のような例があります。

(1)は、 $a+b,a$ の最大公約数を $g$ と置いて考えましょう。 $a+b,a$ はどちらも $g$ の倍数なので、どちらも $g\times$ (整数)、という形で書けます。辺々引けば、 $b$ も $g\times$ (整数)、という形で書けることがわかります。もし $g$ が2以上なら、 $a,b$ は2以上の整数で割り切れることになるので、互いに素であることに反してしまいます。よって、 $g=1$ となり、 $a+b,a$ は互いに素になります。

(2)は、この話を逆にするだけです。 $a,b$ の最大公約数を $G$ と置いて考えましょう。 $a,b$ はどちらも $G$ の倍数なので、どちらも $G\times$ (整数)、という形で書けます。辺々足せば、 $a+b$ も $G\times$ (整数)、という形で書けることがわかります。もし $G$ が2以上なら、 $a+b,a$ が互いに素であることに反するので、 $G=1$ となり、 $a,b$ は互いに素になります。

2つの整数が互いに素であれば、和や差ともとの数（どちらでもいい）とは、互いに素であることが示せます。ここで見たような、和や差が最大公約数の倍数になるという考え方は、これからもいろんなところで目にするでしょう。

「互いに素」の性質

互いに素な2つの整数の公倍数に関して、基本的で重要な性質があります。

冒頭の例で挙げた例 $9,14$ について考えてみましょう。これらは互いに素です。最大公約数が1ということですね。また、素因数分解をしたときに、共通の素因数がないとも言えます。

さて、 $k$ が整数で、 $14k$ が $9$ の倍数になっていたとしましょう。このとき、 $k$ はどんな整数になっているでしょうか。

$14k$ が $9=3^2$ の倍数になっているとすると、 $14k$ を素因数分解したときには、素因数 $3$ を含み、その指数は $2$ 以上になっていないといけません。 $14$ は素因数 $3$ を含んでいないので、結局、 $k$ が素因数 $3$ を含むしかなく、しかも、その指数は $2$ 以上となることがわかります。つまり、 $k$ は $9$ の倍数になる、ということです。

一般に、次のことが成り立ちます。

$a,b$ が互いに素なら、共通な素因数はありません。なので、 $ak$ が $b$ の倍数なら、 $b$ に含まれるすべての素因数が $k$ に含まれていて、その指数も $b$ のもの以上になっていないといけません。なので、 $k$ は $b$ の倍数になっていないといけない、ということがわかります。

これは基本的な内容ですが、互いに素な2つの整数が出てきたときに、頻繁に使う性質です。

おわりに

ここでは、「互いに素」という言葉の意味と、互いに素になる例、簡単な場合に「互いに素となることを示す」問題、互いに素な2つの整数の性質を見ました。「互いに素」はすでに知っている人もいるかもしれませんが、今後は文字を使って抽象的な議論をしていくことになるので、徐々に慣れていくようにしましょう。