松坂和夫「代数系入門」の最大公約数

昔々読んで感銘を受けた証明を書く*1。

n、m > 0 を自然数とする。
J = { x : 整数 | x = an + bm, a, b: 整数} とする。
J は n、m の最大公約数 d の倍数の集合と一致する。

明らかに n、m ∈ J だから、J は正の数を含む。従って J には最小の正の元が存在し(整列性)、それを d とする。 d は J の元だからある整数 u、v が存在して

d = un + vm    (1)

と表すことができる。J の任意の元 z = an + bm に対してこれを d で割って

z = qd + r, 0 ≦ r < d

剰余 r は

r = z - qd = (a - qu)n + (b - qv)m

となり、J の元である: r ∈ J 。d の取り方から r = 0。即ち z は d の倍数。
逆に d の倍数は d の表示式(1)を整数倍することで J に含まれることがわかる。

*1:少し簡単にした