扩展欧几里得算法求最大公约数

扩展欧几里得算法是用来求解两个数的最大公约数并计算贝祖等式的一种方法。其基本思想是通过递归用较小的数去除较大的数，直到两个数相等为止。具体步骤如下：

假设需要求解的两个数为a和b，其中a > b：

1. 用b去除a，得到a = qb + r，其中q为a除以b的商，r为余数。
2. 如果r等于0，则b即为最大公约数，结束。
3. 如果r不等于0，则继续用r去除b，得到b = pr + s，其中p为b除以r的商，s为余数。
4. 重复上述步骤，直到余数为0为止。此时，最大公约数即为上一步的余数。

在扩展欧几里得算法中，需要记录每一次的商和余数，用于计算贝祖等式。具体步骤如下：

1. 假设需要求解的两个数为a和b，其中a > b。
2. 用b去除a，得到a = qb + r，其中q为a除以b的商，r为余数。
3. 如果r等于0，则b即为最大公约数。此时，可以得到贝祖等式：b = gcd(a, b) = qs + rt，其中s = 0，t = 1。
4. 如果r不等于0，则继续用r去除b，得到b = pr + s，其中p为b除以r的商，s为余数。
5. 递归计算，得到gcd(a, b) = gcd(b, r) = qs' + rt'，其中s' = t，t' = s - pt。
6. 重复上述步骤，直到余数为0为止。此时，最大公约数即为上一步的余数。