User: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)