采用Euclid（欧几里德）算法来求最大公因子，其算法是： (1) 输入两个正整数m和n。 (2) 用m除以n，余数为r，如果r等于0，则n是最大公因子，算法结束，否则(3)。 (3) 把n赋给m，把r赋给n，转(2)。

例如，求出24和16的最大公因子：

(1) 输入m=24，n=16。

(2) 用24除以16，余数为8，因为r不等于0，所以转(3)。

(3) 把n=16赋给m，把r=8赋给n，转(2)。

(2) 用16除以8，余数为0，因为r等于0，所以n=8是最大公因子。

所以，24和16的最大公因子是8。

相关问题

扩展欧几里德算法求模逆元

扩展欧几里德算法可以用来求解模逆元，对于给定的正整数 a 和模数 m，模逆元 x 是满足 ax ≡ 1 (mod m) 的整数 x。以下是求解模逆元的步骤：

1. 使用扩展欧几里德算法求解 a 和 m 的最大公约数 gcd(a, m) 和一对整数 x0 和 y0，使得 ax0 + my0 = gcd(a, m)。

2. 如果 gcd(a, m) 不为 1，则 a 在模 m 下没有逆元。

3. 如果 gcd(a, m) 为 1，则 x0 是 a 在模 m 下的逆元。因为 ax0 ≡ 1 (mod m)，所以 x0 就是满足条件的 x。

4. 如果 x0 是负数，则可以加上 m 使其变为正数。

下面是求解模逆元的 Python 代码实现：

def ext_euclid(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = ext_euclid(b, a % b)
        return d, y, x - (a // b) * y

def mod_inverse(a, m):
    d, x, y = ext_euclid(a, m)
    if d != 1:
        return None  # a 在模 m 下没有逆元
    else:
        x %= m
        if x < 0:
            x += m
        return x

在上述代码中，ext_euclid 函数是扩展欧几里德算法的实现，mod_inverse 函数调用了 ext_euclid 函数来求解模逆元。如果 a 在模 m 下没有逆元，则返回 None，否则返回满足条件的 x 值。