第1个回答 2010-09-25
你的辗转相除法有错！
辗转相除法：
要求a、b两个整数的最大公约数，a＞b，那么我们先用a除以b，得到商 q1，余数r1：a÷b＝q1…r1我们当然也可以把上面这个式子改写成乘法式：
a＝b * q1＋r1
如果r1＝0，那么b就是a、b的最大公约数3。要是r1≠0，就继续除，用b除以r1，我们也可以有和上面一样的式子：
b＝r1q2＋r2
如果余数r2＝0，那么r1就是所求的最大公约数3。因为如果b＝r1q2＋r2变成了b＝r1q2，那么b1r1的公约数就一定是a1b的公约数。这是因为一个数能同时除尽b和r1，那么由a＝b * q1＋r1，就一定能整除a，从而也是a1b的公约数。
反过来，如果一个数d，能同时整除a1b，那么由1）式，也一定能整除r1，从而也有d是b1r1的公约数。
这样，a和b的公约数与b和r1的公约数完全一样，那么这两对的最大公约数也一定相同。那b1r1的最大公约数，在r1＝0时，不就是r1吗？所以a和b的最大公约数也是r1了。
如果r2不是0，用r1除以r2，……直到余数为零为止。