擴展歐幾里得演算法（EXGCD）學習筆記

• 2021 年 3 月 15 日
• 筆記

0.前言

相信大家對於歐幾里得演算法都已經很熟悉了。再學習數論的過程中，我們會用到擴展歐幾里得演算法（exgcd），大家一定也了解過。這是本蒟蒻在學習擴展歐幾里得演算法過程中的思考與探索過程。

1.Bézout定理

擴展歐幾里得演算法利用歸納法，證明了Bézout定理。

Bézout定理：對於任意整數 \(a\),\(b\) ，存在一對整數 \(x\),\(y\)，滿足 \(ax+by=gcd(a,b)\)
在擴展歐幾里得的演算法中，我們求出 \(x\),\(y\) 的值。

2.證明

2.1 \(gcd\)

首先，我們來看一下 \(gcd\) 函數

int gcd (int a, int b) {
	if(b == 0) return a;
	else return gcd(b, a % b);
}

在第二行，也就是遞歸終止時，\(b=0\) 且 \(a=gcd(a,b)\)。 我們可以發現存在一對整數 \(x\),\(y\) 滿足條件 \(ax+by=gcd(a,b)\)。
將已知的值代入可得:\(ax+b*0=gcd(a,b)\)
∵\(a=gcd(a,b)\)
∴\(gcd(a,b)*x=gcd(a,b)\)
∴\(y\)在終止時可取任意值，\(x=1\)

2.2歸納法

我們在2.1中得到了 \(b=0\) 時的解。現在，我們用歸納法一步步得到最終解。當 \(b>0\) 時，我們假設 \(b*x\) 滿足條件 \(b*x+(a\,mod\,b*y)gcd(b,a\,mod\,b)\)(代入的值也正是我們平時進行gcd的轉移方程)
\(∵ bx+(a\,mod\,b)y=bx+[a-b(a/b)]y\)
\(∴ bx+(a\,mod\,b)y=bx+ay-by(a/b)\)
\(∴ bx+(a\,mod\,b)y=ay+bx-by(a/b)\)
\(∴ bx+(a\,mod\,b)y=ay+b[x-(a/b)y]\)
令 \(x_1=y\), \(y_1=x-(a\,mod\,b)y\),再代入已得到的式子，就能得到：
\(ax_1+by_1=gcd(a,b)\),所以可以得出Bézout定理成立。

3.程式碼實現

3.1思路簡述

我們的程式碼在截止條件上與 \(gcd\) 相同，都是 if(b == 0)時停止遞歸。我們在此基礎上再改變 \(x\) 和 \(y\) 的值。

3.2參考程式碼及注釋

大部分都按照前面的推導過程

int exgcd(int a, int b, int &x, int &y) { //x，y的初始值無關
	if(b == 0) {
		x = 1, y = 0;//改變x，y的值（y可取任意值）
		return a;
	} else {
		int tmp = exgcd(b, a % b, x, y);//保存下一次的最大公約數
		int z = x; //存儲上一次的x
		y = x; //及上文中的y1
		x = z - y * (a / b); //及上文中的x_1
		return tmp;//返回最大公約數
	}
}