# 扩展欧几里得算法

## 算法和举例

{\displaystyle {\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{且}}\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{且}}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 {\begin{pmatrix}240&46\\1&0\\0&1\end{pmatrix}}\rightarrow {\begin{pmatrix}10&46\\1&0\\-5&1\end{pmatrix}}\rightarrow {\begin{pmatrix}10&6\\1&-4\\-5&21\end{pmatrix}}\rightarrow {\begin{pmatrix}4&6\\5&-4\\-26&21\end{pmatrix}}\rightarrow {\begin{pmatrix}4&2\\5&-9\\-26&47\end{pmatrix}}}$[3]

## 证明

${\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; 徐六通 杨娟 吴斌 译. 离散数学及其应用 原书第七版. 2015-01-01: 232页. ISBN 978-7-111-45382-6.
3. ^ 張慧玲. 介紹多項式帶餘除法的矩陣形式及其應用. 太原大學教育學院學報. 2014, (1): 第103–105頁 [2016-03-02]. （原始内容存档于2022-12-14）.