最初はユークリッドの互除（ごじょ）法から入ります
定理1.1
(x, y) を x と y の最大公約数とする
a, b ∈N で a を b で割った余りが r のとき
(a, b) = (b, r)
証明
(a, b) = g, (b, r) = h とおいて g = h であることを示す
a, b は g の倍数なので、
a = a'g, b = b'g …①
と書ける
a を b で割った商を q, 余りを r と置くと
a = qb + r …②
これより r = a - qb
これに①を代入して r = a'g - qb'g = g(a' - qb')
となり r も g を約数として持つ
もともと b は g を約数として持つから g は b と r の公約数
公約数は最大公約数以下だから…③
g <= h
