互いに素とは? 背理法を使った証明の例題・合同式との関係も合わせて解説

この記事では、「互いに素」について解説します。
背理法を用いた証明と合同式との関係についても説明していますから、この機会に背理法や合同式についても理解しておきましょう。
互いに素は整数の分野で非常に重要な考え方ですので、この記事でマスターしてください。

1. 互いに素とは?

最初に2つの整数をm, nとしておきます (m≠n)。
m, nそれぞれの約数のうち共通するものが公約数です。
仮にm＝2, n＝4としましょう。
このときmの約数は1, 2で、nの約数は1, 2, 4ですから、公約数は1, 2の2つです。
これら2つのうち最大である2が最大公約数です。
ここまでが前提となる基本知識です。

次にm=2, n=3としましょう。
このとき公約数は1のみです。
したがって、最大公約数は1です。
このように最大公約数が1であることを「互いに素である」といいます。
つまり、「互いに素である」を言い換えると、「共通する素因数をもたない」となります(素因数とは、素数である約数のことです)。
この「共通する素因数をもたない」というのもポイントですので覚えておきましょう。

互いに素という言葉から、2つの整数がともに素数であると勘違いをする人もいるかもしれませんが、あくまでも2つの整数の公約数が1のみであるという意味です。
2つの整数がともに素数であれば必ず互いに素となりますが、互いに素だからといって2つの整数がともに素数であるとは限りません
(「2つの異なる整数がともに素数である」は「2つの異なる整数が互いに素である」の十分条件だが必要条件ではない)。
たとえば、8と15も互いに素です。
なお、1はすべての整数に対して互いに素となります。

2. 背理法を使って互いに素を証明しよう: 例題と解説

互いに素を証明する時に大切なのが、背理法と呼ばれる手法です。
背理法とは、命題Aを証明するとき、仮にAが偽だと前提したうえで話を進め、そこから矛盾が生じることを示して、間接的にAを証明する手法のことです。

では、実際に背理法を用いて例題を解いてみましょう。
例題:
nとn+1が互いに素であることを証明せよ (nは整数)。

解答:
(証明)
nとn+1が互いに素ではないと仮定する。
このとき、nとn+1に共通する素因数をdとすると、整数a, bを用いて

n＝ad, n+1＝bd

よって、

ad+1＝bd
d(b－a)＝1

このとき、dは仮定より素数であるから、

0<b-a=1/d<1

しかるに、仮定よりa, bは整数であるから、b-aは整数であり、矛盾が生じる。
したがって、nとn+1は互いに素である。
(証明終了)

3. 合同式と互いに素

合同式は、一般的な高校の教科書では発展型として紹介されるくらいで、あまり詳しくは習いません。
センタ－試験にも出題されることはありませんが、実は難関大学の入試では合同式を知らないと解きづらい問題が出題されることがあります。
合同式について詳しくはこちらの記事をご覧ください:
合同式の問題の解き方・合同式の性質の証明

合同式とは、簡単にいえば、2つの整数を同じ整数で割ったときの余りについて考えるための道具です。
例えば、4を3で割った余りは1で、7を3で割った余りも1です。
これを合同式を用いて表すと、4≡7 (mod 3) となり、「4と7は3を法として合同である」と読みます。

さて、合同式を用いた除法を考えるとき、互いに素が関係するのです。
結論からいうと、合同式の除法において、両辺を同じ整数mで割ることができるのは、mと法nが互いに素であるときだけです
(加法・減法・乗法についてはこのような制限はありません。詳しくは上述したリンク先の記事をご覧ください)。

では、例として21≡30 (mod 9)を考えてみましょう。
これを両辺ともに3で割ると、7≡10 (mod 9)となり正しくありません。
以下でなぜこのようになるのかを考えてみましょう。

まず、整数a, b, m, n (mとnは互いに素)を用いて

ma≡mb (mod n)

とします。
よって

m(a-b)≡0 (mod n)

これは、「m(a-b)はnで割り切れる」ということを意味します。
ここで、mとnは互いに素であると前提していましたから、m(a-b)がnで割り切れるということは、a-bがnの倍数であるということです。
すなわち、

a-b≡0 (mod n)
a≡b (mod n)

以上より、mとnが互いに素であるとき、ma≡mb (mod n)からa≡b (mod n)が導かれます。

しかし、mとnが互いに素でないときは、この論理は成立しません。
なぜなら、m(a-b)≡0 (mod n)からa-b≡0 (mod n)が導かれないからです。
例えば、m=2, n=6のとき、2(a-b)≡0 (mod 6)から導かれるのは、(a-b)≡0 (mod 3)です。

このように、合同式において両辺を同じ整数で割ることができるのは、その整数と法が互いに素であるときのみだと示されました。

では、例えば3x≡6 (mod 9) (xは整数)という合同式をどう変形すればいいのでしょうか？
この場合、両辺を3で割りたくなりますが、3と9は互いに素ではないのでその変形は誤りになります。
このときは、3x-6≡0 (mod 9)と変形します。
これより、

3(x-2)≡0 (mod 9)
x-2≡0 (mod 3)
x≡2 (mod 3)

のように変形できます。

4. 互いに素の実用: 工業製品

数学が苦手な人の中には、数学のなかで社会に出てから役に立つのは四則演算ぐらいだと思っている人もいるかもしれません。
しかし、今回解説した互いに素という考え方は実は現代工業において欠かせないものです。

どこで使われているのかというと、歯車です。
歯車は様々な工業製品に使われていて、特に時計やタイミング機構には不可欠な存在です。
歯車の歯数の組み合わせは自由ですが、大きな力を伝達するときなどに、互いに素の歯数の組み合わせが用いられます。
いつも同じ歯が当たるようになっていると、一部分が摩耗しやすくなるなど、大きな障害が発生してしまいますが、互いに素である歯車を組み合わせれば、全体が均一に摩耗していくため、長持ちします。また、歯のあたりがなめらかになるというメリットもあるのです。
結果、ほとんどの工業製品では、互いに素である歯車が用いられています。
身近なものでこうした数学的な要素が使われているのを知ると、勉強をするときにも親しみがわくのではないでしょうか。

互いに素のまとめ

以上、互いに素とはどのような状態であるかを解説しました。
整数問題ではとても重要な考え方ですから、理解を深めておいて損はありません。
合わせて背理法を用いた証明についてもやり方をマスターしておいてください。

なお、互いに素はユークリッド互除法に関係してきます。詳しくはこちらの記事をご覧ください:
ユークリッド互除法と2元1次不定方程式