ユークリッドの互除法：
a>bでaとbを正の整数とする。
a mod b ≠ 0 ⇒ gcd(a,b) = gcd(b,a mod b)
[証明]
gcd(a,b) = gとおくと、互いに素なk,mを用いて、
a = gk , b = gmと置ける。
gkをgmで割った時の商をQ、余りをRとするとき、
gk = Qgm + Rとおけるから、R = g(k - Qm)
gcd(gm , g(k-Qm) ) = gであることを示す。
コレを示すには、
mとk-Qmが互いに素であることを示せば良い。
背理法を用いる。
k - Qmが1以外のmの約数dを持つとすると、
任意の正の整数lを用いて、k - Qm = dlとおける。
移行すると、k = d(Qm/d + l)となり、
kは1以外のmの約数dをもち、
kとmが互いに素であることに反する。コレは矛盾。
証明終わり
