# 扩展欧几里得算法

## 维基百科，自由的百科全书

${\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 <stdio.h>

//這裡用了int型別，所支持的整數範圍較小，且本程序僅支持非負整數，可能缺乏實際用途，僅供展示。
struct EX_GCD { //s,t是裴蜀等式中的係數，gcd是a,b的最大公因數
int s;
int t;
int gcd;
};

struct EX_GCD extended_euclidean(int a, int b) {
struct EX_GCD ex_gcd;
if (b == 0) { //b=0時直接結束求解
ex_gcd.s = 1;
ex_gcd.t = 0;
ex_gcd.gcd = 0;
return ex_gcd;
}
int old_r = a, r = b;
int old_s = 1, s = 0;
int old_t = 0, t = 1;
while (r != 0) { //按擴展歐基里德算法進行循環
int q = old_r / r;
int temp = old_r;
old_r = r;
r = temp - q * r;
temp = old_s;
old_s = s;
s = temp - q * s;
temp = old_t;
old_t = t;
t = temp - q * t;
}
ex_gcd.s = old_s;
ex_gcd.t = old_t;
ex_gcd.gcd = old_r;
return ex_gcd;
}

int main(void) {
int a, b;
printf("Please input two integers divided by a space.\n");
scanf("%d%d", &a, &b);
if (a < b) { //若a < b，則交換a與b以便求解
int temp = a;
a = b;
b = temp;
}
struct EX_GCD solution = extended_euclidean(a, b);
printf("%d*%d+%d*%d=%d\n", solution.s, a, solution.t, b, solution.gcd);
printf("Press any key to exit.\n");
getchar();
getchar();
return 0;
}


## 参考资料

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

## 参考文献

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 算法导论, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.
• Christof Paar,Jan Pelzl著 马小婷 译. 深入浅出密码学, 清华大学出版社, ISBN 9787302296096. Pages 151-155 6.3.2 扩展的欧几里得算法