跳轉到內容

高中數學擴充套件/素數/模算術

來自華夏公益教科書,開放的世界,開放的書籍
HSME
內容
100% developed 素數
100% developed 模算術
問題和專案
100% developed 問題集
100% developed 專案
解答
100% developed 練習解答
50% developed 問題集解答
雜項
100% developed 定義表
100% developed 完整版本
25% developed PDF 版本

模算術

簡介

模算術與素數有著有趣的聯絡。

模算術是一個系統,其中所有數字都小於某個正整數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。有兩個解,求出這兩個解。

逆元

考慮一個數nn的逆元是指乘以n得到1的數。例如,如果我們要解以下方程

(mod 7) 用於明確我們是在進行模7運算。我們想要以某種方式消除5。將其乘以某個數使其變為1可以實現這個目標。注意

因為3乘以5得到1,我們說3是5在模7下的逆元。現在我們將兩邊都乘以3

因此x = 2 模7是所需的解。

定義(逆元)

(一個數) x 的逆元是指一個數y,使得xy = 1。我們用x-11/x 表示x的逆元。

逆元是唯一的

從上面我們知道5的逆元是3,但5還有其他逆元嗎?答案是否定的。事實上,在任何合理的數字系統中,一個數只有一個逆元。我們可以從下面的證明中看出這一點

假設n有兩個逆元bc

從上面的論證中,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。

我們建立一個兩列表格,其中兩個數中較大的那個數位於右側,如下所示

較小 較大
21 49

現在我們計算 49 (mod 21),得到 7,將其放在第二行的較小列中,並將 21 放入較大列中。

較小 較大
21 49
7 21

對第二行執行相同的操作,生成第三行。

較小 較大
21 49
7 21
0 7

當我們在較小列中看到數字 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

需要注意的是

  1. gcd 不一定是質數。
  2. 兩個不同質數的 gcd 為 1。換句話說,兩個不同質數總是互質的。


練習

1. 確定以下數字集是否互質

  1. 5050 5051
  2. 59 78
  3. 111 369
  4. 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

其中xy 是未知數,ab 是兩個給定的常數,這些方程稱為線性丟番圖方程。有趣的是,有時沒有解,但如果存在解,則意味著存在無限多個解。

丟番圖方程

模算術 部分,我們陳述了一個定理,該定理指出如果 gcd(a,m) = 1,則a-1a 的逆元)存在於 mod m 中。不難看出,如果p 是素數,則對所有小於pb,gcd(b,p) = 1,因此我們可以說在 mod p 中,除了 0 之外的每個數都有逆元。

我們還展示了一種在 mod p 中找到任何元素的逆元的方法。事實上,在模算術中找到一個數的逆元相當於解一種稱為丟番圖方程的方程。丟番圖方程是以下形式的方程

ax + by = d

其中xy 是未知數。

例如,我們應該嘗試找到 216 在 mod 811 中的逆元。設 216 的逆元為x,我們可以寫

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

它具有丟番圖方程的形式。

現在我們將使用不優雅的方法來解決上述問題,然後使用優雅的方法(使用魔方表)。

上面提到的兩種方法都使用歐幾里得演算法來找到兩個數的 gcd。事實上,gcd 與逆元的概念密切相關。讓我們對數字 216 和 811 應用歐幾里得演算法。但是,這次我們應該儲存更多詳細資訊;更具體地說,我們想設定一個名為 PQ 的附加列,它代表部分商。部分商只是一個專業術語,表示“n 能進入m 多少次”,例如 3 和 19 的部分商是 6,4 和 21 的部分商是 5,最後一個例子 7 和 49 的部分商是 7。

較小 較大 PQ
216 811 3
163

表格說三個 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

現在我們設定所謂的“魔方表”,它最初看起來像這樣

0 1
1 0

現在我們在第一行寫入部分商

3 1 3 13 4
0 1
1 0

我們根據以下規則生成表格

將部分商乘以它左側同一行中一個位置的數字,將乘積加到同一行中左側兩個位置的數字,並將和放入相應的行中。

聽起來比實際要複雜。讓我們透過生成一列來舉例說明

3 1 3 13 4
0 1 3
1 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 11453216

我們可以檢查

|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)。

那麼什麼決定了同餘方程組是否有解?讓我們考慮一般情況

我們有

本質上,這個問題要求我們找到kl,使得上述方程成立。

我們可以這樣解決這個問題

現在假設m和n的最大公約數是gcd(m,n) = d,並且m = dmo,n = dno。我們有

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

同樣,上述結論只有在(a - b)/d是整數的情況下才成立。而且如果(a - b)/d是整數,那麼就存在解,因為mono互質!

總之:對於兩個同餘方程組

存在解當且僅當

d = gcd(m,n) 能整除(a - b)

以上結論可以很好地推廣到兩個以上的同餘方程。對於n個同餘方程組

...

為了使解存在,我們要求如果ij

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. 已知最大素數 - 摘要


反饋

你覺得怎麼樣? 太簡單還是太難? 資訊太多還是不夠? 我們如何改進? 請在討論標籤中留言告訴我們。 更好的是,自己編輯它,讓它變得更好。

華夏公益教科書