●ユークリッドの互除法の証明

この証明がわかりにくいという意見が多いので、証明方法を2つ紹介します。

[証明1]（公約数の大小を利用しない方法）
自然数a,b (a≥b)に対して、aをbで割った商をq、余りをrとおくと、a=bp+rと書けて、bとrの公約数は、aの約数である。つまり、bとrの公約数はaとbの公約数でもある。
逆に、r=a-bqよりaとbの公約数は、rの約数である。つまり、aとbの公約数は、bとrの公約数である。つまり、aとbの公約数は、bとrの公約数でもあることになる。
以上から、｛aとbの公約数全体｝=｛bとrの公約数全体｝が言えるので、gcd(a,b)=gcd(b,r)となる。

[証明2]（公約数の大小を利用する方法）
自然数a,b (a≥b)に対して、aをbで割った商をqとするとa=bq+rと書ける。aとbの最大公約数をgcd(a,b)、bとrの最大公約数をgcd(b,r)とする。
a=bq+rの右辺はgcd(b,r)で割り切れるので、左辺のaもgcd(b,r)で割り切れる。するとgcd(b,r)はaとbの公約数なので、gcd(b,r)≦gcd(a,b)。
一方a=bq+rを変形すると、r=a-bqとなり、この式の右辺はgcd(a,b)で割り切れるので、左辺のrもgcd(a,b)で割り切れる。するとgcd(a,b)はbとrの公約数なので、gcd(a,b)≦gcd(b,r)。
したがって、gcd(a,b)=gcd(b,r)となる。