辗转相除法的原理
辗转相除法，即欧几里德算法，被用来求两个数的最大公约数，书上只是很简单的教会你，通过辗转相除，直到最后余数为0，此时的除数便是两数的最大公约数。为了进一步说明这其中的原理，现在就介绍一下，希望对一些人有所帮助。尽量通俗易懂
（ a , b ）表示a 和b的最大公约数
a | b 表示a可以整除b
现在开始证明：
给你两个数a 和 b（假定a大于b），那么你可以通过除法，写出如下的表达式：a = q*b + r 。这很容易明白，就是用a除以b，得到一个商q和余数r 。
通过辗转相除，直到余数为0，此时除数便是最大公约数。假定最后a成了A，b成了B，于是（A，B）= （a，b）此时，便是最需要理解的地方，为什么这两组数的最大公约数就是相等的呢？
回到a = q*b + r 。先假定a 和 b的最大公约数是d，即（a ，b）= d，现在你的任务就是证明（ b，r）= d。
证明：
因为d | a，且d | b，
则d | r（ 在这里就不证明为什么了，稍微想象你就明白了）
所以d是b和r的公约数，但是我们不知道d是不是b和r的最大公约数
假设任一c是b和r的最大公约数，
则c｜r ，且c | b，
则c | a，
所以c是a和b的公约数，
所以c <=d,（已经假定了d是a和b的最大公约数），
所以d就是b和r的最大公约数了。（你假定了c是任意的，也就是说d大于任意其他的公约数，当然d就是最大的了）
也就是说（a，b）= （b，r）
然后你可以像a = q*b + r这样，写出b和r之间的关系，一直写下去，直到余数为0，而（x，0） = x。
然后你可以逆推，就可以得到（A，B）= （a，b）
总结：
由于里面绕的歪子可能有点多，需要慢慢理解。最关键的就是先证明（a，b）= （b，r），然后一直写下去，直到余数为0。然后根据相等的等价性（即a=b,b=c,则a=c），便得到了结论
