模算術
介紹
模算術與素數以一種有趣的方式聯絡在一起。
模算術是一個系統,其中所有小於某個正整數(例如,n)的數字都被使用。所以,如果你開始計數,你會從 0、1、2、3、...、n - 1 開始,但你不會計算 n,而是從 0 重新開始。而原本的 n + 1 現在是 1,原本的 n + 2 現在是 2。一旦達到 2n,數字會再次重置為 0,依此類推。模算術也被稱為時鐘算術,因為我們只使用 12 個數字來顯示標準時間。在時鐘上,我們從 1 開始,而不是 0,一直到 12,然後從 1 重新開始。因此有了時鐘算術這個名字。
這個序列也延續到了原本的負數。原本的 -1 現在是 n - 1。例如,考慮模 7 算術,它就像普通算術一樣,除了我們只使用 0、1、2、3、4、5 和 6。如果我們看到一個超出此範圍的數字,我們就會加上 7(或者減去 7),直到它落入該範圍。
如上所述,模算術與普通算術並沒有太大區別。例如,在模 7 算術中,我們有



以及

我們對負數進行了一些計算。考慮 5 × -6。由於 -6 不在 0 到 6 的範圍內,我們需要給它加上 7 直到它落在範圍內。而 -6 + 7 = 1。因此,在模 7 算術中,-6 = 1。在上面的例子中,我們證明了 5 × -6 = -30 = 5,但 5 × 1 = 5。所以,我們在使用 -6 代替 1 的時候並沒有造成任何傷害。為什麼?
注意 - 負數:-3 的首選表示形式是 4,因為 -3 + 7 = 4,但在計算中使用 -3 或 4 都能得到相同的結果,只要我們將最終答案轉換為 0 到 6 之間的數字(包括 0 和 6)。
練習
在模 11 中求
1.
- -1 × -5
2.
- 3 × 7
3. 計算 2 的前 10 次方
- 21, 22, 23, ... , 210
你發現了什麼?
使用 2 的冪求
- 61, 62, 63, ... , 610
你再次發現了什麼?
4.

即,透過試錯(或其他方法)找到所有滿足 x2 = 4 (mod 11) 的數字 x。有兩個解,找到它們。
5.

即,找到所有滿足 x2 = 9 (mod 11) 的數字 x。有兩個解,找到它們。
逆元
考慮一個數字 n,n 的逆元是指與 n 相乘得到 1 的數字。例如,如果我們要解以下方程

(mod 7) 用於明確我們進行的是模 7 算術。我們要想辦法消除 5。將它乘以某個東西使其變為 1 可以解決問題。請注意,

因為 3 乘以 5 等於 1,所以我們說 3 是 5 在模 7 中的逆元。現在我們將等式兩邊都乘以 3
|
|
|
|
|
|
|
|
|
|
|
因此,x = 2 模 7 是所需的解。
定義(逆)
- (一個數)x 的逆是另一個數y,使得xy = 1。我們用x-1 或 1/x 表示x 的逆。
逆是唯一的
從上面我們知道 5 的逆是 3,但是 5 是否還有其他的逆?答案是否定的。實際上,在任何合理的數字系統中,一個數字只能有一個逆。我們可以從下面的證明中看到這一點
假設n 有兩個逆b 和c

從上面的論證中,n 的所有逆必須相等。因此,如果數字n 有逆,則該逆必須是唯一的。
任何模n 運算的一個有趣性質是數字n - 1 的逆是它本身。也就是說,(n - 1) × (n - 1) = 1 (mod n),或者我們可以寫成 (n - 1)2 = (-1)2 = 1 (mod n)。證明留作本節末尾的練習。
逆的存在
並非每個數字在每個模運算中都有逆。例如,3 在模 6 運算中沒有逆,即我們找不到一個數字x 使得 3x = 1 模 6(讀者可以很容易地驗證)。
考慮模 15 運算,並注意 15 是合數。我們知道 1 的逆是 1,14 的逆是 14。但是 3、6、9、12、5 和 10 呢?它們都沒有逆!注意,它們每個都與 15 有一個公因數!
例如,我們證明了 3 在模 15 運算中沒有逆。假設 3 有一個逆x,那麼我們有

我們將從模運算跳躍到有理數運算。如果 3x = 1 在模 15 運算中,那麼

對於某個整數k。現在我們將兩邊都除以 3,得到

但這不可能,因為我們知道x 是一個整數,而不是分數。因此,3 在模 15 運算中沒有逆。要證明 10 沒有逆更難,留作練習。
我們現在將陳述關於模運算中逆存在的定理。
定理
- 如果n 是素數,則每個數字(除了 0)在模n 運算中都有逆。
類似地
- 如果n 是合數,則每個與n 沒有公因數的數字都有逆。
有趣的是,除法 與逆的概念密切相關。考慮以下表達式

計算上述表示式的常規方法是找到 3 的逆(是 5)。所以

我們將 3 的逆寫成 1/3,所以我們將乘以 3-1 看作除以 3,得到

注意,我們得到了相同的答案!實際上,如果逆存在,除法方法將始終有效。
然而,在不同的模系統中的表示式將產生錯誤的答案,例如

我們不會得到 2,因為 3-1 在模 9 運算中不存在,所以我們不能使用除法方法。
練習
1. 8 在模 16 運算中是否有逆元?如果沒有,為什麼?
2. 如果 x 存在,求 x 模 7。






3. 用兩種方法計算 x,分別是 求逆元 和 除法

4. (技巧)求 x

5. 求所有模 n 的逆元(n ≤ 19)
互質和最大公約數
如果兩個數的最大公約數 (gcd) 為 1,則稱這兩個數互質。例如,21 和 55 都是合數,但它們互質,因為它們的最大公約數為 1。換句話說,它們除了 1 之外沒有其他公約數。
有一個快速巧妙的方法來計算兩個數的最大公約數,稱為歐幾里得演算法。讓我們用幾個例子來說明。
示例 1
- 求 21 和 49 的最大公約數。
我們建立一個兩列表,其中兩個數中較大的數在右側,如下所示。
現在我們計算 49 模 21 的結果,即 7,並將它放在第二行 較小數 列中,並將 21 放入 較大數 列中。
對第二行執行相同的操作,生成第三行。
只要我們看到 較小數 列中出現數字 0,我們就知道相應的 較大數 是我們開始的兩個數的最大公約數,即 7 是 21 和 49 的最大公約數。這個 演算法 稱為歐幾里得演算法。
示例 2
- 求 31 和 101 的最大公約數。
| 較小數 | 較大數 |
| 31 | 101 |
| 8 | 31 |
| 7 | 8 |
| 1 | 7 |
| 0 | 1 |
示例 3
- 求 132 和 200 的最大公約數。
| 較小數 | 較大數 |
| 132 | 200 |
| 68 | 132 |
| 64 | 68 |
| 4 | 64 |
| 0 | 4 |
重要說明
- 最大公約數不一定是素數。
- 兩個不同素數的最大公約數為 1。換句話說,兩個不同的素數總是互質的。
練習
1. 判斷以下數字集合是否互質
- 5050 5051
- 59 78
- 111 369
- 2021 4032
2. 求 15、510 和 375 的最大公約數
資訊 -- 演算法
演算法是對一系列操作的逐步描述,當正確執行時,可以完成一項任務。有用於尋找素數、判斷兩個數是否互質、求逆元以及許多其他目的的演算法。
你將在本章 數學程式設計 中學習如何在計算機上實現我們已經看到的某些演算法。
求逆元
讓我們從另一個角度重新審視逆元的概念。事實上,我們將提供一個萬無一失的方法來求任何數的逆元。讓我們考慮
- 5x = 1 (mod 7)
我們知道 x 是 5 的逆元,我們可以很快地算出它是 3。但 x = 10 也是一個解,x = 17、24、31、... 7n + 3 也是解。所以有無限多個解;因此,我們說 3 等價於 10、17、24、31 等等。這是一個至關重要的觀察結果。
現在讓我們考慮

這裡引入了一個新的符號,它是帶有三個而不是兩個橫線的等號。它是“等價”符號;上面的語句應該讀作“216x 等價於 1”,而不是“216x 等於 1”。從現在開始,我們將使用等價符號表示模運算,使用等號表示普通運算。
回到示例,我們知道 x 存在,因為 gcd(811,216) = 1。上面的問題在於,沒有快速的方法來確定 x 的值!我們知道最好的方法是將 216 乘以 1、2、3、4... 直到得到答案,最多需要 811 次計算,對於人類來說太繁瑣了。但有一個更好的方法,我們已經多次觸及它了!
我們注意到我們可以像以前一樣“跳躍”到有理數學中

我們再次跳躍到有理數學中

我們再跳一次

現在模式很清楚了,我們將從頭開始,以確保過程不中斷

現在我們要做的就是選擇一個f的值,並將其代回以找到a!記住a是216模811的逆。我們選擇f = 0,因此e = 1,d = 13,c = 40,b = 53,最後a = 199!如果f被選擇為1,我們將得到一個不同的a值。
那些非常敏銳的讀者應該已經注意到這只是歐幾里得最大公因數演算法的逆過程。
以下是這種巧妙方法在實際應用中的更多示例
示例 1
找到a的最小正值

選擇d = 0,因此a = 49。
示例 2 找到a的最小正值

選擇e = 0,因此a = -152 = 669
示例 3 找到a的最小正值

設定i = 0,則a = -21 = 34。為什麼對於這兩個如此小的數字,這個方法如此緩慢?你對係數能說什麼?
示例 4 找到a的最小正值

現在d不是一個整數,因此21在模102中沒有逆。
我們到目前為止討論的是如何找到以下形式的方程的整數解
- ax + by = 1
其中x和y是未知數,a和b是兩個給定的常數,這些方程被稱為線性丟番圖方程。有趣的是,有時沒有解,但如果存在解,則意味著存在無限多個解。
丟番圖方程
在模算術部分,我們陳述了一個定理,該定理指出如果gcd(a,m) = 1,那麼a-1(a的逆)存在於模m中。不難看出,如果p是素數,那麼對於所有小於p的b,gcd(b,p) = 1,因此我們可以說在模p中,除了0之外的每個數字都有逆。
我們還展示瞭如何找到任何元素模p的逆。事實上,在模算術中找到一個數字的逆相當於求解一種被稱為丟番圖方程的方程。丟番圖方程是以下形式的方程
- ax + by = d
其中x和y是未知數。
舉個例子,我們應該嘗試找到216在模811中的逆。設216的逆為x,我們可以寫成

我們可以將上面的公式改寫成日常算術形式

這屬於丟番圖方程的形式。
現在我們將會使用兩種方法來解決上面的問題:一種是不優雅的方法,另一種則是優雅的方法(使用神奇表格)。
上面提到的兩種方法都使用歐幾里得演算法來求兩個數的最大公約數。事實上,最大公約數與逆元的概念密切相關。讓我們將歐幾里得演算法應用於 216 和 811 這兩個數字。但是這一次,我們需要儲存更多細節;更具體地說,我們需要設定一個名為 PQ 的附加列,代表部分商。部分商只是一個技術術語,表示“n 除以 m 的結果是多少”,例如:3 和 19 的部分商是 6,4 和 21 的部分商是 5,最後一個例子 7 和 49 的部分商是 7。
表格顯示三個 216 除以 811 餘 163,或者用符號表示為
- 811 = 3×216 + 163。
讓我們繼續
| 較小數 | 較大數 | PQ |
| 216 | 811 | 3 |
| 163 | 216 | 1 |
| 53 | 163 | 3 |
| 4 | 53 | 13 |
| 1 | 4 | 4 |
| 0 | 1 | |
從表格中我們可以得到以下表達式:
- 811 = 3× 216 + 163
- 216 = 1× 163 + 53
- 163 = 3× 53 + 4
- 53 =13× 4 + 1
現在我們可以透過反向操作來計算 216 的逆元
- 1 = 53 - 13×4
- 1 = 53 - 13×(163 - 3×53)
- 1 = 40×53 - 13×163
- 1 = 40×(216 - 163) - 13×163
- 1 = 40×216 - 53×163
- 1 = 40×216 - 53×(811 - 3×216)
- 1 = 199×216 - 53×811
現在觀察這個方程模 811 的結果,我們會發現 216 的逆元是 199。
神奇表格
神奇表格是一種更優雅的方法來進行上述計算,讓我們使用從歐幾里得演算法中得到的表格
| 較小數 | 較大數 | PQ |
| 216 | 811 | 3 |
| 163 | 216 | 1 |
| 53 | 163 | 3 |
| 4 | 53 | 13 |
| 1 | 4 | 4 |
| 0 | 1 | |
現在我們建立所謂的“神奇表格”,最初看起來是這樣的
現在我們將部分商寫到第一行
我們根據以下規則生成表格
- 將一個部分商乘以它左邊同一個行的數字,然後將乘積加上它左邊兩個位置同一行的數字,並將結果放到對應的行中。
聽起來可能比實際操作更復雜。讓我們透過生成一列來演示
我們在第二行中放一個 3,因為 3 = 3×1 + 0。我們在第三行中放一個 1,因為 1 = 3×0 + 1。
現在我們將生成整個表格,不會中斷
| | 3 | 1 | 3 | 13 | 4 |
| 0 | 1 | 3 | 4 | 15 | 199 | 811 |
| 1 | 0 | 1 | 1 | 4 | 53 | 216 |
我們可以驗證
- |199×216 - 811×53| = 1
事實上,如果神奇表格構建正確,並且我們正確地交叉相乘並相減了最後兩列,那麼我們總是會得到 1 或 -1,前提是我們開始使用的兩個數字是互質的。神奇表格只是更簡潔地進行數學運算的方式。
練習
1. 求出最小的正整數 x

2. 求出最小的正整數 x

3.
(a) 構建 33a = 1 (mod 101) 的神奇表格
(b) 計算並以 p/q 的形式表示

你發現了什麼?
4.
(a) 構建 17a = 1 (mod 317) 的神奇表格
(b) 計算並以 p/q 的形式表示

你發現了什麼?
中國剩餘定理
中國剩餘定理在中國被稱為韓信點兵,最直白的翻譯是韓信數兵。原問題是這樣的
- 存在一個數 x,被 3 除餘 2,被 5 除餘 3,被 7 除餘 2。求出最小的 x。
我們將問題轉換為符號形式

我們如何找到這樣的 x?我們將使用一種熟悉的方法,它最好透過例子來解釋
觀察 x = 2 (mod 3),我們將其跳躍到普通的數學中

現在我們觀察這個方程模 5 的結果
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
將(1)代入得到:
|
|
|
|
|
現在觀察上述等式模7的結果

我們得到

為了使x最小,我們選擇b=1,因此x=23。一個簡單的檢驗(由讀者完成)可以證實x=23是解。一個值得思考的問題是:滿足三個同餘式的下一個最小的x是多少?答案是x=128,下一個是233,再下一個是338,它們相差105,即3、5和7的乘積。
我們將透過以下例子進一步說明求解同餘方程組的方法
例1 找出滿足以下條件的最小的x



解
|
|
|
|
|
|
|
|
|
|
|
現在將結果代入第一個方程,我們得到
|
|
|
|
|
|
|
|
我們得到


再次代入
|
|
|
|
|
因此,52 是滿足同餘式的最小 *x*。
示例 2
求滿足以下同餘式的最小 *x*



解
|
|
|
|
|
|
|
|
|
|
|
代入
 |
|
 |
|
 |
|
現在求解b
 |
|
 |
|
 |
|
再次代入
 |
 |
|
|
 |
|
因此,269 是滿足同餘式的最小 x。
練習
1. 求解x

2. 求解x

*解的存在性*
上面的習題都有解。那麼,是否存在一個同餘式系統,使得找不到解?當然有可能,考慮
- x ≡ 5 (mod 15)
- x ≡ 10 (mod 21)
一個更狡猾的例子是
- x ≡ 1 (mod 2)
- x ≡ 0 (mod 2)
但我們不會考慮這種愚蠢的例子。
回到第一個例子,我們可以嘗試透過以下方法求解

上面的方程沒有解,因為 3 在模 21 下沒有逆元!
人們可能會很快得出結論,如果兩個模系統有一個公因子,那麼就沒有解。但事實並非如此!考慮


我們可以找到一個解
 |
 |
|
|
 |
|
|
 |
|
現在我們將等式兩邊都乘以5的逆元(即17),得到

顯然,k = 3 是一個解,並且這兩個模系統與第一個示例(即15和21)相同。
那麼是什麼決定了同餘方程組是否有解呢?讓我們考慮一般情況


我們有


本質上,問題要求我們找到k和l,使得上述方程成立。
我們可以用以下方法來解決這個問題


現在假設m和n的gcd(m,n) = d,並且m = dmo,n = dno。我們有


如果(a - b)/d是一個整數,那麼我們可以將該方程模mo,得到

同樣,上述結果只有在(a - b)/d為整數時才有意義。如果(a - b)/d為整數,那麼就存在一個解,因為mo和no是互質的!
總之:對於兩個同餘方程組


只有當
- d = gcd(m,n) 整除 (a - b) 時,方程才有解。
以上結論可以推廣到多個同餘方程的情況。對於一個包含 n 個同餘方程的方程組


- ...

要使方程組有解,要求當 i ≠ j 時
- gcd(mi,mj) 整除 (ai - aj)
練習
判斷以下每個同餘方程組是否存在解。並解釋原因。
1.
- x ≡ 7 (mod 25)
- x ≡ 22 (mod 45)
2.
- x ≡ 7 (mod 23)
- x ≡ 3 (mod 11)
- x ≡ 3 (mod 13)
3.
- x ≡ 7 (mod 25)
- x ≡ 22 (mod 45)
- x ≡ 7 (mod 11)
4.
- x ≡ 4 (mod 28)
- x ≡ 28 (mod 52)
- x ≡ 24 (mod 32)
進一步學習
本章對數論進行了簡單的介紹,數論是數學中一個極其優美的分支。本章的介紹較為簡單,數學難度較低,內容也相對容易。如果你喜歡本章的內容,你可能也會喜歡進一步學習模運算,該章節對模運算進行了更深入、更嚴格的討論。
此外,如果你想挑戰一下自己,你可以嘗試我們為你準備的習題集。另一方面,專案要求你採用更具調查性的方式,探討中國剩餘定理的一些更深層的應用。
鳴謝
致謝:本教材的這一章在很大程度上借鑑了悉尼大學數學系榮譽退休副教授 Terry Gagen 的靈感,以及他對“數論與代數”的講義。Terry 在學生中非常受歡迎,以其風趣的教學風格而聞名。
參考文獻
1. 已知最大素數——摘要
反饋
你覺得怎麼樣? 太簡單了還是太難了?資訊太多還是不夠?我們如何改進?請在討論欄中留言告訴我們。更重要的是,自己編輯它,讓它變得更好。