欧几里德算法及贝祖公式

一、欧几里德算法
欧几里德算法是一个用来求两个整数的最大公约数的算法，他也叫辗转相除法。定理如下：

gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0) gcd(greatest common divisor)

证明如下：

a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有a能被d整除，b能被d整除，所以r=a-kb也能被d整除，因此d也是（b,a mod b）的公约数；
反推，假设d是a，a mod b 的公约数，则有b能被d整除，r能被d整除，所以a = kb+r 也能被d整除，因此d是（a，b）的公约数。
因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证

通过该定理，要如何求最小公约数呢？就是不断的运用原理“两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。”，将两个数缩小，直到一个数为0，另一个数就是最小公约数。
例如：求9和12的公约数，gcd(9,12)= gcd(9,12-9)=gcd(9,3) = gcd(9-3,3)=gcd(6,3) =gcd(6-3,3)=gcd(3,3) =gcd(3-3,3) = gcd(0,3) = 3。这个过程可以在计算机中迭代完成。
二、扩展欧几里德算法
仅仅求最大公约数，貌似没什么牛逼的，但由欧几里德算法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如3= 1 ×