擴展歐幾里德演演算法

擴展歐幾里德演演算法

擴展歐幾里德演演算法是用來在已知a, b求解一組x，y，使它們滿足貝祖等式： ax+by = gcd(a, b) =d（解一定存在，根據數論中的相關定理）。擴展歐幾里德常用在求解模線性方程及方程組中。

目錄

1歐幾里德演算法概述公式表述

2擴展演算法 pascal語言實現

歐幾里德演演算法

概述

歐幾里德演演算法又稱輾轉相除法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：

gcd函數就是用來求(a,b)的最大公約數的。

gcd函數的基本性質：

公式表述

證明：a可以表示成，則

假設d是a,b的一個公約數，則有

而，因此d|r

因此d是(b,a mod b)的公約數

假設d 是(b,a mod b)的公約數，則

但是

因此d也是(a,b)的公約數

因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證

擴展演演算法

對於不完全為 0 的非負整數 a，b，gcd（a，b）表示 a，b 的最大公約數，必然

存在整數對 x，y ，使得

pascal語言實現

求解 x，y的方法的理解

設。

1，顯然當。此時；

2，時

設;

根據樸素的歐幾里德原理有

則:

即:

說明：即為mod運算。[a/b]代表取小於的最大整數。

也就是

根據恆等定理得：

這樣我們就得到了求解 x,y 的方法：x，y 的值基於 x，y.

上面的思想是以遞歸定義的，因為 gcd 不斷的遞歸求解一定會有個時候，所以遞歸可以結束。

擴展歐幾里德演演算法

擴展歐幾里德演演算法是用來在已知a, b求解一組x，y使得(解一定存在，根據數論中的相關定理)。擴展歐幾里德常用在求解模線性方程及方程組中。下面是一個使用C++的實現：

把這個實現和Gcd的遞歸實現相比，發現多了下面的x,y賦值過程，這就是擴展歐幾里德演演算法的精髓。

可以這樣思考:

對於而言，我們求得 x, y使得

由於 (註：這裡的/是程序設計語言中的除法)

那麼可以得到:

因此對於a和b而言，他們的相對應的p，q分別是 y和()

使用擴展歐幾里德演演算法解決不定方程的辦法

對於不定整數方程，若,則該方程存在整數解，否則不存在整數解。

有種較為不嚴謹的方法證明，不過至少彌補了一點空白，望某些數論大師補充修改：

由於我們知道，存在一組x與y使得。

將等式兩邊同時乘以整數k，即。如果，則。

那麼可以令。這樣一來，就有。

若，由於（假設），所以不存在（m為整數），也就不存在。也就是說，不存在的整數解x與y。

所以，即只有當時，有正整數解。得證。

上面已經列出找一個整數解的方法，在找到的一組解后，的其他整數解滿足：

(其中t為任意整數)

至於的整數解，只需將的每個解乘上即可，但是所得解並不是該方程的所有解，找其所有解的方法如下：

在找到的一組解后，可以

得到的一組解的其他整數解滿足：

(其中t為任意整數)

p 、q就是的所有整數解。

編程時 exgcd 更多用於求解“中國剩餘定理”相關知識舉個例子比如n除以5餘2 除以13餘3 那麼n最小是多少，所有的n滿足什麼條件？

歐幾里德演演算法的擴展

擴展歐幾里德演演算法不但能計算(a，b)的最大公約數，而且能計算a模b及b模a的乘法逆元，用C語言描述如下：

擴展歐幾里德演演算法對於最大公約數的計算和普通歐幾里德演演算法是一致的。計算乘法逆元則顯得很難明白。

首先重複操作整除中的一個論斷：

如果，則存在m，n，使得，稱呼這種關係為a、b組合整數d，m，n稱為組合係數。當時，有，此時可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。

為了證明上面的結論，我們把上述計算中看成的迭代初始值，考察一組數，用歸納法證明：當通過擴展歐幾里德演演算法計算后，每一行都滿足

第一行：成立

第二行：成立

假設前k行都成立，考察第行

對於行和k行有

分別滿足：

根據擴展歐幾里德演演算法，假設

則：

則

得證

因此，當最終迭代計算到1時，有，顯然，是a模b的乘法逆元，是b模a的乘法逆元。

目錄