证明辗转相除法(欧几里德算法)

定理：两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。

证明：

gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0) a可以表示成a = kb + r（a，b，k，r皆为正整数），则r = a mod b

• 12，18的公因数有：1，2，3，6。
• 由算法gcd（a，b）=gcd(b,a%b)有gcd（12，18）=gcd(18,12%18)=gcd(18,12)
• 18,12的公因数有：1，2，3，6。
• 接着往下算，gcd（18，12）=gcd(12,18%12)=gcd(12,6)
• 12,6的公因数有：1，2，3，6。
• 再往下，gcd（12，6）=gcd(6,12%6)=gcd(6,0)
• 0,6的公因数有：1，2，3，6。

• 最后，就由gcd（0，n)=n得gcd（0，6）=6

  第1，3，5，7他们的公因数集都是相等的，自然的，集合里的最大值也是相等的。

证明：也就是证明如果a=bq+r，那么d是a和b的公因数，当且仅当d是b和r的公因数。

1)设d是a和b的公因数，则d|a且d|b，于是d|(a−bq)。也就是说d|r, 因为r=a−bq. ==》d是b,r的公因数。

这里解释一下d|（a-bq)：

因为d|a，d|b,所以有a=dx,b=dy;把d代入a-bq有dx-dyq=d(x-yq).

所以d|（a-bq)

2)设d是b和r的公因数，则d|r且d|b。于是，d|（bq+r）.所以d|a ==》所以d是a,b的公因数。

综上，a,b的所有公因数和b,r的所有公因数是一样的。那么，d是a，b的最大公因数，当且仅当d是b和r的最大公因数。