複数の整数の最大公約数と最小公倍数について

【目次】
１．複数の整数の最大公約数と最小公倍数を考える意義
２．基本用語の復習
  ２－１．約数と倍数の復習
  ２－２．公約数と公倍数の復習
  ２－３．最大公約数と最小公倍数の復習
３．最大公約数と最小公倍数の存在の一意性
  ３－１．定理１：複数の整数の最大公約数と最小公倍数の存在
  ３－２．複数の整数の最大公約数と最小公倍数の面白さ
４．公約数と最大公約数の約数の一致（公倍数も同様）
  ４－１．補題２－１：二つの整数の公約数と最大公約数の約数
  ４－２．補題２－２：二つの整数の公倍数と最小公倍数の倍数
  ４－３．定理３－１：複数の整数の公約数と最大公約数の約数
  ４－４．定理３－２：複数の整数の公倍数と最小公倍数の倍数
５．最大公約数の最大公約数、最小公倍数の最小公倍数
  ５－１．系４－１：最大公約数の最大公約数
  ５－２．系４－２：最小公倍数の最小公倍数
  ５－３．定理５－１：複数の最大公約数の最大公約数
  ５－４．定理５－２：複数の最小公倍数の最小公倍数
６．複数の整数の最大公約数や最小公倍数を求める方法

複数の整数の最大公約数と最小公倍数を考える意義

複数の整数の最大公約数と最小公倍数をきちんと考えられるようになることで、二つの整数の最大公約数と最小公倍数を考えるだけでは見えてこない、整数における最大公約数と最小公倍数の持つ重要な役割をより深く理解できるのではないかと思います。

そのポイントは、以下の定理３－１と定理３－２で示すように、「公約数の集合と最大公約数の約数の集合が一致する」、「公倍数の集合と最小公倍数の倍数の集合が一致する」という最大公約数と最小公倍数の持つ特徴にあります。

この最大公約数と最小公倍数の持つ特徴によって、整数は、単なる順序を持った要素の集合では持ち合わせていない簡便な法則性を持つことになります。

その簡便な法則性とは、つまり、公約数や公倍数という二つの集合の共通部分を取るために、わざわざ約数や倍数を計算し、その共通要素を照らし合わせて公約数や公倍数を割り出すという必要がなくなります。

その代わりに、最大公約数や最小公倍数を計算するだけで、その約数や倍数を取れば公約数や公倍数を計算することができるのです。

この性質によって、特に複数の整数の場合には、約数や倍数の全体を計算するのではなく、公約数や公倍数の最大値や最小値、つまり最大公約数や最小公倍数だけを次々に計算して、複数の整数全体の最大公約数や最小公倍数を計算すれば、最後にその約数や倍数から全体の公約数や公倍数を割り出すことができることになります。

そして、その最大公約数や最小公倍数だけを次々に計算することは、ユークリッドの互除法で効率的にできてしまうわけです。

まずもって、単に数えただけに過ぎない整数に、なぜこのように強力な法則性が生じるのか、とても不思議で興味深い事実です。

くわえて、上記から明らかなように、このような整数の性質は、整数の大きさや個数が増えれば増えるほど、計算の手間が省けるという実際的な効力も持ち、理論的にも数学の様々な場面で大きな役割を果たしています。

教科書（数研出版、高校数学の教科書、以下同じ。詳しくは、高校数学マスター基本方針：参考にする教科書を参照ください）でも、最大公約数と最小公倍数は、複数の整数に対して定義され、以下で証明する定理３－１と定理３－２も紹介されています。

しかしながら、きちんとした証明や解説は省かれ、主に二つの整数の最大公約数と最小公倍数についてだけしか解説されていないので、このページでは、その複数の整数の最大公約数と最小公倍数についてのきちんとした証明や解説を行いたいと思います。

証明や解説が長くなるので、あらかじめこのページの最終目標をきちんと書いておくと、最終目標は、複数の整数の最大公約数や最小公倍数を求めるためには、それらの公約数や公倍数を求める必要はなく、最大公約数の最大公約数や最小公倍数の最小公倍数を次々に計算して行くだけで済む、ということを証明することにしたいと思います。

基本用語の復習

約数と倍数の復習

とにかく、まずは、約数と倍数の復習から始めましょう。
教科書より、約数と倍数の定義を引用すると、

約数、倍数とは、２つの整数\(a,b\)について、ある整数\(k\)を用いて、\[a=bk\]と表されるとき、\(b\)は\(a\)の約数であるといい、\(a\)は\(b\)の倍数であるという。

となります。

ここでは、約数と倍数の具体例をいくつか確認しておきましょう。

\(0\)の約数：　\(\cdots\ ,-5,-4,-3,-2,-1,0,1,2,3,4,5,\ \cdots\)
\(0\)の倍数：　\(0\)

\(1,-1\)の約数：　\(-1,1\)
\(1,-1\)の倍数：　\(\cdots\ ,-5,-4,-3,-2,-1,0,1,2,3,4,5,\ \cdots\)

\(2,-2\)の約数：　\(-2,-1,1,2\)
\(2,-2\)の倍数：　\(\cdots\ ,-10,-8,-6,-4,-2,0,2,4,6,8,10,\ \cdots\)

\(3,-3\)の約数：　\(-3,-1,1,3\)
\(3,-3\)の倍数：　\(\cdots\ ,-15,-12,-9,-6,-3,0,3,6,9,12,15,\ \cdots\)

\(4,-4\)の約数：　\(-4,-2,-1,1,2,4\)
\(4,-4\)の倍数：　\(\cdots\ ,-20,-16,-12,-8,-4,0,4,8,12,16,20,\ \cdots\)

\(5,-5\)の約数：　\(-5,-1,1,5\)
\(5,-5\)の倍数：　\(\cdots\ ,-25,-20,-15,-10,-5,0,5,10,15,20,25,\ \cdots\)

\(6,-6\)の約数：　\(-6,-3,-2,-1,1,2,3,6\)
\(6,-6\)の倍数：　\(\cdots\ ,-30,-24,-18,-12,-6,0,6,12,18,24,30,\ \cdots\)

以降の文章は、上記の具体例を思い浮かべながら読むと理解がしやすいと思います。

約数と倍数の定義については、こちら「素因数分解の一意性（算術の基本定理）の証明：整数に関わる用語の定義：自然数、整数、約数、倍数」も参考にしてみてください。

公約数と公倍数の復習

次は、公約数と公倍数の復習も正確に行っておきましょう。

教科書では、公約数と公倍数の定義は、

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

２つ以上の整数に共通な倍数を、それらの整数の倍数という。

とされています。

たしかに、この公約数と公倍数の定義を見れば分かる通り、公約数と公倍数が定義される対象は、２つ以上の整数となっています。

つまり、教科書においてもこのページで解説される内容が、大まかにでも教室で議論されることを期待しているように思いますが、おそらく、多くの高校生は、このページで解説されるような内容にたどり着く前に、高校生活を終えるのではないでしょうか。

それでは、数学や整数の面白さは感じられないのではないかと思います。

最大公約数と最小公倍数の復習

では、さらに最大公約数と最小公倍数の定義の復習をしたいと思います。

教科書では、最大公約数と最小公倍数の定義は、

最大公約数とは、公約数のうち最大のもの。

最小公倍数とは、公倍数のうち正で最小のもの。

とされています。

公倍数の定義に「正で」という言葉が加えられている理由は、上記で示した倍数の具体例を見て頂ければ分かる通り、整数の範囲で倍数を定義すると、\(0\)や負の倍数が含まれるので、それらを除くために加えられています。

自然数の範囲で倍数を定義する場合には、この「正で」という言葉は必要なくなります。

ちなみに、記法としては、最大公約数(the greatest common divisor)と最小公倍数(the least common multiple)の頭文字を取って、gcdやlcmと略記する場合があります。

整数\(a,b\)の最大公約数や最小公倍数を、\(gcd(a,b)\)や\(lcm(a,b)\)で表すこともあります。

以上で、基本的な用語の復習は終わりにして、教科書では省かれている複数の整数の最大公約数と最小公倍数についてのいくつかの証明を行っていきたいと思います。

最大公約数と最小公倍数の存在の一意性

まずは、その複数の整数に最大公約数と最小公倍数がきちんと定義できることを確認しておきましょう。

つまり、複数の整数の間に、最大公約数と最小公倍数が一意に存在することを証明します。

定理１：　複数の整数の最大公約数と最小公倍数の存在

【定理１：　複数の整数の最大公約数と最小公倍数の存在】
２つ以上の整数の公約数と公倍数の集合は、一意に定まる。
その最大公約数と最小公倍数も、一意に定まる。
とくに、これらは公約数と公倍数を取る順序によらない。

【証明】
まず、約数について考えましょう。

２つ以上の整数のうち、任意の整数\(n\)について、\(n\)の約数の集合\(N\)は一意に定まります。詳しくは、素因数分解の一意性（算術の基本定理）の証明：補題２　約数の一意性の証明をご覧ください。

２つ以上の整数が\(m\)個あったとすると、それらの公約数の集合\(D\)は、それらに共通の約数なので、
\[D\ =\ \bigcap_{ i = 0 }^{m} N_{i}\]
となります。

ただし、ここで\(m\)は有限な数として考えます。

ここで、集合の共通部分を取る演算\(\cap\)は、結合法則を満たすので、つまり、どのように\(( )\)を付けて計算の順序を変えても、計算の結果は等しいので、公約数の集合Dは、公約数を取る順序によらずに一意に定まります。

もう少し、詳しく考えると、公約数の集合\(D\)の任意の公約数\(d\)は、すべての\(i\)について\(N_{i}\)に含まれているので、どのような公約数を取る順序であっても、共通部分に残るはずです。

一方で、ある整数\(d^{‘}\)が、公約数の集合\(D\)に含まれなかったとすると、少なくとも一つの整数\(n^{‘}\)が、初めの\(m\)個ある整数のうちにあって、\(n^{‘}\)の約数の集合\(N^{‘}\)に\(d^{‘}\)は含まれないはずです。

そうすると、どのような公約数を取る順序であっても、\(N^{‘}\)との共通部分を取る際に、\(d^{‘}\)は含まれなくなることが分かります。

つまり、どのような公約数を取る順序であっても、ある整数が、すべての\(i\)について\(N_{i}\)に含まれていれば公約数であり、少なくとも一つの\(i\)について\(N_{i}\)に含まれていなければ公約数ではないわけです。

このことを、すべての\(i\)について、\(N_{i}\)に含まれている約数に対して確認することができるので、公約数の集合\(D\)は一意に定まることが分かります。

公約数の集合\(D\)は一意に定まり、かつ、その要素の数は有限個なので、その最大値となる整数も一意に定まります。したがって、最大公約数も一意に定まります。

倍数については、公倍数が一意に定まることは、公約数の議論とまったく同じです。

最小公倍数については、\(m\)個の整数の集合を\(U\)、\(m\)個の整数の公倍数の集合を\(M\)とすると、\(U\)に\(0\)が入っていなければ、\(0\)ではないある二つの整数\(a,b \in U\)について、少なくとも一つ\(ab \in M\)が公倍数となるので、\(M\)は\(0\)を除いても空集合にはなりません。

したがって、\(M\)について、正の公倍数に限れば\(1\)を下限として最小値、つまり最小公倍数が一意に定まります。

ただし、\(m\)個の整数の集合\(U\)に\(0\)が入る場合には、\(M=\{0\}\)なので最小公倍数は定まりません。□

複数の整数の最大公約数と最小公倍数の面白さ

冒頭でも指摘しましたが、通常、複数の集合の共通部分を取り出すには、各集合を比較してすべての共通部分を割り出していく必要があります。

さらに、要素が順序（大小）を持っている複数の集合の場合であっても、通常は、共通部分の最大の要素のみを取り出していくと、取り出す順序によって、取り出される要素の結果は変わってしまいます。

例えば、\(\{1,2,3\}\)、\(\{1,2,3,4\}\)、\(\{1,2,4\}\)の共通部分の最大値は、\(2\)です。

しかし、\(\{1,2,3\}\)、\(\{1,2,3,4\}\)の共通部分の最大値を先に取ると、\(3\)であり、\(3\)と\(\{1,2,4\}\)の共通部分はなくなってしまいます。

したがって、要素が順序（大小）を持っている複数の集合の場合に、その共通で最大の要素を取り出すには、まず、全体の共通部分を取り出すことが必要になり、その上で、その共通部分の最大の要素を取り出すことになります。

そうすると、最大公約数を取り出すためには、公約数をすべて取り出す必要がありそうです。

そして、公約数の集合を割り出すには、各整数の約数の集合をすべて比較していく必要がありそうです。

しかし、ここから紹介する補題、系、定理により、公約数をすべて取り出す必要はなく、最大公約数のみを取り出していけばよいことが分かります。

さらに、公約数の集合についても、取り出した最大公約数から計算できることが分かります。

このことは、最小公倍数についてもあてはまるのです。

以上の説明から、整数はかなり特殊な性質を持っているのだなあと、感じられましたでしょうか。

公約数と最大公約数の約数の一致（公倍数も同様）

補題２－１：　二つの整数の公約数と最大公約数の約数

【補題２－１：　二つの整数の公約数と最大公約数の約数】
整数\(a,b\)の公約数の集合と、整数\(a,b\)の最大公約数の約数の集合は一致する。

【証明】
整数\(a,b\)の公約数の集合を集合\(D\)、整数\(a,b\)の最大公約数の約数の集合を集合\(G\)とします。

まず、\(D\ \supset\ G\)を証明しましょう。

最大公約数を\(g\)とすると、\(g\)は整数\(a,b\)の公約数の最大値なので、そもそも、整数\(a,b\)の公約数であり、\(g\in D\)が成り立ちます。

\(g\)が整数\(a,b\)の公約数ということは、\(g\)は\(a\)の約数でもあり、\(g\)は\(b\)の約数でもあります。

\(g\)が\(a\)の約数であるということは、定義より、ある整数\(k\)があって、

\[a\ =\ gk \tag{1}\]

が成り立ちます。

ここで、\(g\)の任意の約数、つまり、集合\(G\)の任意の要素を\(g^{‘}(\in G)\)とすると、やはり、約数の定義より、ある整数\(k^{‘}\)があって、

\[g\ =\ g^{‘}k^{‘} \tag{1}\]

となります。

数式（１）に（２）を代入すると、

\[a\ =\ g^{‘}(k^{‘}k) \]

となり、\(k^{‘}k\)は整数なので、\(g^{‘}\)も\(a\)の約数であることが分かります。

\(g\)は\(b\)の約数でもあるので、同様に、\(g^{‘}\)は\(b\)の約数でもあることが分かります。

したがって、\(g^{‘}\)は整数\(a,b\)の公約数であり、\(g^{‘}\in\ D\)が言えました。

次に、\(D\ \subset\ G\)を証明しましょう。

\(D\ \not\subset\ G\)を仮定して、矛盾を導き出しましょう。

\(D\ \not\subset\ G\)であれば、\(D\)のある要素\(d\)が存在して、\(d \notin G\)が成り立ちます。

ここで、約数は正負が対称なので、正の約数\(d,g \gt 0\)だけについて考えれば十分と分かります。

さらに、\(1\)は、すべての整数の約数なので、\(d \notin G\)が成り立つならば\(d \neq 1\)です。

したがって、\(d\ge 2\)なので\(g\ge 2\)でもあり、\(D\)も\(G\)も\(\{-1,1\}\)ではありません。

これと素因数分解の一意性（参考：素因数分解の一意性（算術の基本定理）の証明：定理　素因数分解の一意性の証明）より、\(d\)と\(g\)は、少なくとも一つ以上の素数の一意な積に素因数分解することができます。

そこで、\(d\)を素因数分解した素因数の組合せの積を\(Z_{d}\)、\(g\)を素因数分解した素因数の組合せの積を\(Z_{g}\)とします。

さらに、任意の素因数\(p\)について、\(d\)に含まれる\(p\)の指数を\(p_{d}\)、\(g\)に含まれる\(p\)の指数を\(p_{g}\)とします。

\(Z_{d}\)のすべての素因数\(p\)について、\(Z_{g}\)に\(p\)が\(p_{d}\)個以上含まれる、つまり\(p_{g} \ge p_{d}\)とすると、

ある整数\(l\)があって、

\[Z_{g}=Z_{d}l\]

つまり、

\[g=dl\]

と表すことができるので、\(d\)は\(g\)の約数となり、\(d \notin G\)に矛盾します。

したがって、\(Z_{d}\)の少なくとも一つの素因数\(p\)があって、\(Z_{g}\)に\(p\)は\(p_{d}\)個未満しか含まれません。つまり、\(p_{g} \lt p_{d}\)となります。

ここで、\(p^{p_{d}}\)は、\(Z_{d}\)の約数なので、\(d\)の約数であり、したがって、\(p^{p_{d}}\)も整数\(a,b\)の公約数です。

さらに、\(g\)も整数\(a,b\)の公約数でした。

したがって、整数\(a\)を素因数分解した素因数の組合せの積を\(Z_{a}\)とすると、

\(Z_{a}\)には、その約数である\(Z_{g}\)と\(p^{p_{d}}\)が含まれます。

しかしながら、\(Z_{g}\)に\(p\)は\(p_{d}\)個未満しか含まれませんので、\(Z_{g}p\)が\(Z_{a}\)の約数であることが分かります。

同様に、整数\(b\)を素因数分解した素因数の組合せの積を\(Z_{b}\)とすると、\(Z_{g}p\)が\(Z_{b}\)の約数であることが分かります。

したがって、\(Z_{g}p\)、つまり、\(gp\)は、整数\(a,b\)の公約数であることが分かりましたが、\(gp\)は\(g\)よりも大きく、\(g\)が最大公約数であることに矛盾します。□

補題２－２：　二つの整数の公倍数と最小公倍数の倍数

【補題２－２：　二つの整数の公倍数と最小公倍数の倍数】
整数\(a,b\)の公倍数の集合と、整数\(a,b\)の最小公倍数の倍数の集合は一致する。

【証明】
整数\(a,b\)の公倍数の集合を集合\(M\)、整数\(a,b\)の最小公倍数の倍数の集合を集合\(L\)とします。

まず、\(M\ \supset\ L\)を証明しましょう。

整数\(a,b\)の最小公倍数を\(l\)とすると、\(L\)の任意の要素\(l^{‘}\)は、\(l\)の倍数なので、定義より、ある整数\(k\)があって、

\[l^{‘}=lk \tag{1}\]

と表されます。

\(l\)は、整数\(a,b\)の公倍数なので、\(a\)の倍数であり、倍数の定義より、ある整数\(k^{‘}\)があって、

\[l=ak^{‘} \tag{2}\]

と表されます。

数式（１）に（２）を代入すると、

\[l^{‘}=a(k^{‘}k) \]

となり、\(l^{‘}\)も\(a\)の倍数であることが分かります。

\(l\)は\(b\)の倍数でもあるので、同様に、\(l^{‘}\)が\(b\)の倍数であることも分かります。

したがって、\(l^{‘}\)が整数\(a,b\)の公倍数であることが分かり、\(l^{‘}\in M\)が成り立ちます。

次に、\(M\ \subset\ L\)を証明しましょう。

\(M\ \not\subset\ L\)を仮定して、矛盾を導き出しましょう。

\(M\ \not\subset\ L\)であれば、\(M\)のある要素\(m\)が存在して、\(m \notin L\)が成り立ちます。

つまり、\(m\)は\(l\)の倍数ではないので、定義より、どのような整数\(k^{”}\)を取っても、

\[m=l \cdot k^{”} \tag{3}\]

と表すことはできません。

一方で、最小公倍数\(l\)は、正の公倍数であり\(0\)ではありません。

ちなみに、上述した通り、\(0\)に最小公倍数は定義されないので、前提として整数\(a,b\)は\(0\)ではなく、その最小公倍数\(l\)も正の公倍数であり\(0\)ではありません。

したがって、整数の剰余（余り）の一意性（参考：素因数分解の一意性（算術の基本定理）の証明：補題１　剰余（余り）の一意性の証明）により、次の式を満たす整数\(s\)と\(0\le r\lt l\)がただ一つ存在します。

\[m=l\cdot s+r \tag{4}\]

ここで\(r = 0\)とすると、数式（３）と矛盾するので、\(r\neq 0\)であることが分かります。

数式（４）を変形すると、

\[r=m\ -\ l\cdot s\]

右辺に注目すると、\(m\)も\(l\)も整数\(a,b\)の公倍数なので、\(a\)の倍数でもあり、\(b\)の倍数でもあります。

したがって、\(m\)と\(l\)から\(a\)を括りだすことも、\(b\)を括りだすこともできるので、左辺の\(r\)も\(a\)の倍数でもあり、\(b\)の倍数でもあることが分かります。

つまり、\(r\)も整数\(a,b\)の公倍数になります。

そうすると、\(r\)は\(0\lt r\lt l\)であり、\(l\)よりも小さな正の公倍数となり、\(l\)が最小公倍数であることと矛盾します。□

それでは、次に、二つの整数を対象とした【補題２－１】と【補題２－２】の対象を広げて、二つ以上の整数を対象としても成り立つことを証明しましょう。

定理３－１：　複数の整数の公約数と最大公約数の約数

【定理３－１：　複数の整数の公約数と最大公約数の約数】
複数の整数の公約数の集合と、その複数の整数の最大公約数の約数の集合は一致する。

【証明】
複数の整数を\(k_{i}\ (1\le i \le m)\)としょう。

まず、\(k_{1}\)と\(k_{2}\)の最大公約数を\(g_{2}\)とすると、【補題２－１：　二つの整数の公約数と最大公約数の約数】より、\(k_{1}\)と\(k_{2}\)の公約数の集合を\(K_{2}\)、\(g_{2}\)の約数の集合を\(G_{2}\)とすると、\(K_{2}\)と\(G_{2}\)は一致します。

次に、【定理１：　複数の整数の最大公約数と最小公倍数の存在】より、２つ以上の整数の公約数は、公約数の取る順序によらずに一意に定まるので、\(K_{2}\)と\(k_{3}\)の公約数の集合の共通部分を\(K_{3}\)とすれば、\(K_{3}\)は\(k_{1}\)と\(k_{2}\)と\(k_{3}\)の公約数の集合となります。

一方、\(g_{2}\)と\(k_{3}\)の最大公約数を\(g_{3}\)として、\(g_{3}\)の約数の集合を\(G_{3}\)とすると、【補題２－１：　二つの整数の公約数と最大公約数の約数】より、\(G_{3}\)は、\(G_{2}\)と\(k_{3}\)の公約数の集合の共通部分となります。

ここで、\(K_{2}=G_{2}\)より、\(K_{3}=G_{3}\)となることが分かります。したがって、\(G_{3}\)は\(k_{1}\)と\(k_{2}\)と\(k_{3}\)の公約数の集合となります。

同様に、\(2\le i \le m-1\)において【定理１：　複数の整数の最大公約数と最小公倍数の存在】より、２つ以上の整数の公約数は、公約数の取る順序によらずに一意に定まるので、\(K_{i}\)と\(k_{i+1}\)の公約数の集合の共通部分を\(K_{i+1}\)とすれば、\(K_{i+1}\)は\(k_{1},\ \cdots\ ,k_{i+1}\)の公約数の集合となります。

一方、\(g_{i}\)と\(k_{i+1}\)の最大公約数を\(g_{i+1}\)として、\(g_{i+1}\)の約数の集合を\(G_{i+1}\)とすると、【補題２－１：　二つの整数の公約数と最大公約数の約数】より、\(G_{i+1}\)は、\(G_{i}\)と\(k_{i+1}\)の公約数の集合の共通部分となります。

ここで、\(K_{i}=G_{i}\)より、\(K_{i+1}=G_{i+1}\)となることが分かります。したがって、\(G_{i+1}\)は\(k_{1},\ \cdots\ ,k_{i+1}\)の公約数の集合となります。

以上より、\(G_{m}\)は\(k_{1},\ \cdots\ ,k_{m}\)の公約数の集合であることが分かりました。

\(K_{m}=G_{m}\)であり、\(K_{m}\)の最大値と\(G_{m}\)の最大値は一致します。

\(K_{m}\)の最大値は、\(k_{1},\ \cdots\ ,k_{m}\)の最大公約数であり、\(G_{m}\)の最大値は\(g_{m}\)なので、\(g_{m}\)も\(k_{1},\ \cdots\ ,k_{m}\)の最大公約数であることが分かります。

\(G_{m}\)は、\(g_{m}\)の約数の集合なので、\(K_{m}=G_{m}\)より、\(k_{1},\ \cdots\ ,k_{m}\)の公約数の集合と最大公約数の約数の集合が一致していることが分かります。□

定理３－２：　複数の整数の公倍数と最小公倍数の倍数

【定理３－２：　複数の整数の公倍数と最小公倍数の倍数】
複数の整数の公倍数の集合と、その複数の整数の最小公倍数の倍数の集合は一致する。

【証明】
【定理３－１：　複数の整数の公約数と最大公約数の約数】において、約数を倍数に、最大を最小に置き換えれば、同じように証明できます。□

前述しましたが、【定理３－１】と【定理３－２】のすごいところは、最大公約数あるいは最小公倍数を取り出せば、公約数あるいは公倍数の集合を取り出したことになることです。

しかし、まだ、複数の整数において最大公約数あるいは最小公倍数をどのように計算すればよいかについては何も分かっていません。

複数の整数において最大公約数あるいは最小公倍数を計算するために、公約数あるいは公倍数の集合を計算していくしかないのであれば、この定理は、公約数あるいは公倍数の集合を取り出すための実際上の役には立たないことになります。

しかしながら、最大公約数あるいは最小公倍数を計算するために、直接、各整数の約数の集合から公約数、あるいは各整数の倍数の集合から公倍数の集合を計算する必要はありません。

代わりに、最大公約数の最大公約数あるいは最小公倍数の最小公倍数を計算して行けば良いことが、次の系と定理から分かります。

最大公約数の最大公約数、最小公倍数の最小公倍数

系４－１：　最大公約数の最大公約数

【系４－１：　最大公約数の最大公約数】
複数の整数の集合\(A\)と\(B\)があったときに、\(A\ \cup\ B\)の最大公約数は、\(A\)の最大公約数と\(B\)の最大公約数の最大公約数と一致する。

【証明】
\(A\)の公約数の集合を\(C_{a}\)、最大公約数を\(g_{a}\)、\(g_{a}\)の約数の集合を\(G_{a}\)とします。

【定理３－１：　複数の整数の公約数と最大公約数の約数】より、

\[C_{a}=G_{a} \tag{1}\]

が成り立ちます。

同様に、\(B\)の公約数の集合を\(C_{b}\)、最大公約数を\(g_{b}\)、\(g_{b}\)の約数の集合を\(G_{b}\)とします。

【定理３－１：　複数の整数の公約数と最大公約数の約数】より、

\[C_{b}=G_{b} \tag{2}\]

が成り立ちます。

\(A\ \cup\ B\)の公約数の集合を\(C_{ab}\)とすると、【定理１：　複数の整数の最大公約数と最小公倍数の存在】より、取る順序によらず複数の整数の公約数の集合は一意に定まるので、

\[C_{ab}=C_{a}\ \bigcap\ C_{b} \tag{3}\]

が成り立ちます。

ちなみに、\(A\)と\(B\)に重複する整数があっても、公約数は変わりがありません。

数式（１）（２）を（３）に代入して、

\[C_{ab}=G_{a}\ \bigcap\ G_{b} \tag{4}\]

が成り立ちます。

ここで、\(G_{a}\ \cap\ G_{b}\)は\(g_{a}\)と\(g_{b}\)の公約数の集合です。

したがって、\(g_{a}\)と\(g_{b}\)の最大公約数を\(g_{ab}\)、\(g_{ab}\)の約数の集合を\(G_{ab}\)とすると、

【定理３－１：　複数の整数の公約数と最大公約数の約数】より、

\[G_{a}\ \bigcap\ G_{b} = G_{ab} \tag{5}\]

が成り立ちます。

数式（４）（５）より、

\[C_{ab}\ =\ G_{ab} \]

が成り立ちます。

したがって、\(A\ \cup\ B\)の最大公約数を\(c_{ab}\)とすると、

\[c_{ab}\ =\ g_{ab} \]

が成り立つことが分かりました。□

系４－２：　最小公倍数の最小公倍数

【系４－２：　最小公倍数の最小公倍数】
複数の整数の集合\(A\)と\(B\)があったときに、\(A\ \cup\ B\)の最小公倍数は、\(A\)の最小公倍数と\(B\)の最小公倍数の最小公倍数と一致する。

【証明】
【定理３－２】の証明と同様に、【系４－１：　最大公約数の最大公約数】において、約数を倍数に、最大を最小に置き換えれば、同じように証明できます。

それでは、次に、二つの集合を対象とした【系４－１】と【系４－２】の対象を広げて、二つ以上の集合を対象としても成り立つことを証明しましょう。

定理５－１：　複数の最大公約数の最大公約数

【定理５－１：　複数の最大公約数の最大公約数】
\(n\)個の複数の整数の集合\(K_{i}\ (1 \le i \le n)\)があったときに、\(\bigcup_{i=1}^{n} K_{i}\)の最大公約数は、各\(K_{i}\)の最大公約数の最大公約数と一致する。

【証明】
\(K_{i}\)の最大公約数を\(k_{i}\)とします。

まず、\(i=1\)のときに、

\(K_{1} \cup K_{2}\)の最大公約数を\(g{2}\)、\(k_{1},k_{2}\)の最大公約数を\(h_{2}\)とすると、

【系４－１：　最大公約数の最大公約数】を\(K_{1}\)と\(K_{2}\)に適用すると、\(k_{1}\)と\(k_{2}\)の最大公約数である\(h_{2}\)と、\(K_{1} \cup K_{2}\)の最大公約数である\(g_{2}\)には、\(g_{2}=h_{2}\)が成り立ちます。

次に、\(i=2\)のときに、

\(K_{1} \cup K_{2} \cup K_{3}\)の最大公約数を\(g_{3}\)、\(k_{1},k_{2},k_{3}\)の最大公約数を\(h_{3}\)、\(h_{2}\)と\(k_{3}\)の最大公約数を\(j_{3}\)とすると、

【系４－１：　最大公約数の最大公約数】を\(\{k_{1},k_{2}\}\)と\(\{k_{3}\}\)に適用すると、\(h_{2}\)と\(k_{3}\)の最大公約数である\(j_{3}\)と、\(\{k_{1},k_{2},k_{3}\}\)の最大公約数である\(h_{3}\)には、

\[j_{3}=h_{3} \tag{1}\]

が成り立ちます。

一方で、\(K_{1} \cup K_{2}\)の最大公約数である\(g_{2}\)と\(k_{1},k_{2}\)の最大公約数である\(h_{2}\)は、\(g_{2}=h_{2}\)となるので、\(h_{2}\)と\(k_{3}\)の最大公約数である\(j_{3}\)は、\(g_{2}\)と\(k_{3}\)の最大公約数にもなります。

そこで、【系４－１：　最大公約数の最大公約数】を\(K_{1} \cup K_{2}\)と\(K_{3}\)に適用すると、\(g_{2}\)と\(k_{3}\)の最大公約数である\(j_{3}\)と、\(K_{1} \cup K_{2} \cup K_{3}\)の最大公約数である\(g_{3}\)には、

\[g_{3}=j_{3} \tag{2}\]

が成り立ちます。

数式（１）（２）上記を合わせると、\(g_{3}=h_{3}\)が成り立ちます。

同様に、\(3 \le i \le n-1\)のときに、

\(\bigcup_{s=1}^{i+1} K_{s}\)の最大公約数を\(g_{i+1}\)、\(k_{1},k_{2}, \cdots ,k_{i+1}\)の最大公約数を\(h_{i+1}\)、\(h_{i}\)と\(k_{i+1}\)の最大公約数を\(j_{i+1}\)とすると、

【系４－１：　最大公約数の最大公約数】を\(\{k_{1},k_{2}, \cdots ,k_{i}\}\)と\(\{k_{i+1}\}\)に適用すると、\(h_{i}\)と\(k_{i+1}\)の最大公約数である\(j_{i+1}\)と、\(\{k_{1},k_{2}, \cdots ,k_{i+1}\}\)の最大公約数である\(h_{i+1}\)には、

\[j_{i+1}=h_{i+1} \tag{3}\]

が成り立ちます。

一方で、\(\bigcup_{s=1}^{i} K_{s}\)の最大公約数である\(g_{i}\)と\(k_{1},k_{2}, \cdots ,k_{i}\)の最大公約数である\(h_{i}\)は、\(g_{i}=h_{i}\)となるので、\(h_{i}\)と\(k_{i+1}\)の最大公約数である\(j_{i+1}\)は、\(g_{i}\)と\(k_{i+1}\)の最大公約数にもなります。

そこで、【系４－１：　最大公約数の最大公約数】を\(\bigcup_{s=1}^{i} K_{s}\)と\(K_{i+1}\)に適用すると、\(g_{i}\)と\(k_{i+1}\)の最大公約数である\(j_{i+1}\)と、\(\bigcup_{s=1}^{i+1} K_{s}\)の最大公約数である\(g_{i+1}\)には、

\[g_{i+1}=j_{i+1} \tag{4}\]

が成り立ちます。

数式（３）（４）上記を合わせると、\(g_{i+1}=h_{i+1}\)が成り立ちます。

つまり、\(\bigcup_{s=1}^{n} K_{s}\)の最大公約数である\(g_{n}\)と、\(k_{1},k_{2}, \cdots ,k_{n}\)の最大公約数である\(h_{n}\)に、

\[g_{n}=h_{n}\]

が成り立ちました。□

定理５－２：　複数の最小公倍数の最小公倍数

【定理５－２：　複数の最小公倍数の最小公倍数】
\(n\)個の複数の整数の集合\(K_{i}\ (1 \le i \le n)\)があったときに、\(\bigcup_{i=1}^{n} K_{i}\)の最小公倍数は、各\(K_{i}\)の最小公倍数の最小公倍数と一致する。

【証明】
【定理５－１：　複数の最大公約数の最大公約数】において、最大公約数を最小公倍数に置き換えれば、同じように証明できます。□

複数の整数の最大公約数や最小公倍数を求める方法

ここまでくれば、このページの目標である「複数の整数の最大公約数や最小公倍数を求めるためには、それらの公約数や公倍数を求める必要はなく、最大公約数の最大公約数や最小公倍数の最小公倍数を次々に計算して行くだけで済む」ということを示すことができます。

まず、最大公約数や最小公倍数を計算したい複数の整数の全体集合を\(U\)とします。

次に、\(U\)を\(U\)の空でない部分集合\(K_{i}\ (1 \le i \le n)\)に分けたとします。

そうすると、最大公約数の最大公約数や最小公倍数の最小公倍数を次々に計算する方法とは、具体的には、すでに最大公約数や最小公倍数が分かっている\(K_{i}\)の和集合の組から、その組全体の和集合の最大公約数や最小公倍数を計算することを繰り返し、最終的にその和集合が\(U\)と一致することだと分かります。

そして、【定理５－１】【定理５－２】の対象となる集合の中身は、整数一つでもそれ自身を最大公約数や最小公倍数とみなしてしまえば問題なく適用できます。

つまり、最大公約数や最小公倍数を計算する過程において、その元々の整数か、その途中に出てくる最大公約数や最小公倍数か、どちらが対象となっていても、これらの定理を適用できることが分かります。

したがって、和集合が\(U\)と一致するまで繰り返される、その一回一回の計算の正しさが、初めから最後まですべて【定理５－１】【定理５－２】によって保障されます。

くわえて、この計算がどのような順序や和集合を取るとしても、結果的にその和集合が\(U\)と一致すれば、\(U\)の最大公約数や最小公倍数を計算することができたことになるので、計算の順序や過程は関係ないことも分かります。

以上で、このページの目標を示すことができました。

ただ、実際の一つ一つの最大公約数や最小公倍数の計算が、約数や倍数を取り出して比較するよりも大変であったら、今までの議論はあまり意味がありません。

しかし、その非常に簡単で効率的な計算方法としてユークリッドの互除法などが知られています。ユークリッドの互除法について詳しくは、最大公約数と最小公倍数の計算方法：ユークリッドの互除法をご覧ください。

複数の整数の最大公約数をユークリッドの互除法を使って効率的に計算するための一つの方法としては、複数の整数を一列に並べて、初めは左の二つの最大公約数を取り、その最大公約数と次の整数の最大公約数を取るという計算を最後まで繰り返せば、複数の整数全体の最大公約数を計算することができます。最小公倍数の場合も同様です。

ちなみに、このページでは、最大公約数あるいは最小公倍数を取り出す一回の計算で対象とする整数の個数を、３個以上の場合も想定して考えましたが、通常、用いられるユークリッドの互除法は、2個の整数を計算の対象とします。

付け加えると、冒頭でも触れましたが、最大公約数や最小公倍数を計算すれば、【定理３－１：　複数の整数の公約数と最大公約数の約数】や【定理３－２：　複数の整数の公倍数と最小公倍数の倍数】から、その約数や倍数を取れば、複数の整数の公約数や公倍数を計算することもできたことになります。

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