互いに素な整数に成り立つ重要な定理

【目次】
１．定理の紹介
２．「互いに素」の定義の復習
  ２－１．定義をさかのぼること
  ２－２．定義を理解すること
３．定理の「割り切る」による言い換え
４．定理の証明
  ４－１．証明１　素因数分解の一意性を用いて
  ４－２．証明２　ユークリッドの補題を用いて

定理の紹介

教科書（数研出版、高校数学の教科書、以下同じ。詳しくは、高校数学マスター基本方針：参考にする教科書を参照ください）P.118で紹介されている、以下の互いに素な整数に成り立つ定理を今回は証明します。

【互いに素な整数に成り立つ定理】

\(a\),\(b\),\(k\)は整数とする。
\(a\),\(b\)が互いに素で、\(ak\)が\(b\)の倍数であるならば、\(k\)は\(b\)の倍数である。

この定理は、整数に関する基本的な定理で、様々な定理の証明のポイントとして使われますので、教科書では証明抜きで紹介されていますが、きちんと証明まで理解しておくと良いと思います。

実際、応用問題をあれこれと解く前に、このような基本的な定理に対して疑問をしっかりと持ち、自分できちんと証明することができるようにしておけば、難関大の問題もそれほど苦労せずに解答できるようになるのではないかと思います。

なぜなら、難しい問題ほど、解答のポイントとなる事柄は、このような基本的な定理の証明の中に凝縮されているものだからです。言い換えれば、原理がきちんと理解できているかが、数学の問題のすべてだからです。

このことは、数学以外の学問の多くでも同様にあてはまります。手を動かし反復練習することも大切なことですが、効率よく楽に勉強したければ、最初は大変でも原理を掴み取ってしまうよう心掛けることが大切です。

「互いに素」の定義の復習

定義をさかのぼること

まず、「互いに素」の定義を復習しましょう。教科書では、

整数\(a,b\)が互いに素であるとは、\(a,b\)の最大公約数が1であること

とされています。

では、さらに最大公約数の定義を復習すると、

公約数のうち最大のものを最大公約数という

とされています。

では、さらに公約数の定義を復習すると、

２つ以上の整数に共通な約数を、公約数という

とされています。

では、さらに約数の定義を復習すると、こちらのページ「素因数分解の一意性（算術の基本定理）の証明：自然数、整数、約数、倍数」をご覧ください。

このように、定義というのは、頭の中であれ、それができなければ、手を使ってであれ、前に前に遡ってきちんと確認することが大切です。

そうすると、「互いに素」の定義は、結局は、約数の定義に帰着することが分かります。

定義を理解すること

この約数の定義から、公約数があり、最大公約数があり、互いに素の場合があり得る、ということを確認すれば、「互いに素」の定義を理解したことになります。

それでは、約数の定義から、公約数があり、最大公約数があり、互いに素の場合があり得る、ということを確認してみましょう。

そのためにはまず、「素因数分解の一意性（算術の基本定理）の証明：補題２　約数の一意性の証明」をご覧ください。

そうすると、上記【補題２　約数の一意性の証明】より、すべての整数の約数は一通りに決まっているので、２つ以上の整数に共通な約数も一通りに決まります。つまり、２つ以上の整数の公約数は一通りに決まります。

２つ以上の整数の公約数は一通りに決まるので、その中で最も大きな整数も決まります。それが最大公約数となるわけです。

そして、その２つ以上の整数の中で、一つに定まる最大公約数が\(１\)の場合に、それらの整数を互いに素と呼ぶというのです。

ただ、通常は「互いに素」という言葉は、「互いに素」の定義にあるように二つの整数の間に用いる言葉なので、三つ以上の整数の条件として用いる場合には、より具体的な言葉の説明をするべきでしょう。

このような理解が深まれば、次のような「互いに素」の別の定義の仕方も思い浮かびます。

互いに素な整数とは、\(1\)と\(-1\)以外に公約数を持たない相異なる整数のことである。

なぜなら、約数の定義より、\(1\)と\(-1\)はすべての整数の約数で、それしか公約数を持たなければ、最大公約数は\(1\)となります。

一方、最大公約数が\(1\)であるならば、仮に\(1\)と\(-1\)以外に公約数\(n\)を持てば、必ず\(|n|\gt 1\)が成り立ちます。そのため、\(1\)よりも大きな公約数が存在して、最大公約数が\(1\)となることと矛盾します。したがって、\(1\)と\(-1\)以外に公約数を持ちません。

あるいは、互いに素な整数とは、\(1\)以外に正の公約数を持たない相異なる整数のことである、の方がすっきりしているかもしれません。

定理の「割り切る」による言い換え

次に、教科書の【互いに素な整数に成り立つ定理】は、次のように言い換えることもできます。

\(a\),\(b\),\(k\)は整数とする。
\(a\),\(b\)が互いに素で、\(ak\)が\(b\)で割り切れるならば、\(k\)は\(b\)で割り切れる。

まず、「互いに素」という条件から、\(a\)も\(b\)も前提として\(0\)にはなれません。

なぜなら、これも約数の定義より、\(0\)の約数は、すべての整数なので、任意の整数\(z\)と\(0\)の公約数には、少なくとも\(1\)と\(-1\)以外に\(z\)自身が含まれるので、\(0\)はどの整数とも互いに素になりえないからです。

したがって、\(b\neq 0\)です。そのため、\(ak\)を\(b\)で割ることができ、それが割り切れるので余りは\(0\)になります。

つまり、ある整数\(l\)があって、\(ak=bl\)と表すことができます。

したがって、倍数の定義より、\(ak\)は\(b\)の倍数となります。

これは、\(k\)についても同様です。

逆の主張、「倍数\(\ \Rightarrow\ \)割り切れる」については、次のページを「素因数分解の一意性（算術の基本定理）の証明：定義　割り切るとは」をご覧ください。

ちなみに、約数と倍数の定義により「\(b\)が\(ak\)の約数であること」、と「\(ak\)は\(b\)の倍数であること」が同値であることも注意してください。

定理の証明

それでは、説明が長くなりましたが、以下に証明を二つ紹介したいと思います。

【互いに素な整数に成り立つ定理】

\(a\),\(b\),\(k\)は整数とする。
\(a\),\(b\)が互いに素で、\(ak\)が\(b\)の倍数であるならば、\(k\)は\(b\)の倍数である。

証明１　素因数分解の一意性（算術の基本定理）を用いて

【証明１　素因数分解の一意性（算術の基本定理）を用いて】
まず、\(a\),\(b\),\(k\)をきちんと場合分けして考えましょう。

前述のとおり、\(0\)はどの整数とも互いに素になりえないので、前提として、\(a\)と\(b\)は\(0\)ではないことが分かります。

\(a\)が\(1\)の場合には、\(ak=k\)となるので、\(k\)は\(b\)の倍数であることが分かります。

\(a\)が\(-1\)の場合には、\(ak=-k\)となるので、\(-k\)は\(b\)の倍数であり、\(b\)の倍数は正負を入れ替えてもやはり倍数なので、\(k\)が\(b\)の倍数であることが分かります。

\(b\)が\(1\)の場合には、すべての整数は\(1\)の倍数なので、\(k\)は\(b\)の倍数であることが分かります。

\(b\)が\(-1\)の場合には、\(-1\)の倍数は\(1\)の倍数と等しいので、\(k\)は\(b\)の倍数であることが分かります。

\(k\)が\(0\)の場合には、\(0\)はすべての整数の倍数なので、\(k\)は\(b\)の倍数であることが分かります。

\(k\)が\(1\)の場合には、\(a\)が\(b\)の倍数でなければなりませんが、そのとき\(a\)と\(b\)の最大公約数は\(|b|\)となり、\(a\)と\(b\)は互いに素なので、\(|b|=1\)となります。

したがって、\(b\)が\(1\)又は\(-1\)の場合のみを考えればよく、上記より、\(k\)は\(b\)の倍数であることが分かります。

\(k\)が\(-1\)の場合には、まず、\(a\)と\(-a\)はともに同じ\(0\)以外の整数を範囲とするので、上記「\(k\)が\(1\)の場合」は\(a\)を\(-a\)としても成り立つことが分かります。

そこで上記「\(k\)が\(1\)の場合」に「\(a\)を\(-a\)」とすると、\(1\cdot -a=-1\cdot a\)であり、\(1\)が\(b\)の倍数であれば、\(-1\)も\(b\)の倍数なので、\(-1\)を改めて\(k\)と取り直せば、\(k\)が\(-1\)の場合も成り立つことが分かります。

したがって、後は\(|a|,|b|,|k|\ge 2\)を示せばよいことになります。

\(2\)以上の合成数は、一意に素因数分解することができるので、\(|a|\)を素因数分解した積に含まれる素数の組合せは一通りに定まります。

参照：「素因数分解の一意性（算術の基本定理）の証明」

ただし、ここでは、\(|a|\)が素数の場合は、\(|a|\)それ自体を一意に定まった素数の組合せとみなします。

そこで、\(a\)を素因数分解してできる、符号付の素数の組合せの積を\(A\)とします。

同様に、\(k\)を素因数分解してできる、符号付の素数の組合せの積を\(K\)とします。

すると、\(ak\)を素因数分解すると、やはり、一通りに定まった符号付の素数の組合せの積になりますが、

\(ak=AK\)なので、その一意の素因数分解は、\(AK\)であることが分かりました。

一方、\(ak\)は\(b\)の倍数なので、ある整数\(l\)があって、\(ak=bl\)が成り立ちます。

すると、\(bl\)を素因数分解すると、やはり、一通りに定まった符号付の素数の組合せの積になるので、

\(bl=ak=AK\)より、その一意の素因数分解は、同じく\(AK\)であることが分かります。

ここで、\(b\)を素因数分解してできる、符号付の素数の組合せの積を\(B\)、

\(l\)を素因数分解してできる、符号付の素数の組合せの積を\(L\)とします。

ただし、\(l\)が\(1\)又は\(-1\)の場合には、\(L=l\)とします。

すると、\(bl\)の素因数分解も、一通りに定まった素数の組合せの積になるので、\(BL=bl=ak=AK\)より、\(AK\)と\(BL\)が素数の組合せとして等しいことが分かります。

ここで、\(B\)に含まれる任意の素数を\(p\)とします。

\(p\)が\(A\)にも含まれるとすると、\(p\)は\(a\)と\(b\)の\(1\)ではない最大公約数となり、互いに素であることに反します。

したがって、\(p\)は\(A\)に含まれません。

しかし、\(AK\)と\(BL\)は、素数の組合せとして等しいので、\(p\)は\(AK\)には含まれる必要があります。

したがって、\(p\)は\(K\)に含まれています。

つまり、\(B\)に含まれるすべての素数\(p\)は、\(K\)に含まれるので、ある整数\(l^{‘}\)があって、\(K=Bl^{‘}\)と表すことができます。

したがって、\(k=bl^{‘}\)であり、\(k\)が\(b\)の倍数であることが示されました。□

証明２　ユークリッドの補題を用いて

【証明２　ユークリッドの補題を用いて】
素因数分解の一意性を用いると、素数の組合せという考え方が必要になったり、少しややこしくなってしまいます。

同じような証明ですが、直接、ユークリッドの補題（参照：素因数分解の一意性（算術の基本定理）の証明－補題３　ユークリッドの補題の証明）を用いた方が、多少、分かりやすくなるかと思います。

【証明１　素因数分解の一意性（算術の基本定理）を用いて】で確認した細かな論拠は、繰り返しになるので省いて証明したいと思います。もしも、議論が追えない場合には、【証明１】がヒントになるだろうと思いますので、読み返してみてください。

まず、\(|a|,|b|,|k|\lt 2\)の場合は、【証明１】と同じとして、\(|a|,|b|,|k|\ge 2\)の場合についてのみ考えたいと思います。

合成数は、素因数分解することができるので（参照：素因数分解の一意性（算術の基本定理）の証明－素因数分解の存在の証明）、\(|b|\)が合成数ならば素因数分解ができます。

そこで、\(b\)が含む任意の素数\(p\)について、\(ak\)は\(b\)の倍数なので、\(p\)は\(ak\)を割り切ります。

したがって、ユークリッドの補題より、\(p\)は\(a\)又は\(k\)を割り切りますが、\(a\)を割り切るとすると、\(p\)は\(a\)と\(b\)の公約数となり、\(a\)と\(b\)が互いに素であることに矛盾します。

したがって、\(p\)は\(k\)を割り切ります。

つまり、\(b\)に含まれるすべての素数\(p\)は、\(k\)を割り切るので、\(k\)が\(b\)の倍数であることが示されました。□

そもそも、どのような条件の下で、整数の積の全体が割り切れるときに、その積を構成する整数も割り切れるのか、という問題意識は、ユークリッドの補題と共通する点があります。

ある条件の下で全体の性質が部分にも適用できる、という事実は、たしかにとても強力な条件となるので、重要性が高いのだろうと思います。

実際、様々な問題を解く場面で、この定理は用いられます。

公開日：２０１９年７月１１日
修正日：ー