使用者:Gqqnb/筆記/計算機安全與數論

整係數二元一次方程之整數解、最大公約數、歐幾里德算法

通常談到最大公因數時, 我們都會提到一個非常基本的事實: 給予二整數 a 與 b, 必存在有整數 x 與 y 使得ax + by = gcd(a,b)。

有兩個數a,b，對它們進行輾轉相除法，可得它們的最大公約數——這是眾所周知的。然後，收集輾轉相除法中產生的式子，倒回去，可以得到ax+by=gcd(a,b)的整數解。

例如，用類似輾轉相除法，求47x+30y=1的整數解。

• 47=30*1+17
• 30=17*1+13
• 17=13*1+4
• 13=4*3+1

然後把它們改寫成「餘數等於」的形式

• 17=47*1+30*(-1) //式1
• 13=30*1+17*(-1) //式2
• 4=17*1+13*(-1) //式3
• 1=13*1+4*(-3)

然後把它們「倒回去」

• 1=13*1+4*(-3) //應用式3
• 1=13*1+[17*1+13*(-1)]*(-3)
• 1=13*4+17*(-3) //應用式2
• 1=[30*1+17*(-1)]*4+17*(-3)
• 1=30*4+17*(-7) //應用式1
• 1=30*4+[47*1+30*(-1)]*(-7)
• 1=30*11+47*(-7)

得解x=-7, y=11。

這個方法疑似就是擴展歐幾里德算法。

模運算

例題1：試求同餘方程 x + 11 ≡ 7 (mod 17) 的解。

解：x ≡ 7 - 11 ≡ -4 ≡ 13 (mod 17) 。 答案若寫成負的並沒什麼錯誤。 但當我們在模 n 之下工作時，通常將最後的答案表示為介於 0 與 n - 1 之間的整數。

除法原理：在模 n 下，若要兩邊同除以某數，該數須與 n 互質。

例題2：試求同餘方程 4x + 11 ≡ 7 (mod 17) 的解。

解：4x ≡ 7 - 11 ≡ -4 (mod 17), 所以 x ≡ -1 ≡ 16 (mod 17)。 被 4 除沒問題, 因為 gcd(4,17) = 1。

例題3：試求同餘方程 3x +12 ≡ 17 (mod 21) 的解。

讀者可以自行嘗試一下，再繼續看本文。這些同餘方程可以轉化為整係數二元一次方程之整數解的問題。

• 3x +12 ≡ 17 (mod 21)
• => 3x+12=17+21y
• => 3x+21y=5 （y的正負無所謂）。

讀者可能還沒試到解，其實，貝祖等式說因為3和21的最大公約數是3，不是2的倍數，所以此方程無解。

同餘方程的線性表示

對於任意的同餘方程a ≡ b (mod n)，都有 ${\begin{cases}a=nx+m\\b=ny+m\end{cases}}$（根據定義，a,b同餘，m就是它們在模n下的餘數），然後a-b=(x-y)n => a-b=kn。

例題4：試求同餘方程 5x + 7 ≡ 11 (mod 17) 的解。

解：5x ≡ 4 (mod 17)。兩邊可以除以5，因為5和17互質。但${\frac {4}{5}}$在模 17 之下是什麼意思呢? 我們知道 4 ≡ 21 ≡ 38 ≡ 55 ≡ ··· (mod 17), 所以 5x ≡ 4 (mod 17) 與 5x ≡ 55 (mod 17) 是一樣的。恰好55又是5的倍數，所以現在我們可除以 5 得到 x ≡ 11 (mod 17) 為其答案。 注意 4 ≡ 11* 5 (mod 17), 所以在模 17 之下 11 就如同是${\frac {4}{5}}$一樣。到了這裡，就可以引入模反元素這個概念了。

模反元素

例題4也可以這麼算：不知怎麼的，我們知道了5 * 7 ≡ 1 (mod 17)。就如同$5\times {\frac {1}{5}}=1$，${\frac {1}{5}}$是5的乘法逆元一樣，我們把7稱為5在模17下的模反元素。

疑似模反元素可以為負數，只要絕對值小於模就可以了（可以參考餘數的範圍）；但人們往往喜歡把它「正過來」。

求模反元素

已知a，求a在模b下的模反元素。

設有ax ≡ 1 (mod b)，然後把它寫成線性方程 ax-1=by => ax+by=1。

已知擴展歐幾里德算法可求形如ax+by=1的方程的整數解，於是ExtendedGCD(a,b)={1,x,y}，得模反元素為x。

相關條目

• 餘數

參考

Diophantine Equation: ax+by=gcd(a,b)