最大公約数と最小公倍数の定理について、自分の理解を深めるために（参考文献の行間を埋めるかたちで）証明を再現してみた．参考文献は「代数と数論の基礎」（中島匠一）．

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$
■