辗转相除求19x+72y = 1
时间: 2024-05-30 18:08:18 浏览: 13
我们可以使用扩展欧几里得算法来解决这个问题。该算法可以在求两个整数的最大公约数的同时,找到一组整数解,使得这两个整数的线性组合等于它们的最大公约数。具体步骤如下:
首先,我们需要对较大的数进行求模操作,以确保两个数都为正整数。因为 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。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)