2.1.3 最大公約数の生成

ユークリッドの互除法は大きな数の最大公約数を求められるということに過ぎません。理論的にも大変重要な手法なのです。

ユークリッドの互除法の理論的に重要な点は、次のような定理が成り立つことを示すことができることです。

定理 2.1.17
$n,m$を整数とすると
（1） $(n,m)=d$のとき、$an+bm=d$となるような整数$a,b$が存在する。逆に、整数$a,b$が存在して$an+bm=d'$となるとき$d\mid d'$である。
（2） $A$を$n$の倍数全体の集合、$B$を$m$の倍数全体の集合とするとき、$A+B$は$d=(n,m)$の倍数全体の集合となる。
（3） $n,m$が互いに素 $\Longleftrightarrow$ $an+bm=1$となる整数$a,b$が存在する

ここで、$A+B$とは$A$の要素$a$と$B$の要素$b$の和からなる集合、つまり、 $A+B=\{a+b \vert a\in A, b\in B\}$を意味しています。

証明の前に例を見ましょう。

例 2.1.18
$n=3,m=5$とすると、$3$の倍数全体の集合$A$は、

$$A=\{\cdots,-12,-9,-6,-3, 0, 3, 6, 9,12,\cdots\}$$

$5$の倍数全体の集合$B$は、

$$B=\{\cdots,-15,-10,-5, 0, 5,10,15,\cdots\}$$

このとき、 $A+B=\{a+b \vert a\in A, b\in B\}$を求めてみましょう。

$B$は5の倍数ですので、$A+B$は、$A$を5の倍数分平行移動したものです。
-10から10までの範囲で$A$を平行移動させてみましょう。

$$A+(-10)=\{\cdots,-10,-7,-4,-1, 2, 5, 8,\cdots\}$$

$$A+(-5)=\{\cdots,-8,-5,-2,1, 4, 7,10,\cdots\}$$

$$A+0=\{\cdots,-9,-6,-3, 0, 3, 6, 9,\cdots\}$$

$$A+5=\{\cdots,-10,-7,-4,-1, 2, 5, 8,\cdots\}$$

$$A+10=\{\cdots,-8,-5,-2, 1, 4, 7,10,\cdots\}$$

これから、$A+B$はどうなるでしょうか。

$$A+B=\{\cdots,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10\cdots\}$$

これから、A+Bは整数全体になりそうですね。これが、定理2.1.17が意味していることです。

これは、驚きの定理です。是非、みなさんもいろいろなパターンで試してみてください。この後なぜこれが正しいのか証明します。証明も大切ですが、いろいろなパターンを自分自身で計算し体験し感覚をつかむことがより大切です。

それでは、定理2.1.17の証明をしましょう、

証明
（1）整数$n,m$にユークリッドの互除法を適用して、$d,0$とすることができました。ユークリッドの互除法の操作（1）から（3）までの操作をしても、2つの数は$an+bm$の形をしています。したがって、$an+bm=d$となる整数$a,b$が存在することが分かります。
また、$an+bm=d'$のとき$d$は$n,m$の約数ですので$d'$の約数となります。 （2）（1）より、$an+bm=d$ですが両辺を$x$倍することにより$A+B$に$d$の倍数が全て含まれていることが分かります。したがって、$C$を$d$の倍数からなる集合とすると、 $A+B\supset C$が分かります。
逆に、$A+B$の元$a_1n+b_1m$を考えると、$n,m$は$d=(n,m)$の倍数ですので、$a_1n+b_1m$も$d$の倍数となります。したがって、 $A+B\subset C$です。証明できました。
（3） 左から右は（1）の特別な場合です。 右から左も（2）の特別な場合です。