遊びの数学を本気で楽しむ

（証明）

①
背理法で証明していこう。
ｃをａ、ｂの公倍数だが、ｎ＝lcm(ａ、ｂ）の倍数ではない数とする。
割り算定理より
ｃ＝ｎｑ＋ｒかつ0≦ｒ≦ｎ－1となる自然数ｑ、ｒが存在する。

ｃ＝ｎｑ＋ｒと割り算定理より、ｒもａ、ｂの倍数となるが、ｒ＜ｎであるから、ｎ＝lcm(ａ、ｂ)に矛盾する。
よって題意が証明された。

②
ｂはgcd(ａ、ｂ)の倍数なので ｂ／gcd(ａ、ｂ) は自然数である。
よってab/gcd(ａ、ｂ)はａの倍数。
同様にして、これはｂの倍数でもあるから lcm(ａ、ｂ)｜ａｂ／gcd(ａ、ｂ) となるので、lcm(ａ、ｂ)gcd(ａ、ｂ)｜ａｂである。

また、lcm(ａ、ｂ)／ｂは整数だから、 ａｂ／lcm(ａ、ｂ)はaの約数。
同様にしてこれはｂの約数でもあるから ａｂ／lcm(ａ、ｂ)｜gcd(ａ、ｂ) となるので、 ａｂ｜lcm(ａ、ｂ)gcd(ａ、ｂ)。

③
ｃをａ、ｂの公約数とし、ｎ＝gcd(ａ、ｂ)とする。
このとき、ａｂ／ｎ＝lcm(ａ、ｂ)であり、ａｂ／ｃはａ、ｂの公倍数だから
①よりａｂ／ｃはａｂ／ｎの倍数である。
よってｃ｜ｎである。

④
ａ｜ｂｃだからｂｃはａ、ｂの公倍数、よって①よりｂｃはlcm(ａ、ｂ)の倍数である。
gcd(ａ、ｂ)＝1なのだから　②よりlcm(ａ、ｂ)＝ａｂである。
したがってａｂ｜ｂｃ、よってａ｜ｃである。


といった具合である。




また、これらよりこんな性質をも見出す事ができる。

ａ、ｂを整数とする。このとき、ａｎ＋ｂｍ＝gcd(ａ、ｂ)を満たす整数ｎ、ｍが存在する。


（証明）

ｂに関して帰納法で証明する。
ｂ＝1のときは、ｎ＝1、ｍ＝ａ－1とおけばよい。

そこで、ｂに対して定理が成り立つことをｂがより小さいときには常に定理が成り立つという仮定のもとで示す。
割り算定理よりａ－ｂｓ＝ｒ、0≦ｒ≦ｂ－1を満たす整数ｓ、ｒが存在する。

ｒ＝0のときは、ｂはａの約数なので、ａ－ｂ(ｓ－1)＝ｂ＝gcd(ａ、ｂ)である。

ｒ＞0のときは、帰納法の過程より、ｂ－ｒｔ＝gcd(ｂ、ｒ)を満たす整数ｔが存在する。

よって、
－ａｔ＋ｂ(1＋ｓｔ) ＝ｂ－ｒｔ＝gcd(ｂ、ｒ)=gcd(ｂ、ａ－ｂｓ)＝gcd(ａ、ｂ)となる。
よって、ｎ＝－ｔ、ｍ＝1＋ｓｔとおけばよい。

これによって題意は満たされることになる。
これにより、定理が証明された。