用辗转相除求799x+10752y = 1

我们可以使用扩展欧几里得算法（辗转相除法的扩展）来求解这个方程。首先，我们用辗转相除法求出10752和799的最大公约数：

10752 = 13 * 799 + 445
  799 = 1 * 445 + 354
  445 = 1 * 354 + 91
  354 = 3 * 91 + 91
   91 = 1 * 91 + 0

所以，最大公约数为91。接下来，我们使用扩展欧几里得算法来求解方程799x + 10752y = 1。

根据扩展欧几里得算法的过程，我们得到以下的表格：

i    qi   xi   yi
------------------
0          1    0
1          0    1
2    13    1   -13
3     1   -13   174
4     1   187 -2491
5     4 -7475 99313

因此，方程的一组解为x = -7475，y = 99313。同时，我们可以得到方程的通解为：

x = -7475 + 11760k
y = 99313 - 15739k

其中k是任意整数。

相关问题

辗转相除求19x+72y = 1

我们可以使用扩展欧几里得算法来解决这个问题。该算法可以在求两个整数的最大公约数的同时，找到一组整数解，使得这两个整数的线性组合等于它们的最大公约数。具体步骤如下：

首先，我们需要对较大的数进行求模操作，以确保两个数都为正整数。因为 19 和 72 都是正整数，我们可以先将方程变形为 72y ≡ 1 (mod 19)。

然后，我们可以使用扩展欧几里得算法来解决这个同余方程。该算法需要递归地计算辗转相除的余数和商，直到余数为 0 为止。在每一步中，我们需要维护两个变量 x 和 y，它们表示上一步的商和余数的线性组合。具体步骤如下：

1. 初始化 x1 = 1, y1 = 0, x2 = 0, y2 = 1。
2. 计算商 q = 72 // 19 = 3, 余数 r = 72 % 19 = 15。
3. 如果余数 r 等于 0，停止递归，返回最大公约数 d = 19 和 x2 的值。
4. 否则，更新 x1, y1, x2, y2 的值：
- x1, y1 = x2, y2
- x2, y2 = x1 - q * x2, y1 - q * y2
5. 递归调用步骤 2-4，将 r 替换为 19，将 19 替换为 r。

按照上述步骤，我们可以得到：

72 = 19 * 3 + 15
19 = 15 * 1 + 4
15 = 4 * 3 + 3
4 = 3 * 1 + 1
3 = 1 * 3 + 0

所以最大公约数 d = 1。最后一步的余数为 0，表明我们已经找到了一组整数解，使得 19 和 72 的线性组合等于它们的最大公约数。根据递推公式，我们可以得到：

1 = 4 - 3 * 1
= 4 - (15 - 4 * 3) * 1
= 4 * 4 - 15 * 1
= 4 * (19 - 15 * 1) - 15 * 1
= 4 * 19 - 19 * 1 * 15

所以一组满足条件的整数解为 x = 4, y = -15。即 19 * 4 + 72 * (-15) = 1。

编写一个函数gcd1(x,y),用辗转相除法求x,y的最大公约数。

下面是使用辗转相除法求最大公约数的 Python3 代码实现：

def gcd1(x, y):
    while y != 0:
        r = x % y
        x = y
        y = r
    return x

函数中，每次循环使用辗转相除法求得余数r，然后将y赋值为原来的x，x赋值为原来的y，继续循环直到y等于0为止，此时x的值就是x和y的最大公约数。