为什么能用辗转相除法求最大公约数

辗转相除法是一种利用余数递归求解最大公约数的方法。假设要求两个数a和b的最大公约数，我们可以先用a除以b得到余数r，然后再用b除以r得到余数r1，再用r除以r1得到余数r2，以此类推，直到余数为0为止。此时，最后一次除法的除数就是a和b的最大公约数。

这个方法的正确性可以通过以下方式证明：

1. 假设d是a和b的一个公约数，即d能同时整除a和b。

2. 设a = qb + r，其中q和r是a除以b的商和余数。由于d整除a和b，所以d也要整除qb和r。

3. 但是，r = a - qb，所以d也要整除r和qb。

4. 接着，我们用b除以r得到余数r1，再用r除以r1得到余数r2，以此类推，直到余数为0为止。

5. 在这个过程中，我们可以发现，每次得到的余数都可以表示成前面两个数的线性组合，即r_i = a_i - q_i b_i，其中a_i和b_i是前面两个数，q_i是a_i除以b_i的商。

6. 由于d同时整除a和b，所以d也要整除a_i和b_i，因此d也要整除r_i。

7. 最后，当余数为0时，我们得到的除数就是a和b的最大公约数。由于d能整除a和b，所以d也能整除最大公约数。

综上所述，辗转相除法是一种正确的求解最大公约数的方法。

相关问题

C语言用辗转相除法求最大公约数

在C语言中，可以使用辗转相除法来求两个数的最大公约数。具体步骤如下：
1. 输入两个数a和b。
2. 判断a和b是否都不为0，如果是则继续，否则输出错误信息。
3. 如果a小于b，则交换a和b的值。
4. 用a除以b，得到余数c。
5. 如果c为0，则b就是最大公约数。
6. 如果c不为0，则用b除以c，得到余数d。
7. 重复步骤5和6，直到余数为0，此时b就是最大公约数。
8. 输出最大公约数b。

下面是C语言代码的实现：

#include <stdio.h>
int main() {
    int a, b, c, temp;
    printf("Please input two numbers:");
    scanf("%d %d", &a, &b);
    if (a && b != 0) {
        if (a < b) {
            temp = a;
            a = b;
            b = temp;
        }
        c = a % b;
        while (c != 0) {
            a = b;
            b = c;
            c = a % b;
        }
        printf("%d", b);
    } else {
        printf("Error");
    }
}

用辗转相除法求最大公约数编程

以下是Python代码示例：

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 测试
print(gcd(24, 36)) # 输出12

解释：该函数使用递归方式实现了辗转相除法，如果b等于0，则a就是最大公约数，否则继续递归调用gcd函数，传入参数b和a mod b。