最大公約数と最小公倍数の定理について、自分の理解を深めるために（参考文献の行間を埋めるかたちで）証明を再現してみた．参考文献は「代数と数論の基礎」（中島匠一）．
bがaで割り切れて, かつaがbで割り切れる ⇔ a=b
$a|b$ かつ $b|a$ ⇔ $a=b$
が成り立つことを示す．
$a|b$という表記は「$a$は$b$の約数である（=$b$は$a$で割り切れる）」ことを意味する．
これは「$b=ak$となるような整数$k$が存在する」と言い換えることができる．
$a|b$より
$b=aA$となるような整数$A$が存在する．
$b|a$より
$a=bB$となるような整数$B$が存在する。
$a=bB$を代入して
$b=bBA$
両辺に$\frac{1}{b}$をかけて
$BA=1$
したがって
$A=1$
$B=1$
$a=bB$に代入して
$a=b$
逆は自明．
■
a,bの任意の公倍数は最小公倍数の倍数である
$a,b$の任意の公倍数を$m$とすると
$lcm(a,b) | m$
が成り立つことを示す．
$L = lcm(a,b)$とする.
$m = Lk + r (0≦r<L)$とする.
これを$r$についての式にすると
$r = m - Lk$
ここで$m,L$は$a,b$の公倍数であるので、$r$も$a,b$の公倍数である．
なぜそう言えるのかを以下に説明する。
まず, $m,L$が$a$の倍数であることに注目して
$m = aM$
$L = al$
とすると
$r = m - Lk = aM - alk = a(M - lk)$
これで、$r$を$a$の倍数として表現できた．
同様にして$r$を$b$の倍数として表現できる．
$r$は$a$の倍数としても$b$の倍数としても表現できる数なので, $r$は$a,b$の公倍数である．
しかし, $r$が$a,b$の公倍数であるとすると, $L$の最小性と矛盾する（最小公倍数の定義は「0でない公倍数のうち最小の自然数」なので, $r<L$となるような自然数$r$の存在は$L$の定義と矛盾する）．したがって$r = 0$．
$r=0$を代入して
$m=Lk + 0$
$m = Lk$
ここで各変数の意味を確認すると, $m$は「$a,b$の任意の公倍数」である．$L$は「$a,b$の最小公倍数」である．$m = Lk$より「$a,b$の任意の公倍数は, $a,b$の最小公倍数の倍数である」と結論できる．
■
a,bの任意の公約数は最大公約数の約数である
$a,b$の任意の公約数を$d$, 最大公約数を$G$とするとき
$lcm(d,G) = G$
が成り立つことを示す．
$d,G$の最小公倍数を$l$とすると
$lcm(d,G) = l$
公倍数の定義より$G≦l$
$d|a$ かつ $G|a$ より $a$は$d,G$の公倍数．$d,G$の公倍数が$a$, 最小公倍数が$l$ということは$l|a$（「任意の公倍数は最小公倍数の倍数」を利用した）
$d|b$ かつ $G|b$ より $b$は$d,G$の公倍数．$d,G$の公倍数が$b$, 最小公倍数が$l$ということは$l|b$（「任意の公倍数は最小公倍数の倍数」を利用した）
$l|a, l|b$より, $l$は$a,b$の公約数であることが示された．
$G$の最大性より, $l≦G$である．
$G≦l$ かつ $l≦G$ から、$l = G$
$lcm(d,G) = l$
$l = G$を代入して
$lcm(d,G) = G$
■
gcd(a,b)=gcd(b,a)
$gcd(a,b) = gcd(b,a)$ が成り立つことを示す．
$G_1 = gcd(a,b)$
$G_2 = gcd(b,a)$
とする．
$G_1$は$a,b$の公約数なので「最大公約数は任意の公約数の倍数」であることより
$G_1|G_2$
と表せる。
同様に, $G_2$は$b,a$の公約数なので「最大公約数は任意の公約数の倍数」であることより
$G_2|G_1$
と表せる．
$G_1|G_2$ かつ $G_2|G_1$ より $G_1=G_2$
■
gcd(a, b+ac) = gcd(a, b)
$gcd(a, b+ac) = gcd(a, b)$
が成り立つことを示す．
$G_1 = gcd(a, b+ac)$
$G_2 = gcd(a, b)$
とする。
$a = G_2A_2$
$b = G_2B_2$
$b+ac = G_2B_2 + G_2A_2c = G_2(B_2 + A_2c)$
$G_2$は$a,b+ac$の公約数であることから
$G_2 ≦ G_1$
$a = G_1A_1$
$b + ac = G_1B_1$
両辺から$ac$を引いて
$(b + ac) - ac = (G_1B_1) - ac$
$(b + ac) - ac = (G_1B_1) - G_1A_1c$
$b + (ac - ac) = G_1(B_1) - G_1(A_1c)$
$b = G_1(B_1 - A_1c)$
$G_1$は$a$と$b$の公約数であることから
$G_1 ≦ G_2$
$G_1≧G_2$ かつ $G_1≦G_2$ より
$G_1=G_2$
■
gcd(a/d,b/d) = gcd(a,b)/d
$d|a, d|b$ のとき
$gcd(\frac{a}{d},\frac{b}{d}) = \frac{gcd(a,b)}{d}$
が成り立つことを示す．
$d' = gcd(\frac{a}{d},\frac{b}{d})$
$d'' = \frac{gcd(a,b)}{d}$
とおく．
方針としては
$d'|d''$ かつ $d''|d'$
を示すことで $d' = d''$ を証明する．
まず $d'$ に注目する。
$d' = gcd(\frac{a}{d},\frac{b}{d})$
「任意の公約数は最大公約数の約数である」より
$d'|\frac{a}{d}$ かつ $d'|\frac{b}{d}$
$d$ をかけて
$dd'|a$ かつ $dd'|b$
「任意の公約数は最大公約数の約数である」より
$dd'|gcd(a,b)$
$\frac{1}{d}$をかけて
$d'|\frac{gcd(a,b)}{d}$
以上より $d'|d''$ が示された．
つぎに $d''$に注目する．
$d'' = \frac{gcd(a,b)}{d}$
両辺に $d$ をかけると
$dd'' = gcd(a,b)$
「任意の公約数は最大公約数の約数である」より
$dd''|a dd''|b$
$\frac{1}{d}$ をかけると
$d''|\frac{a}{d} d''|\frac{b}{d}$
「任意の公約数は最大公約数の約数である」より
$d''|gcd(\frac{a}{d}, \frac{b}{d})$
以上より $d''|d'$ が示された．
$d'|d''$ かつ $d''|d'$ より $d'=d''$
$gcd(\frac{a}{d},\frac{b}{d}) = \frac{gcd(a,b)}{d}$ が示された。
gcd(a/g,b/g)=1
$d$が$a,b$の公約数であり $g=gcd(a,b)$とするとき
$gcd(\frac{a}{g},\frac{b}{g}) = 1$
が成り立つことを示す．
$gcd(\frac{a}{d},\frac{b}{d}) = \frac{gcd(a,b)}{d}$
に $d=g$ を代入する．
$gcd(\frac{a}{g},\frac{b}{g}) = \frac{gcd(a,b)}{g} = \frac{gcd(a,b)}{gcd(a,b)} = 1$
gcd(ac,bc)=gcd(a,b)c
$d'=gcd(ac,bc)$
$d''=gcd(a,b)c$
として $d'=d''$ が成り立つことを示す．
まず $d'=gcd(ac,bc)$ に注目する．
「最大公約数は任意の公約数の倍数である」より
$d'|ac$ かつ $d'|bc$
$\frac{1}{c}$をかけて
$\frac{d'}{c}|a$ かつ $\frac{d'}{c}|b$
「任意の公約数は最大公約数の約数である」より
$\frac{d'}{c}|gcd(a,b)$
$c$をかけて
$d'|gcd(a,b)c$
以上より
$gcd(ac,bc)|gcd(a,b)c$
つぎに $d''=gcd(a,b)c$ に注目する．
$\frac{1}{c}$をかけて
$\frac{d''}{c}=gcd(a,b)$
「最大公約数は任意の公約数の倍数である」より
$\frac{d''}{c}|a$ かつ $\frac{d''}{c}|b$
$c$をかけて
$d''|ac$ かつ $d''|bc$
「任意の公約数は最大公約数の約数」より
$d''|gcd(ac,bc)$
以上より
$gcd(a,b)c|gcd(ac,bc)$
まとめると
$gcd(ac,bc)|gcd(a,b)c$ かつ $gcd(a,b)c|gcd(ac,bc)$ より
$gcd(ac,bc) = gcd(a,b)c$
■
gcd(a,b)はgcd(a,bc)の約数である
$gcd(a,b)|gcd(a,bc) (c≠0)$
が成り立つことを示す．
$G_1=gcd(a,b)$
とすると
$a=G_1A$
$b=G_1B$
$bc=G_1Bc$
$a,bc$は$G_1$を公約数とするため, 「任意の公約数は最大公約数の約数」より
$G_1|gcd(a,bc)$
以上より
$gcd(a,b)|gcd(a,bc)$
■
ユークリッドの互除法の証明
$a$を$b$で割ったときの商を$q$, 余りを$r (0≦r<b)$とする．
このとき$gcd(a,b) = gcd(b,r)$が成り立つことを示す．
$G_1 = gcd(a,b)$
$G_2 = gcd(b,r)$
$G_1 = G_2$ を証明する．
証明の方針
- $G_1$が（$a,b$の最大公約数であると同時に）$b,r$の公約数でもある．
- $G_2$が（$b,r$の最大公約数であると同時に）$a,b$の公約数でもある．
以上から, $G_1 = G_2$であることを示す．これを示すために
- $r$を$G_1$の倍数として表現する．
- $a$を$G_2$の倍数として表現する．
「$a$を$b$で割ったときの商を$q$、余りを$r$とする」は
$a÷b = q … r$
と表せる。$a,r$についての式で表すと
$a = bq + r$
$r = a - bq$
となる．さらに, $a,b$の最大公約数は$G_1$なので、$a=G_1A$ $b=G_1B_1$として
$r = a - bq = G_1A - (G_1B_1)q = G_1A - G_1(B_1q) = G_1(A - B_1q)$
この式から「$r$は$G_1$を約数としてもつ」と言える．
さらに$G_1$は$b$の約数でもあるので「$G_1$は$b,r$の公約数である」と言える．
まとめると
- $G_1$は$b,r$の公約数である．
- $G_2$は$b,r$の最大公約数である．
最大公約数は「公約数のうち最大のもの」と定義されるので
$G_1 ≦ G_2$
が成り立つ．
$b,r$の最大公約数は$G_2$なので, $b=G_2B_2$ $r=G_2R$として
$a = bq + r = (G_2B_2)q + G_2R = G_2(B_2q + R)$
この式から「$a$は$G_2$を約数としてもつ」と言える.
さらに$G_2$は$b$の約数でもあるので「$G_2$は$a,b$の公約数である」と言える.
まとめると
- $G_1$は$a,b$の最大公約数である．
- $G_2$は$b,r$の公約数である.
最大公約数は「公約数のうち最大のもの」と定義されるので
$G_1 ≧ G_2$
が成り立つ．
$G_1 ≦ G_2$ かつ $G_1 ≧ G_2$ より $G_1 = G_2$
■
g=gcd(a,b) l=lcm(a,b) とするとき lg=ab
$g=gcd(a,b)$
$l=lcm(a,b)$
とするとき
$lg=ab$
が成り立つことを示す．
$ab$は$a,b$の公倍数である．
「任意の公倍数は最小公倍数の倍数である」つまり $l|ab$ なので
$ab=ld$
と表すことができる．
$ab=ld$ の両辺に $\frac{1}{b}$ をかけて
$a=\frac{ld}{b}=\frac{l}{b}・d$
$ab=ld$ の両辺に $\frac{1}{a}$ をかけて
$b=\frac{ld}{a}=\frac{l}{a}・d$
このことから $d$ は $a,b$ の公約数であるといえる．
「任意の公約数は最大公約数の約数である」より
$d|g$
が成り立つ．
つぎに $\frac{ab}{g}$ について
$\frac{ab}{g}=a・\frac{b}{g}=b・\frac{a}{g}$
このことから $\frac{ab}{g}$ は $a,b$ の公倍数であるといえる．
$\frac{ab}{g}$ に $ab=ld$ を代入して
$\frac{ld}{g}$
「任意の公倍数は最小公倍数の倍数である」より
$l|\frac{ld}{g}$
$g$ をかけて
$gl|ld$
$\frac{1}{l}$ をかけて
$g|d$
が成り立つ。
$d|g$ かつ $g|d$ より $d=g$
$d=g$ を $ab=ld$ に代入すると $ab=lg$
■