模算術
簡介
模算術與素數有著有趣的聯絡。
模算術是一個系統,其中所有數字都小於某個正整數n,例如,如果從0開始計數,則會得到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),直到它落在該範圍內。
如上所述,模算術與普通算術並沒有太大區別。例如,在模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(含)之間的數字。
練習
在模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 之外沒有其他公約數。
存在一種快速且優雅的方法來計算兩個數的 gcd,稱為歐幾里德演算法。讓我們通過幾個例子來進行說明
示例 1
- 求 21 和 49 的 gcd。
我們建立一個兩列表格,其中兩個數中較大的那個數位於右側,如下所示
現在我們計算 49 (mod 21),得到 7,將其放在第二行的較小列中,並將 21 放入較大列中。
對第二行執行相同的操作,生成第三行。
當我們在較小列中看到數字 0 時,我們知道相應的較大數字是最初兩個數字的 gcd,即 7 是 21 和 49 的 gcd。這種演算法被稱為歐幾里德演算法。
示例 2
- 求 31 和 101 的 gcd
| 較小 | 較大 |
| 31 | 101 |
| 8 | 31 |
| 7 | 8 |
| 1 | 7 |
| 0 | 1 |
示例 3
- 求 132 和 200 的 gcd
| 較小 | 較大 |
| 132 | 200 |
| 68 | 132 |
| 64 | 68 |
| 4 | 64 |
| 0 | 4 |
需要注意的是
- gcd 不一定是質數。
- 兩個不同質數的 gcd 為 1。換句話說,兩個不同質數總是互質的。
練習
1. 確定以下數字集是否互質
- 5050 5051
- 59 78
- 111 369
- 2021 4032
2. 求數字 15、510 和 375 的 gcd
資訊 -- 演算法
演算法是描述一系列動作的逐步說明,當正確執行時可以完成一項任務。存在用於查詢質數、判斷兩個數是否互質、查詢逆元以及許多其他用途的演算法。
您將在 [[../../../Mathematical Programming/]] 章節中學習如何使用計算機實現我們已經看到的某些演算法。
查詢逆元
讓我們從不同的角度再次審視逆元的概念。事實上,我們將提供一種萬無一失的方法來找到任何數的逆元。讓我們考慮
- 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的不同值。
細心的讀者應該已經注意到,這只是歐幾里得的gcd演算法反過來。
以下是一些這種巧妙方法應用的例子
示例 1
找到a的最小正值

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

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

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

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

我們可以用日常算術重新寫上述表示式

它具有丟番圖方程的形式。
現在我們將使用不優雅的方法來解決上述問題,然後使用優雅的方法(使用魔方表)。
上面提到的兩種方法都使用歐幾里得演算法來找到兩個數的 gcd。事實上,gcd 與逆元的概念密切相關。讓我們對數字 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
現在觀察 mod 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

我們得到

我們選擇b = 1 來最小化x,因此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. 已知最大素數 - 摘要
反饋
你覺得怎麼樣? 太簡單還是太難? 資訊太多還是不夠? 我們如何改進? 請在討論標籤中留言告訴我們。 更好的是,自己編輯它,讓它變得更好。