この記事では、「互いに素」の意味をわかりやすく解説していきます。
性質の証明や、互いに素であることを利用する問題も説明していきますので、ぜひこの記事を通してマスターしてくださいね。
目次
互いに素とは？
互いに素とは、\(2\) つの整数の最大公約数が \(1\) であることです。
\(2\) つの整数 \(a, b\) を共に割り切る整数が \(1\) と \(−1\) のみ、すなわち \(a, b\) の最大公約数が \(1\) であるとき、「\(a\) と \(b\) は互いに素である」という。
特に、\(1, −1\) はすべての整数に対して互いに素となる。
整数を扱う問題では、「互いに素」という性質は非常に強い条件として使えます。
互いに素である・互いに素でない例
例えば、次の \(2\) 数 \((a, b)\) が互いに素であるかを見てみましょう。
（例）
- \((3, 5)\)
公約数は \(1\) と \(−1\)
→ 互いに素 - \((28, 41)\)
公約数は \(1\) と \(−1\)
→ 互いに素 - \((3, 24)\)
公約数は \(−3, −1, 1, 3\)
→ 互いに素ではない
このとき、互いに素である \(2\) つの整数が素数であるとは限りません。
あくまでも、公約数（共通する約数）のうち一番大きい数が \(1\) である場合を「互いに素」といいます。
「互いの素」という性質が身近に使われている例として、多くの工業製品に組み込まれている歯車があります。
互いの素な歯車をかみ合わせることで、全体が均一に摩耗し、結果的に長持ちします。
もし互いに素でない歯車を使用すると、頻繁に同じ歯同士が当たって部分的に壊れやすくなってしまうのです。
互いに素 = 素数の公約数を持たない
互いに素な整数同士では、常に以下のことがいえます。
互いに素な整数 \(a, b\) の最大公約数は \(1\)
\(\iff \color{red}{a, b}\) には素数の公約数（= 共通の素因数）が存在しない
素数とは、\(1\) とその数自身以外に正の約数をもたない自然数でしたね（\(2, 3, 5, \cdots\) など）。
特に「ある \(2\) つの数が互いに素であること」を証明するときには、「素数の公約数」というキーワードが大活躍します。
必ず頭に入れておきましょう。
互いに素な整数の性質
\(2\) つの数が互いに素であることがわかっている場合、次の性質を使うことができます。
\(a, b, k\) は整数、\(m, n, p, q\) は自然数とする。
- \(a, b\) が互いに素かつ \(ak\) が \(b\) の倍数ならば、 \(k\) は \(b\) の倍数である。
- \(a^m, b^n\) が互いに素ならば、\(a, b\) は互いに素である。
- \(m, n\) が互いに素かつ \(p, q\) が互いに素のとき、
\(\displaystyle \frac{n}{m} = \frac{q}{p}\) ならば \(m = p, n = q\)
互いに素な \(2\) つの数が共通の素因数をもたないことを考えると、どれも成り立つことがわかります。
互いに素の証明問題
ある \(2\) つの数が互いに素であることを証明する問題はよく問われます。
特に有名な次の \(3\) つの証明問題の解き方を順番に説明していきます。
- 隣り合う \(2\) つの整数 \(n, n + 1\) は互いに素である
- \(2\) つの自然数 \(m, n\) が互いに素であるならば、\(n, m − n\) は互いに素である
- \(2\) つの自然数 \(m, n\) が互いに素であるならば、\(m + n, mn\) は互いに素である
これらはそれぞれ、「背理法」によって証明できます。
背理法とは、ある命題が成り立たないと仮定すると矛盾が生じることを示す証明方法です。
背理法とは？証明のやり方を例題でわかりやすく解説
証明I「n, n + 1 が互いに素」
隣り合う \(2\) つの整数 \(n, n + 1\) は互いに素であることを示せ。
\(n, n + 1\) が互いに素でないと仮定すると矛盾が生じることを示します。
「\(n\) と \(n + 1\) が互いに素でない」と仮定する。
このとき、\(n\) と \(n + 1\) の両方を割り切る \(2\) 以上の整数 \(d\) が存在し、
\(n = da\) …①, \(n + 1 = db\) …② （\(a, b\) は整数）
とおける。
ここで、② − ①より
\((n + 1) − n = db − da\)
すなわち
\(d(b − a) = 1\)
\(b − a\) は整数であるから、
\(d = \pm 1\)
これは、\(d \geq 2\) に矛盾する。
したがって \(n\) と \(n + 1\) は互いに素である。
（証明終わり）
証明II「m, n が互いに素 \(\iff\) n, m − n が互いに素」
\(2\) つの自然数 \(m, n\) が互いに素であるならば、\(n, m − n\) は互いに素であることを示せ。
\(n, m − n\) が互いに素ではない、つまり、素数の公約数をもつと仮定し、矛盾を導きます。
「\(n, m − n\) が互いに素ではない \(\iff\) 素数の公約数 \(p\) をもつ」と仮定する。
このとき、整数 \(a, b\) を用いて
\(n = pa\) …①
\(m − n = pb\) …②
とおける。
① + ②より
\(m = p(a + b)\) …③
①、③より、\(m\) と \(n\) は素数の公約数 \(p\) をもつ。
これは、\(m, n\) が互いに素であることと矛盾する。
したがって、整数 \(m, n\) が互いに素であるならば、\(n, m − n\) は互いに素である。
（証明終わり）
証明III「m, n が互いに素 \(\iff\) m + n, mn が互いに素」
\(2\) つの自然数 \(m, n\) が互いに素であるならば、\(m + n, mn\) は互いに素であることを示せ。
\(m + n, mn\) が互いに素ではない、つまり、素数の公約数をもつと仮定し、矛盾を導きます。
「\(m + n, mn\) が互いに素ではない \(\iff\) 素数の公約数 \(p\) をもつ」と仮定する。
このとき、整数 \(a, b\) を用いて
\(m + n = pa\) …①
\(mn = pb\) …②
とおける。
②から、\(m\) または \(n\) は \(p\) の倍数である。
\(m\) が \(p\) の倍数のとき、\(m = pk\) (\(k\) は整数) とおくと、
①より
\(n = pa − m = pa − pk = p(a − k)\)
\(a − k\) は整数であるから、\(n\) も \(p\) の倍数である。
これは、\(m, n\) が互いに素であることと矛盾する。
また、\(n\) が \(p\) の倍数のときも同様に \(m\) が \(p\) の倍数と示せ、矛盾する。
したがって、\(m, n\) が互いに素であるならば、\(m + n, mn\) は互いに素である。
（証明終わり）
ここで示した以外にも、互いに素であることを示す証明問題はいくらでもあります。
基本的な方針はほとんど同じなので、あとは問題特有の条件をうまく数式で表すことを意識しましょう！
互いに素の利用問題
ここでは、互いに素である整数を利用して解ける問題について説明します。
利用問題①「二元一次不定方程式」
二元一次不定方程式には、以下の重要な定理が存在します。
\(a, b\) が互いに素である \(\iff\) \(ax + by = 1\) が整数解をもつ
係数 \(a, b\) が互いに素であることを利用して、二元一次不定方程式の整数解を求められるケースが多くあります。
詳しくは、以下の記事で詳しく説明しています。
不定方程式とは？問題の解き方を種類別にわかりやすく解説！
利用問題②「合同式の商」
合同式をある数 \(a\) で割ってもよいのは、法 \(n\) と \(a\) が互いに素である場合に限られます。
\(a\) と \(n\) が互いに素のとき、
\begin{align}\color{red}{ab \equiv ac \pmod{n} \iff b \equiv c \pmod{n}}\end{align}
（見切れる場合は横へスクロール）
合同式
余りが等しいことを示す等式。
詳しくは、以下の記事で詳しく説明しています。
合同式（mod）とは？性質の証明や計算問題の解き方
以上で解説は終わりです。
整数問題において、「互いに素」という条件は非常に強力です。
「互いに素」の意味や性質を理解して、いろいろな問題に活用できるようになりましょう！