擴充歐幾裡得算法

• 裴蜀定理
• 擴充歐幾裡得算法
• • 最小正整數解

裴蜀定理

裴蜀定理：對任意的整數a、b，關于未知數x、y的線性丢番圖方程ax+by=m，當且僅當m是gcd(a,b)的整數倍時方程有解。

該方程稱為裴蜀等式。

證明 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)時有解：

設 d = g c d ( a , b ) d=gcd(a,b) d=gcd(a,b)，則有 d ∣ a d\mid a d∣a， d ∣ b d\mid b d∣b，是以 ∀ x , y ∈ Z , d ∣ a x + b y \forall x,y\in\mathbb{Z},d\mid ax+by ∀x,y∈Z,d∣ax+by，即 d ∣ m d\mid m d∣m

設 s s s是最小的 m m m，則有 d ∣ s d\mid s d∣s

令 q = ⌊ a s ⌋ , r = a % s = a − q s = a − q ( a x + b y ) = a ( 1 − q x ) + b ( − q y ) q=\lfloor\frac{a}{s}\rfloor,r=a\%s=a-qs=a-q(ax+by)=a(1-qx)+b(-qy) q=⌊sa​⌋,r=a%s=a−qs=a−q(ax+by)=a(1−qx)+b(−qy)，可見 r r r也是 x , y x,y x,y的線性組合，因為 s s s是 x , y x,y x,y線性組合的最小值， 0 ≤ r &lt; s 0\le r&lt;s 0≤r<s，是以 r = 0 r=0 r=0，則有 s ∣ a s\mid a s∣a

同理有 s ∣ b s\mid b s∣b，是以 s s s是 a , b a,b a,b的公約數，而 d d d是 a , b a,b a,b的最大公約數，是以有 s ∣ d s\mid d s∣d

綜上， s = d s=d s=d

證明 a x + b y = m ax+by=m ax+by=m有解的充要條件是 g c d ( a , b ) ∣ m gcd(a,b)\mid m gcd(a,b)∣m：

充分性：若 g c d ( a , b ) ∣ m gcd(a,b)\mid m gcd(a,b)∣m，則 m = k ∗ g c d ( a , b ) m=k*gcd(a,b) m=k∗gcd(a,b)，設 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)的一組解為 x 0 , y 0 x_0,y_0 x0​,y0​，顯然 k x 0 , k y 0 kx_0,ky_0 kx0​,ky0​是 a x + b y = m ax+by=m ax+by=m的一組解。

必要性：設 d = g c d ( a , b ) d=gcd(a,b) d=gcd(a,b)，則有 d ∣ a d\mid a d∣a， d ∣ b d\mid b d∣b，是以 ∀ x , y ∈ Z , d ∣ a x + b y \forall x,y\in\mathbb{Z},d\mid ax+by ∀x,y∈Z,d∣ax+by，即 d ∣ m d\mid m d∣m

擴充歐幾裡得算法

顯然，當m等于k倍的gcd(a,b)時，裴蜀等式的解是m恰好等于gcd(a,b)時解的k倍。

是以，對任意的裴蜀等式，我們隻需考察m恰好等于gcd(a,b)時裴蜀等式的解。

擴充歐幾裡得算法就是用來求當m恰好等于gcd(a,b)時裴蜀等式的解的一種算法。

設 a ∗ x 1 + b ∗ y 1 = g c d ( a , b ) ， b ∗ x 2 + ( a % b ) ∗ y 2 = g c d ( b , a % b ) a*x_1+b*y_1=gcd(a,b)，b*x_2+(a\%b)*y_2=gcd(b,a\%b) a∗x1​+b∗y1​=gcd(a,b)，b∗x2​+(a%b)∗y2​=gcd(b,a%b)

由歐幾裡得算法（輾轉相除法）可知， g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a\%b) gcd(a,b)=gcd(b,a%b)

∴ a ∗ x 1 + b ∗ y 1 = b ∗ x 2 + ( a % b ) ∗ y 2 \therefore a*x_1+b*y_1=b*x_2+(a\%b)*y_2 ∴a∗x1​+b∗y1​=b∗x2​+(a%b)∗y2​

又 ∵ a % b = a − ⌊ a b ⌋ ∗ b \because a\%b=a-\lfloor\frac{a}{b}\rfloor*b ∵a%b=a−⌊ba​⌋∗b

∴ a ∗ x 1 + b ∗ y 1 = b ∗ x 2 + a ∗ y 2 − ⌊ a b ⌋ ∗ b ∗ y 2 \therefore a*x_1+b*y_1=b*x_2+a*y_2-\lfloor\frac{a}{b}\rfloor*b*y_2 ∴a∗x1​+b∗y1​=b∗x2​+a∗y2​−⌊ba​⌋∗b∗y2​

移項得， a ∗ ( x 1 − y 2 ) + b ∗ ( y 1 − x 2 + ⌊ a b ⌋ ∗ y 2 ) = 0 a*(x_1-y_2)+b*(y_1-x_2+\lfloor\frac{a}{b}\rfloor*y_2)=0 a∗(x1​−y2​)+b∗(y1​−x2​+⌊ba​⌋∗y2​)=0

是以， x 1 = y 2 , y 1 = x 2 − ⌊ a b ⌋ ∗ y 2 x_1=y_2, y_1=x_2-\lfloor\frac{a}{b}\rfloor*y_2 x1​=y2​,y1​=x2​−⌊ba​⌋∗y2​就是一組解

根據上面的推導可知：對于一組線性方程ax+by=gcd(a,b)，它的一組解 x 1 , y 1 x_1,y_1 x1​,y1​可以通過另一組線性方程bx+(a%b)y=gcd(b, a%b)的一組解 x 2 , y 2 x_2,y_2 x2​,y2​計算得出。這恰好滿足遞歸的條件。

例如，當求(a,b)為(15,8)的解時，我們需要先計算(8,7)的解，進而需要先計算(7,1)的解，再進而需要先計算(1,0)的解。

顯然，遞歸的邊界是b=0

當b等于0時，方程變為ax=gcd(a,0)，又因為gcd(a,0)=a，是以方程變為ax=a，解為x=1

這樣，我們運用遞歸算法就可以求出任意一組線性方程ax+by=gcd(a,b)的一組解：

先不斷遞推，一定能推至b=0，b=0時解是已知的，回溯時用已經知道的 x 2 , y 2 x_2,y_2 x2​,y2​，計算上一層的 x 1 , y 1 x_1,y_1 x1​,y1​,這樣就可以算出最開始的解。

代碼如下：

void exgcd(int a, int b, int &x, int &y)
{
    if (b == 0) x = 1;
    else
    {
    	exgcd(b, a % b, y, x);
   		y -= a / b * x; 
   	}
}
           

該算法在遞歸中巧妙地運用了引用類型，使得代碼無比簡潔。

由于x，y參數是引用類型，是以在若幹層遞歸的過程中，我們改變的一直是同一塊記憶體中存儲的數值。

這行代碼是整個算法的核心。根據前文的推導，将a、b變為b、a%b很好了解，那麼為什麼要颠倒x，y的次序呢？

還是根據前文的推導 x 1 = y 2 x_1=y_2 x1​=y2​，也就是說目前層的x和下一層的y相等，是以我們隻需要将目前層的x引用傳給下一層的y引用。引用可以了解為一個變量的别名，颠倒x，y的次序可以了解成：目前層的x和下一層的y是同一個變量的不同名稱，他們其實是一個變量。 這樣就做到了遞歸回溯後 x 1 = y 2 x_1=y_2 x1​=y2​

那麼 y 1 = x 2 − ⌊ a b ⌋ ∗ y 2 y_1=x_2-\lfloor\frac{a}{b}\rfloor*y_2 y1​=x2​−⌊ba​⌋∗y2​是如何做到的呢？

由于x，y在遞歸的上下層中次序颠倒，使得回溯後 x 1 = y 2 x_1=y_2 x1​=y2​，同樣也有 y 1 = x 2 y_1=x_2 y1​=x2​

即在執行這行代碼後 x 1 = y 2 x_1=y_2 x1​=y2​， y 1 = x 2 y_1=x_2 y1​=x2​

那麼 y 1 = x 2 − ⌊ a b ⌋ ∗ y 2 y_1=x_2-\lfloor\frac{a}{b}\rfloor*y_2 y1​=x2​−⌊ba​⌋∗y2​就變成了 y 1 = y 1 − ⌊ a b ⌋ ∗ x 1 y_1=y_1-\lfloor\frac{a}{b}\rfloor*x_1 y1​=y1​−⌊ba​⌋∗x1​

于是就有了下面一行代碼

要注意的是，裴蜀等式有解時一定有無窮多的解，這個算法求得的隻是其中一組解。

代碼應用如下：

#include<iostream>
using namespace std;
void exgcd(int a, int b, int& x, int& y)
{
	if (b == 0) x = 1;
	else
	{
		exgcd(b, a % b, y, x);
		y -= a / b * x;
	}
}
int main()
{
	int a, b, x, y;
	x = 0;
	y = 0;
	cin >> a >> b;
	exgcd(a, b, x, y);
	cout << x << " " << y << endl;
	return 0;
}
           

最小正整數解

int min_x = (x % b + b) % b;//x的最小正整數解
int min_y = (y % a + a) % a;//y的最小正整數解
cout << min_x << " " << (x - min_x) / b * a + y << endl;//x的最小正整數解與其對應的y
cout << (y - min_y) / a * b + x << " " << min_y;//y的最小正整數解與其對應的x
           

證明：

不妨設 x 0 x_0 x0​為 x x x的最小正整數解， y 0 y_0 y0​為 x 0 x_0 x0​對應的 y y y

∵ a ∗ x + b ∗ y = g c d ( a , b ) \because a*x+b*y=gcd(a,b) ∵a∗x+b∗y=gcd(a,b)

∴ a ∗ x + a ∗ b ∗ k + b ∗ y − a ∗ b ∗ k = g c d ( a , b ) \therefore a*x+a*b*k+b*y-a*b*k=gcd(a,b) ∴a∗x+a∗b∗k+b∗y−a∗b∗k=gcd(a,b)

合并得， a ∗ ( x + k ∗ b ) + b ∗ ( y − k ∗ a ) = g c d ( a , b ) a*(x+k*b)+b*(y-k*a)=gcd(a,b) a∗(x+k∗b)+b∗(y−k∗a)=gcd(a,b)

是以，所有整數解都可寫為 x = x 0 + k ∗ b , y = y 0 − k ∗ a x=x_0+k*b,y=y_0-k*a x=x0​+k∗b,y=y0​−k∗a的形式，即x多一個b，y就要少一個a

顯然，若 x x x為正數， x % b = ( x 0 + k ∗ b ) % b = x 0 x\%b=(x_0+k*b)\%b=x_0 x%b=(x0​+k∗b)%b=x0​

若x為負數， x % b = [ ( x 0 − b ) + ( k + 1 ) ∗ b ] % b = x 0 − b x\%b=[(x_0-b)+(k+1)*b]\%b=x_0-b x%b=[(x0​−b)+(k+1)∗b]%b=x0​−b

∴ x % b + b = x 0 或 x 0 + b \therefore x\%b+b=x_0或x_0+b ∴x%b+b=x0​或x0​+b

∴ ( x % b + b ) % b = x 0 \therefore(x\%b+b)\%b=x_0 ∴(x%b+b)%b=x0​

綜上所述 x x x的最小正整數解為 ( x % b + b ) % b (x\%b+b)\%b (x%b+b)%b

同理可證 y y y的最小正整數解為 ( y % a + a ) % a (y\%a+a)\%a (y%a+a)%a

注意：一般情況下，x的最小正整數解與y的最小正整數解并不是一組解。