互いに素とは?意味や証明問題をわかりやすく解説!

この記事では、「互いに素」の意味をわかりやすく解説していきます。

性質の証明や、互いに素であることを利用する問題も説明していきますので、ぜひこの記事を通してマスターしてくださいね。

 

互いに素とは?

互いに素とは、\(2\) つの整数 \(a, b\) の最大公約数が \(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\) である場合を「互いに素」といいます。

 

補足

「互いの素」という性質が身近に使われている例として、多くの工業製品に組み込まれている歯車があります。

互いの素な歯車をかみ合わせることで、全体が均一に摩耗し、結果的に長持ちします。

もし互いに素でない歯車を使用すると、頻繁に同じ歯同士が当たって部分的に壊れやすくなってしまうのです。

 

整数を扱う問題では、「互いに素」という性質は非常に強い条件として使えます。

それでは、「互いに素」な整数の性質や問題の解き方を見ていきましょう。

 

互いに素な整数の性質

ここでは、互いに素な整数の性質を紹介します。

互いに素な整数同士では、常に以下のことがいえます。

Tips

互いに素な整数 \(a, b\) の最大公約数は \(1\)

\(\iff \color{red}{a, b}\) には素数の公約数(= 共通の素因数)が存在しない

素数とは、\(1\) とその数自身以外に正の約数をもたない自然数でしたね(\(2, 3, 5, \cdots\) など)。

特に「ある \(2\) つの数が互いに素であること」を証明するときには、「素数の公約数」というキーワードが大活躍します。

必ず頭に入れておきましょう。

 

また、\(2\) つの数が互いに素であることがわかっている場合、次の性質を使うことができます。

互いに素な数の性質

\(a, b, k\) は整数、\(m, n, p, q\) は自然数とする。

  1. \(a, b\) が互いに素かつ \(ak\) が \(b\) の倍数ならば、 \(k\) は \(b\) の倍数である。
  2. \(a^m, b^n\) が互いに素ならば、\(a, b\) は互いに素である。
  3. \(m, n\) が互いに素かつ \(p, q\) が互いに素のとき、
    \(\displaystyle \frac{n}{m} = \frac{q}{p}\) ならば \(m = p, n = q\)

互いに素な \(2\) つの数が共通の素因数をもたないことを考えると、どれも成り立つことがわかります。

 

互いに素の証明問題

ある \(2\) つの数が互いに素であることを証明する問題はよく問われます。

特に有名なのは次の \(3\) つです。

互いに素になる数の例
  1. 隣り合う \(2\) つの整数 \(n, n + 1\) は互いに素である
  2. \(2\) つの自然数 \(m, n\) が互いに素であるならば、\(n, m − n\) は互いに素である
  3. \(2\) つの自然数 \(m, n\) が互いに素であるならば、\(m + n, mn\) は互いに素である

 

これらは、それぞれ「背理法」によって証明できます。

背理法
ある命題が成り立たないと仮定すると矛盾が生じることを示す証明方法。

背理法とは?証明のやり方を例題でわかりやすく解説

 

実際に証明を確認しましょう。

証明I「隣り合う 2 つの整数」

証明I

隣り合う \(2\) つの整数 \(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「 n と m − n(m, n は互いに素な自然数)」

証明II

\(2\) つの自然数 \(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 と mn(m, n は互いに素な自然数)」

証明III

\(2\) つの自然数 \(m, n\) が互いに素であるならば、\(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\) が互いに素であることを利用して、不定方程式の整数解を求めることがあります。

不定方程式

方程式の数よりも未知数の数が多く、解が無数に存在する方程式。

そのうち、未知数が \(2\) 種類で次数が \(1\) のものを「二元一次不定方程式」という。

\(ax + by = c\) (\(a, b, c\) は係数)

互いに素な性質を利用して「不定方程式」を解く問題については、以下の記事で詳しく説明しています。

不定方程式とは?問題の解き方を種類別にわかりやすく解説!

 

利用問題②「合同式の商」

合同式をある数 \(a\) で割ってもよいのは、法 \(n\) と \(a\) が互いに素である場合に限られます。

合同式の商

\(a\) と \(n\) が互いに素のとき、

\begin{align}\color{red}{ab \equiv ac \pmod{n} \iff b \equiv c \pmod{n}}\end{align}

(見切れる場合は横へスクロール)

合同式

余りが等しいことを示す等式。

互いに素な性質を利用した「合同式」の問題については、以下の記事で詳しく説明しています。

合同式(mod)とは?性質の証明や計算問題の解き方

 

以上で解説は終わりです。

整数問題において、「互いに素」という条件は非常に強力です。

「互いに素」の意味や性質を理解して、いろいろな問題に活用できるようになりましょう!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です