# 擴展歐幾里得算法

${\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] （中文（台灣）‎）.
2. ^ Kenneth H.Rosen; 徐六通 楊娟 吳斌 譯. 離散數學及其應用 原書第七版. : 232頁. ISBN 978-7-111-45382-6.