扩展欧几里得算法

（重定向自擴展歐幾里得演算法

${\displaystyle ax+by=\gcd(a,b).}$

${\displaystyle \left|a\right|(-x)+by=\gcd(|a|,b)}$${\displaystyle \left|a\right|}$为a的绝对值），然后令${\displaystyle x'=(-x)}$

算法和举例

{\displaystyle {\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{and}}\quad 0\leq r_{i+1}<|r_{i}|\\&\,\,\,\vdots \end{aligned}}}

{\displaystyle {\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\text{and }}0&\leq r_{i+1}<|r_{i}|\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned}}}

0 240 1 0
1 46 0 1
2 240 ÷ 46 = 5 2405 × 46 = 10 15 × 0 = 1 0 − 5 × 1 = −5
3 46 ÷ 10 = 4 464 × 10 = 6 04 × 1 = −4 1 − 4 × −5 = 21
4 10 ÷ 6 = 1 101 × 6 = 4 11 × −4 = 5 −5 − 1 × 21 = −26
5 6 ÷ 4 = 1 61 × 4 = 2 −41 × 5 = −9 21 − 1 × −26 = 47
6 4 ÷ 2 = 2 42 × 2 = 0 52 × −9 = 23 −26 − 2 × 47 = −120

证明

${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}}$

实现

def ext_euclid(a, b):
old_s, s = 1, 0
old_t, t = 0, 1
old_r, r = a, b
if b == 0:
return 1, 0, a
else:
while(r!=0):
q = old_r // r
old_r, r = r, old_r-q*r
old_s, s = s, old_s-q*s
old_t, t = t, old_t-q*t
return old_s, old_t, old_r


#include <bits/stdc++.h>
using namespace std;

int ext_euc(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}

int d = ext_euc(b, a % b, y, x);
y -= a / b * x;

return d;
}

int main()
{
int a, b, x, y;
cin >> a >> b;

ext_euc(a, b, x, y);
cout << x << ' ' << y << endl;
return 0;
}


参考资料

1. ^ 沈淵源. 數論輕鬆遊 (PDF). [2017-09-25]. （原始内容存档 (PDF)于2021-01-24） （中文（臺灣））.
2. ^ Kenneth H.Rosen; 徐六通 杨娟 吴斌 译. 离散数学及其应用 原书第七版. : 232页. ISBN 978-7-111-45382-6.