高中數學擴充套件/質數/完整

高中數學擴充套件

---

補充章節 — 質數與模算術 — 邏輯

數學證明 — 集合論與無限過程 — 計數與生成函式 — 離散機率

矩陣 — 模算術擴充套件 — 數學規劃 — 馬爾可夫鏈

HSME
內容
質數
模算術
問題與專案
習題集
專案
解答
習題解答
問題集解答
其他
定義表
完整版本
PDF 版本

引言

質數（簡稱質數）是一個自然數，它只有兩個因數：它本身和數字 1。由於 1 只有一個因數——它本身——我們不認為它是一個質數，而是一個單位。因此，2 是第一個質數，3 是下一個質數，但 4 不是質數，因為 4 除以 2 等於 2 且沒有餘數。我們已經證明了 4 有三個因數：1、2 和 4。具有兩個以上因數的數字稱為合數。

前 20 個質數是 2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67 和 71。

質數是數學家們永遠無法抗拒的魅力源泉。一些關於質數的問題非常困難，即使一些最傑出的數學家們花費數十年的時間也無法解決。其中一個問題是哥德巴赫猜想，它指出所有大於 3 的偶數都可以表示為兩個質數的和。沒有人能夠證明它是真還是假。

本章將介紹質數的一些基本性質及其與稱為模運算的數學領域之間的聯絡。

質數的幾何意義

最上面的前三個圖形展示了將 12 塊方形地磚組裝成矩形的不同方法。最下面的三個圖形表明 7 不能被 2（左圖）或 3（右圖）完全整除。

如果給定 12 塊方形地磚，我們是否可以以不止一種方式將它們組裝成矩形形狀？當然可以，這是因為

${\begin{matrix}12&=&12\times 1\\&=&6\times 2\\&=&4\times 3\\\end{matrix}}$

我們不區分 2×6 和 6×2，因為它們本質上是等效的排列。

但是數字 7 呢？你能以不止一種方式將 7 塊方形地磚排列成矩形形狀嗎？答案是否定的，因為 7 是一個質數。

算術基本定理

定理 是一個非凡的數學事實。定理必須經過證明；一個普遍認為是正確的命題，但沒有證明，被稱為猜想 或假設。

有了這些定義，算術基本定理 只是指出

任何自然數（除 1 外）都可以用一種且只有一種方式表示為質數的乘積。

例如

$12=2\times 2\times 3\,\!$

重新排列乘法順序不視為數字的不同表示，因此沒有其他方式將 12 表示為質數的乘積。

再舉幾個例子

${\begin{matrix}99&=&3&\times &3&\times &11\\52&=&2&\times &2&\times &13\\17&=&17&\end{matrix}}$

可以很容易地看出，合數具有多個質因數（多次計算重複的質因數）。

為什麼？

記住算術基本定理的定義，為什麼數字 1 不被認為是質數？

因式分解

我們從算術基本定理中知道，任何整數都可以表示為質數的乘積。一百萬美金的問題是：給定一個數字 *x*，是否有 *簡單* 的方法找到 *x* 的所有質因數？

如果 *x* 是一個小的數字，那麼很簡單。例如，90 = 2 × 3 × 3 × 5。但是如果 *x* 很大呢？例如 *x = 4539*？大多數人無法在腦中將 4539 分解成質數。但是計算機可以做到嗎？可以，計算機可以相當快地將 4539 分解成質數。我們有 4539 = 3 × 17 × 89。

由於計算機非常擅長算術運算，我們可以透過簡單地指示計算機依次將 *x* 除以 2、然後 3、然後 5、然後 7...等等來計算出 *x* 的所有因數。

因此，存在一種 *簡單* 的方法將數字分解成質因數。只需應用上面描述的方法即可。但是，這種方法對於大數來說太慢了：嘗試將一個擁有數千位數字的數字分解成質因數將花費比當前宇宙年齡更長的時間。但是，有沒有一種 *快速* 的方法？或者更確切地說，有沒有一種 *高效* 的方法？可能存在，但還沒有人找到。當今一些最廣泛使用的加密方案（如 RSA）利用了我們無法快速將大數分解成質因數的事實。如果找到了這樣的方法，許多網際網路交易將變得不安全。

考慮以下三個正在進行的除法方法的示例。

示例 1

$x=21$

${\frac {x}{2}}=10.5$ 不是整數，因此 2 不是 21 的因數

${\frac {x}{3}}=7$ 因此 3 和 7 是 21 的因數。

示例 2

$x=153$

${\frac {x}{2}}=76.5$ 因此 2 不是 153 的因數

${\frac {x}{3}}=51$ 因此 3 和 51 是 153 的因數。

${\frac {51}{3}}=17$ 因此 3 和 17 是 153 的因數。

很明顯，3、9、17 和 51 是 153 的因數。153 的質因數是 3、3 和 17 (3×3×17 = 153)

示例 3

${\frac {2057}{2}}=1028.5$

$\cdots$

${\frac {2057}{11}}=187$

${\frac {187}{11}}=17$

因此 11、11 和 17 是 2057 的質因數。

練習

對下面給定的數字進行因式分解

1

13=

2

26=

3

59=

4

82=

5

101=

6

121=

7 如果時間太長，就放棄。有一個快速的方法。

2187=

有趣的事實 - 這是質數嗎？

有趣的是，藉助計算機，有一種有效的方法可以以 100% 的準確性確定一個數字是否是質數。

2、5 和 3

質數 2、5 和 3 在因式分解中佔有特殊的地位。首先，所有偶數都有 2 作為它們的質因數之一。其次，所有最後一位數字是 0 或 5 的數字都可以被 5 整除。

第三種情況，3 是質因數，是本節的重點。根本問題是：是否有簡單的方法來判斷一個數字是否具有 3 作為其質因數之一？

定理 - 可被 3 整除

一個數字可被 3 整除當且僅當其各位數字之和可被 3 整除。

例如，272 不可被 3 整除，因為 2 + 7 + 2 = 11，不可被 3 整除。

945 可被 3 整除，因為 9 + 4 + 5 = 18。而 18 可被 3 整除。實際上，945 / 3 = 315

123456789 可被 3 整除嗎？

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = (1 + 9) × 9 / 2 = 45

4 + 5 = 9

九可被 3 整除，因此 45 可被 3 整除，因此 123456789 可被 3 整除！

該定理的妙處在於其遞迴性。一個數字可被 3 整除當且僅當其各位數字之和可被 3 整除。我們怎麼知道其各位數字之和是否可被 3 整除？再次應用該定理！

資訊 - 遞迴

一位著名的計算機科學家曾經說過“迭代是人的行為，遞迴是神來之筆”。但這遞迴是什麼意思？在此之前，迭代是什麼？
“迭代”僅僅意味著一遍又一遍地做同樣的事情，而計算機非常擅長這一點。數學中的迭代示例是指數運算，例如 xⁿ 意味著 x 乘以 x 乘以 x 乘以 x...n 次。這是一個迭代的示例。

經濟地（就心理資源而言）思考迭代，透過用自身來定義一個問題，就是“遞迴”。為了遞迴地表示 xⁿ，我們寫

$x^{n}=1$ 如果n 等於 0。

$x^{n}=x\times x^{n-1}$ 如果n > 0

9⁹ 是多少？它是 9 乘以 9 ⁸。但是，9⁸ 是 9 乘以 9⁷。以這種方式重複是遞迴的示例。

練習

對於問題 1-3，進行因式分解

1

45=

2

4050=

3

2187=

4 證明可被 3 整除定理適用於任何三位數。

（在紙上做）

5 一個數字可被 9 整除當且僅當其各位數字之和可被 9 整除。

	對
	錯

確定問題 6-9 中的數字是否可被 9 整除。

6 89

	是
	否

7 558

	是
	否

8 51858

	是
	否

9 41857

	是
	否

尋找質數

質數篩是一種相對有效的方法，用於尋找所有小於或等於指定數字的質數。要找到所有小於或等於 50 的質數，我們執行以下操作

首先，我們將數字 1 到 50 寫在一個表中，如下所示

${\begin{matrix}1&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}$

劃掉 1，因為它不是質數。

${\begin{matrix}X&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}$

現在 2 是表格中未劃去的最小數字。我們標記 2 為素數，並劃去所有 2 的倍數，即 4、6、8、10 ...

${\begin{matrix}X&2_{p}&3&X&5&X&7&X&9&X\\11&X&13&X&15&X&17&X&19&X\\21&X&23&X&25&X&27&X&29&X\\31&X&33&X&35&X&37&X&39&X\\41&X&43&X&45&X&47&X&49&X\\\end{matrix}}$

現在 3 是表格中未標記的最小數字。我們標記 3 為素數，並劃去所有 3 的倍數，即 6、9、12、15 ...

${\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}$

繼續以這種方式找出所有素數。你什麼時候知道已經找到了 50 以下的所有素數？請注意，此演算法稱為埃拉託斯特尼篩法

練習

1. $${\begin{matrix}X&2&3&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&X&X&X&X&29&X\\31&X&X&X&X&X&37&X&X&X\\41&X&43&X&X&X&47&X&X&X\\\end{matrix}}$$素數篩法已應用於上面的表格。請注意，2 和 5 下方所有數字都被劃掉了。構造一個從 1 到 60 的數字矩形網格，以便在對其執行素數篩法後，2 和 5 下方所有數字都被劃掉。網格的寬度是多少？
2. 找出 200 以下的所有素數。
3. 找出 200 以下能被 3 整除的數字。你改變了網格的寬度了嗎？

無限多個素數

要回答什麼是最大的質數？這個問題，讓我們先回答什麼是最大的自然數？如果有人告訴你$10^{10}$是最大的自然數，你可以立即反駁他們，告訴他們$10^{10}+1$是一個更大的自然數。你可以用任何其他自然數$n$替換$10^{10}$，你的論據仍然有效。這意味著不存在所謂的最大的自然數。（你們中的一些人可能會想說無窮大是最大的自然數。但是，無窮大不是自然數，而只是一個數學概念。）

古希臘數學家歐幾里得對質數的無限性進行了以下證明。

質數無限性的證明

讓我們先假設

質數的數量是有限的

因此

一定存在一個比所有其他質數都大的質數，

讓我們將這個質數稱為n。現在，我們將證明上面提到的兩個假設會導致矛盾，因此存在無限多個質數。

將所有質數相乘，得到一個數x。因此

$x=2\times 3\times 5\times \ldots \times n\!$

然後，令y等於x加1

$y=x+1\!$

現在我們可以得出結論，y不能被任何小於等於n的質數整除，因為y比每個這樣的質數的倍數正好大1。由於y不能被任何質數整除，因此y要麼是質數，要麼它的質因數都大於n，這與最初假設n是最大質數相矛盾！因此，我們必須宣佈最初的假設是錯誤的，並且存在無限多個質數。

有趣的事實——已知最大的質數

已知的最大質數是2^82,589,933-1。它有高達24,862,048位數！形如2ⁿ-1的質數被稱為梅森素數，以法國僧侶/業餘數學家命名。

有用的外部資源

• "The Prime Pages. Prime Number Research, Records, and Resources"

模運算

引言

模運算與質數之間存在有趣的聯絡。

模運算是一種系統，其中使用所有小於某個正整數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運算中，我們有

$3+2=5\!$

$5+6=11=4\!$

$5-6=-1=6\!$

以及

${\begin{matrix}3\times 5=15=1\\5\times -6=-30=5\\\end{matrix}}$

我們進行了一些負數的運算。考慮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次方

2¹, 2², 2³, ... , 2¹⁰

你注意到什麼了？
使用2的冪找到

6¹, 6², 6³, ... , 6¹⁰

你又注意到什麼了？

4.

${\sqrt {4}}$

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

5.

${\sqrt {9}}$

即找到所有滿足x² = 9 (mod 11)的數字x。有兩個解，找到它們。

逆元

考慮一個數字n，n的逆元是與n相乘得到1的數字。例如，如果我們要解以下方程

$5x=3{\pmod {7}}\!$

使用 (mod 7) 是為了明確我們正在進行模7運算。我們希望以某種方式消除5。用一個數乘它，把它變成1，就可以完成這個任務。請注意

$3\times 5=15=1{\pmod {7}}\!$

因為 3 乘以 5 等於 1，我們說 3 是 5 在模 7 運算中的逆元。現在我們將兩邊都乘以 3

$3\times 5\!$	$x\!$	$=3\times 3{\pmod {7}}\!$
	$x\!$	$=9{\pmod {7}}\!$
		$=2{\pmod {7}}\!$

所以，x = 2 模 7 是要求的解。

定義 (逆元)

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

逆元是唯一的

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

假設 n 有兩個逆元 b 和 c

$b=b\times 1=b(nc)=(bn)c=1\times c=c\!$

從上面的論證可以看出，n 的所有逆元都必須相等。因此，如果數字 n 有逆元，則該逆元一定是唯一的。

任何模 n 運算的一個有趣的性質是數字 n - 1 具有其自身作為逆元。也就是說，(n - 1) × (n - 1) = 1 (mod n)，或者我們可以寫成 (n - 1)² = (-1)² = 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{\pmod {15}}\!$

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

$3x=15k+1\!$

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

$x=5k+{\frac {1}{3}}\!$

但這不可能成立，因為我們知道 x 是一個整數，而不是分數。因此，3 在模 15 運算中沒有逆元。要證明 10 沒有逆元更難，留作習題。

我們現在將說明關於模運算中逆元存在的定理。

定理

如果 n 是素數，那麼每個數字（除 0 之外）在模 n 運算中都有逆元。

類似地

如果 n 是合數，那麼每個與 n 沒有公因數的數字都有逆元。

有趣的是，除法 與逆元的概念密切相關。考慮以下表達式

$6\times 3^{-1}{\pmod {7}}\!$

計算上述表示式的傳統方法是找到 3 的逆元（即 5）。所以

$6\times 3^{-1}=6\times 5=30=2{\pmod {7}}\!$

我們將 3 的逆元寫成 1/3，所以我們將乘以 3^-1 視為除以 3，得到

$6\times {\frac {1}{3}}={\frac {6}{3}}=2{\pmod {7}}\!$

注意，我們得到了相同的答案！事實上，如果存在逆，除法方法總是有效的。

然而，在不同的模系統中，表示式會產生錯誤的答案，例如

$6\times 3^{-1}{\pmod {9}}\!$

我們沒有得到 2，因為 3^-1 在模 9 中不存在，所以我們不能使用除法方法。

練習

1. 8 在模 16 運算中是否有逆？如果沒有，為什麼？

2. 如果存在 x，求 x 模 7

$x=2^{-1}\!$

$x=3^{-1}\!$

$x=4^{-1}\!$

$x=5^{-1}\!$

$x=6^{-1}\!$

$x=7^{-1}\!$

3. 用兩種方法計算 x，求逆 和 除法

$x=28\cdot 7^{-1}\ \ {\mbox{(mod 29)}}\!$

4. (技巧) 求 x

$x=5^{99}\times (40+3^{-1})\ {\pmod {11}}\!$

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

info -- 演算法

演算法是對一系列動作的逐步描述，當正確執行時，可以完成一項任務。存在用於查詢質數、判斷兩個數字是否互質、查詢逆以及許多其他目的的演算法。
您將在 [[../../../Mathematical Programming/]] 章中學習如何使用計算機實現我們已經見過的某些演算法。

查詢逆

讓我們從另一個角度來看逆的概念。事實上，我們將提供一種萬無一失的方法來找到任何數字的逆。讓我們考慮

5x = 1 (mod 7)

我們知道 x 是 5 的逆，我們可以很快地算出它是 3。但 x = 10 也是一個解，x = 17 也是，還有 x = 24、31、... 7n + 3。因此有無窮多個解；因此我們說 3 等價於 10、17、24、31 等。這是一個至關重要的觀察結果。

現在讓我們考慮

$216x\equiv 1\ \ {\mbox{(mod 811)}}$

這裡引入了一種新的符號，它是帶三個劃線的等號而不是兩個。它是“等價”符號；上面的語句應該讀作“216x 等價於 1”而不是“216x 等於 1”。從現在開始，我們將使用等價符號來表示模運算，而使用等號來表示普通運算。

回到這個例子，我們知道x 存在，因為 gcd(811,216) = 1。上面問題的問題在於沒有快速的方法來確定x的值！我們知道最好的方法是將 216 乘以 1、2、3、4…… 直到我們得到答案，最多需要 811 次計算，對於人類來說太繁瑣了。但是有一個更好的方法，我們已經討論過很多次了！

我們注意到，我們可以像以前一樣“跳躍”到有理數學中。

${\begin{matrix}216a&=&1+811b\\0&\equiv &1+163b&{\pmod {216}}\\\end{matrix}}$

我們再次跳入有理數學。

${\begin{matrix}216c&=&1+163b\\53c&\equiv &1&{\pmod {163}}\\\end{matrix}}$

我們再跳一次。

${\begin{matrix}53c&=&1+163d\\0&\equiv &1+4d&{\pmod {53}}\\\end{matrix}}$

現在模式很明顯，我們應該從頭開始，這樣過程就不會被打斷。

${\begin{matrix}216a&=&1+811b\\216c&=&1+163b\\53c&=&1+163d\\53e&=&1+4d\\e&=&1+4f\\\end{matrix}}$

現在我們所要做的就是選擇f的值，然後代入回去找到a！記住，a 是 216 模 811 的逆。我們選擇 f = 0，因此 e = 1，d = 13，c = 40，b = 53，最後 a = 199！如果選擇f為 1，我們將得到a的不同值。

非常敏銳的讀者應該已經注意到，這只是歐幾里得演算法的逆運算。

以下是一些關於這種巧妙方法應用的例子。

示例 1

求a的最小正值。

${\begin{matrix}33a&\equiv &1\ \ {\mbox{(mod 101)}}\\33a&=&1+101b\\33c&=&1+2b\\c&=&1+2d\\\end{matrix}}$

選擇 d = 0，因此 a = 49。

示例 2 求a的最小正值。

${\begin{matrix}27a&\equiv &1\ \ {\mbox{(mod 821)}}\\27a&=&1+821b\\27c&=&1+11b\\5c&=&1+11d\\5e&=&1+d\\\end{matrix}}$

選擇 e = 0，因此 a = -152 = 669。

示例 3 求a的最小正值。

${\begin{matrix}34a&\equiv &1\ \ {\mbox{(mod 55)}}\\34a&=&1+55b\\34c&=&1+21b\\13c&=&1+21d\\13e&=&1+8d\\5e&=&1+8f\\5g&=&1+3f\\2g&=&1+3h\\2i&=&1+h\\\end{matrix}}$

設定 i = 0，然後 a = -21 = 34。為什麼對於兩個如此小的數字，它會如此緩慢？ 你對係數有什麼看法？

示例 4 求a的最小正值。

${\begin{matrix}21a&\equiv &1\ \ {\mbox{(mod 102)}}\\21a&=&1+102b\\21c&=&1+18b\\3c&=&1+18d\\3d&=&1\\\end{matrix}}$

現在 *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* 是未知數。

例如，我們應該嘗試在模 811 下找到 216 的逆元。設 216 的逆元為 *x*，我們可以寫成

$216x\equiv 1{\pmod {811}}\!$

我們可以用日常算術重新寫上面的內容

$216x+811y=1\!$

它是一個丟番圖方程的形式。

現在我們要用不優雅的方法來解決以上問題，然後用優雅的方法（使用神奇表）。

以上兩種方法都使用歐幾里德演算法來求解兩個數的 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

現在看看模 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	1	1	4	53	216

我們可以檢查

|199×216 - 811×53| = 1

事實上，如果神奇表構建得正確，並且我們對最後兩列進行了 *交叉相乘和相減*，那麼我們總能得到 1 或 -1，前提是我們開始的兩個數字是互質的。神奇表只是更簡潔地進行數學運算的一種方式。

練習

1. 找到最小的正 *x*

$216x\equiv 1\ \ {\mbox{(mod 816)}}$

2. 找到最小的正 *x*

$42x\equiv 7\ \ {\mbox{(mod 217)}}$

3.

(a) 生成 33 *a* = 1 (mod 101) 的神奇表

(b) 計算並用 p/q 的形式表示

$3+{1 \over 16+{1 \over 2}}$

你注意到什麼了？

4.

(a) 生成 17a = 1 (mod 317) 的神奇表

(b) 計算並用 p/q 的形式表示

$18+{1 \over 1+{1 \over {1+{1 \over 1+{1 \over 5}}}}}$

你注意到什麼了？

中國剩餘定理

中國剩餘定理在中國被稱為 *韓信點兵*，最直白的翻譯是 *韓信數兵*。最初的問題是這樣的

存在一個數字 *x*，被 3 除餘 2，被 5 除餘 3，被 7 除餘 2。求最小的 *x*。

我們將問題轉換成符號形式

${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&\equiv &3{\pmod {5}}\\x&\equiv &2{\pmod {7}}\\\end{matrix}}$

如何找到這樣的x？ 我們將使用一種熟悉的方法，最好用例子說明

看x = 2 (mod 3)，我們進入普通數學的“跳躍”

${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&=&2+3a\qquad (1)\end{matrix}}$

現在我們看看模 5 的方程

$2+\!$	$3a\!$	$\equiv 3{\pmod {5}}\!$
	$3a\!$	$\equiv 1{\pmod {5}}\!$
	$a\!$	$\equiv 2{\pmod {5}}\!$
	$a\!$	$=2+5b\!$

代入 (1) 得到以下結果

$x\!$	$=2+3(2+5b)\!$
	$=8+15b\!$

現在看看上面模 7

$x=8+15b\equiv 2{\pmod {7}}\!$

我們得到

$b\equiv 1{\pmod {7}}\!$

我們選擇b = 1 以最小化x，因此x = 23。 簡單的檢查（由讀者執行）應確認x = 23 是一個解。 一個值得問的問題是，滿足這三個同餘式的下一個最小的x是什麼？ 答案是x = 128，下一個是233，再下一個是338，它們相差105，即3、5和7的乘積。

我們將透過以下示例進一步說明求解同餘方程組的方法

示例 1 找到滿足以下條件的最小的x

$x\equiv 1{\pmod {3}}\!$

$x\equiv 2{\pmod {5}}\!$

$x\equiv 3{\pmod {7}}\!$

解法

$x=\!$	$1+3\!$	$a\!$	$\equiv \!$	$2{\pmod {5}}\!$
		$a\!$	$=\!$	$2+5b\!$

現在將結果代回第一個方程，我們得到

$x\!$	$=1+3(2+5b)\!$
	$=7+15b\!$
	$\equiv 3{\pmod {7}}\!$

我們得到

$b\equiv 3{\pmod {7}}\!$

$b=3+7c\!$

再次代回

$x\!$	$=7+15(3+7c)\!$
	$=52+15\times 7c\!$

因此 52 是滿足同餘式的最小 x。

示例 2

找出滿足以下同餘式的最小 x

$x\equiv 5{\pmod {11}}\!$

$x\equiv 3{\pmod {7}}\!$

$x\equiv 8{\pmod {9}}\!$

解法

$x\!$	$=5+11\!$	$a\equiv 3{\pmod {7}}\!$
		$a\equiv 3{\pmod {7}}\!$
		$a=3+7b\!$

代回

$x=\!$	$5+11(3+7b)\!$
$=\!$	$38+11\times 7b\!$
$\equiv \!$	$8{\pmod {9}}\!$

現在求解b

$2+2\times 7b\!$	$\equiv 8{\pmod {9}}\!$
$b\!$	$\equiv 3{\pmod {9}}\!$
$b\!$	$=3+9c\!$

再次代入

$x\!$	$=\!$	$38+11\times 7(3+9c)\!$
	$=\!$	$269+11\times 7\times 9c\!$

因此 269 是滿足同餘式的最小 x。

練習

1. 求解 x

${\begin{matrix}3x&\equiv &5{\pmod {14}}\\2x&\equiv &-3{\pmod {17}}\\x&\equiv &6{\pmod {15}}\\\end{matrix}}$

2. 求解 x

${\begin{matrix}3x&\equiv &5{\pmod {19}}\\7x&\equiv &-3{\pmod {17}}\\x&\equiv &6{\pmod {11}}\\\end{matrix}}$

*解的存在性*

上面的練習都有解。那麼是否存在一個同餘方程組，使得找不到解？當然有可能，考慮

x ≡ 5 (mod 15)

x ≡ 10 (mod 21)

一個更巧妙的例子是

x ≡ 1 (mod 2)

x ≡ 0 (mod 2)

但我們不會考慮這種愚蠢的例子。

回到第一個例子，我們可以嘗試透過以下方法求解

${\begin{matrix}x&=&5+15k&\equiv &10&{\pmod {21}}\\&&15k&\equiv &5&\\&&3k&\equiv &1&\\\end{matrix}}$

上述方程無解，因為 3 在模 21 下沒有逆元！

人們可能很快得出結論，如果兩個模系統有公因子，則沒有解。但這並不正確！考慮

$x\equiv 4{\pmod {15}}\!$

$x\equiv 7{\pmod {21}}\!$

我們可以找到一個解

$x=\!$	$4+15k\!$	$\equiv 7{\pmod {21}}\!$
	$15k\!$	$\equiv 3{\pmod {21}}\!$
	$5\times 3k\!$	$\equiv 3{\pmod {21}}\!$

現在我們將兩邊乘以 5 的逆元（即 17），得到

$3k\equiv 9\!$

顯然，k = 3 是一個解，這兩個模系統與第一個例子相同（即 15 和 21）。

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

$x\equiv a{\pmod {m}}\!$

$x\equiv b{\pmod {n}}\!$

我們有

$x=a+km\!$

$x=b+ln\!$

本質上，問題要求我們找到k 和 l，使得上述方程成立。

我們可以如下解決這個問題

$0=(a-b)+(km-ln)\,\!$

$(ln-km)=(a-b)\,\!$

現在假設 m 和 n 有 gcd(m,n) = d，並且 m = dm_o, n = dn_o。我們有

$dln_{o}-dkm_{o}=(a-b)\,\!$

$ln_{o}-km_{o}=(a-b)/d\,\!$

如果 (a - b)/d 是一個整數，那麼我們可以讀出模 m_o 下的方程，得到

$ln_{o}\equiv (a-b)/d{\pmod {m_{o}}}\,\!$

再次強調，上述公式只有在 (a - b)/d 為整數時才有意義。此外，如果 (a - b)/d 是一個整數，那麼就存在一個解，因為 m_o 和 n_o 是互質的！

概括來說，對於一個包含兩個同餘方程的系統

$x\equiv a{\pmod {m}}\,\!$

$x\equiv b{\pmod {n}}\,\!$

存在解當且僅當

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

上述結論可以很好地推廣到多個同餘方程。對於一個包含 n 個同餘方程的系統

$x\equiv a_{1}{\pmod {m_{1}}}\,\!$

$x\equiv a_{2}{\pmod {m_{2}}}\,\!$

...

$x\equiv a_{n}{\pmod {m_{n}}}\,\!$

要使存在解，我們需要滿足當 i ≠ j 時

gcd(m_i,m_j) 能整除 (a_i - a_j)

練習

判斷以下每個同餘方程組是否存在解。解釋原因。

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. 已知最大素數總結

反饋

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

高中數學擴充套件

---

補充章節 — 質數與模算術 — 邏輯

數學證明 — 集合論與無限過程 — 計數與生成函式 — 離散機率

矩陣 — 模算術擴充套件 — 數學規劃 — 馬爾可夫鏈