高中數學拓展/進階模算術

高中數學拓展

---

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

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

矩陣 — 進階模算術 — 數學規劃 — 馬爾可夫鏈

HSME
內容
進階模算術
乘法群與離散對數
問題與專案
習題集
專案
解答
練習解答
習題集解答
其他
定義表
完整版
PDF版本

介紹

數學是科學的皇后，數論是數學的皇后。 -- 卡爾·弗里德里希·高斯 1777 - 1855

在素數與模算術部分，我們討論了素數的基本性質及其與模算術的聯絡。在大多數情況下，我們的注意力都集中在模p算術，其中p是素數。

在本章中，我們首先討論一些模素數p算術中更基本的結果，然後繼續討論模m算術的結果，其中m是合數。特別是，我們將仔細研究中國剩餘定理（CRT），以及它如何允許我們將模m算術分解為分量。從這個角度來看，CRT是一個極其強大的工具，可以幫助我們相對輕鬆地解開模算術的許多秘密。

最後，我們將介紹阿貝爾群的概念，透過模算術中的乘法來討論離散對數問題，該問題是當今已知最重要的密碼系統之一的基礎。

假設知識 在本章中，我們假設讀者能夠找到逆元，並能夠解決同餘方程組（中國剩餘定理）（參見：素數與模算術）。

威爾遜定理

威爾遜定理是一個簡單的結果，它導致了初等數論中許多有趣的觀察。它指出，如果p是素數，則

$1\cdot 2\cdot 3\cdots (p-1)\equiv p-1{\pmod {p}}$

我們知道 *p* - 1 的逆元是 *p* - 1，所以其他每個數字都可以與其逆元配對並 *消除*。例如，設 *p* = 7，我們考慮

1 × 2 × .. × 6 ≡ (2 × 4) × (3 × 5) × 1 × 6 = 6

我們所做的就是將互為逆元的數字配對，然後剩下的數字就是其逆元為自身的數字。在這種情況下，它們是 1 和 6。

但是，存在一個技術上的難點。對於一個一般的質數 *p*，我們如何知道 1 和 *p* - 1 是模 *p* 中唯一兩個平方後等於 1 的數字？對於非質數的 *m*，*x*² ≡ 1 (mod *m*) 有超過 2 個解，例如，設 *m* = 15，則 x = 1、14、4、11 都是 *x*² ≡ 1 (mod *m*) 的解。

然而，我們可以證明，當 *p* 為質數時，*x*² ≡ 1 (mod *p*) 最多隻有兩個解。我們透過一個簡單的 *反證法* 論證來實現這一點。您可能想跳過以下證明，並想出自己對威爾遜定理為真的原因的解釋。

設 *p* 為質數，且 *x*² ≡ 1 (mod *p*)。我們的目標是證明最多隻有 2 個解，即 *x* = 1、-1

$x^{2}-1\!$	$\equiv 0\!$
$(x-1)(x+1)\!$	$\equiv 0\!$

從上面可以明顯看出，*x* = 1、-1 (≡ *p* - 1) 是解。假設還有另一個解 *x* = *d*，且 *d* 不等於 1 或 -1。由於 *p* 是質數，我們知道 *d* - 1 必須有逆元。我們將 *x* 替換為 *d*，並將兩邊乘以逆元，即

$(d-1)(d+1)\!$	$=0\!$
$d+1\!$	$=0\!$
$d\!$	$=-1\!$

但我們最初的假設是 *d* ≠ -1。這是一個矛盾。因此，*x*² ≡ 1 (mod *p*) 最多隻有 2 個解。

費馬小定理

有一個以業餘數學家之王 費馬 命名的非凡小定理。它指出，如果 *p* 為質數，且給定 *a* ≠ 0，則

$a^{p-1}\equiv 1{\pmod {p}}\!$

這個定理取決於 *p* 是質數的事實。回想一下，如果 *p* 是質數，則 *a* ≠ 0 有逆元。因此，對於任何 *b* 和 *c*，我們必須有

$ab\equiv ac{\pmod {p}}\!$ 當且僅當 $b\equiv c{\pmod {p}}\!$

上述結果的一個簡單推論是，以下數字在模 *p* 下必須互不相同

*a*，2*a*，3*a*，4*a*，...，(*p*-1)*a*

並且這些數字共有 *p* - 1 個！因此，上面的列表只是 1、2、... *p* - 1 按不同順序排列的數字。讓我們看一個例子，取 *p* = 5，*a* = 2

1, 2, 3, 4

在模 5 的情況下，將上述所有數乘以 2，我們得到

2, 4, 1, 3

它們只是原數字的順序不同。

因此，對於任何 *p* 並使用威爾遜定理（回顧：1 × 2 × ... × (p-1) ≡ -1），我們得到

${\displaystyle a\cdot 2a\cdots (p-1)a\!$	$\equiv \!$	$1\cdot 2\cdots (p-1)$
	$\equiv \!$	$-1\!$

另一方面，我們也得到

${\displaystyle a\cdot 2a\cdots (p-1)a\!$	$\equiv \!$	$a^{p-1}(1\cdot 2\cdots (p-1))$
	$\equiv \!$	$-a^{p-1}\!$

將這兩個結果相等，我們得到

$-a^{p-1}\!$

$\equiv \!$

$-1\!$

這實際上是費馬小定理。

一般模 m 的模運算

*中國剩餘定理再探*

本節內容比較理論化，旨在證明下一節中我們將要討論的運算。因此，不必完全理解這裡的內容，讀者可以跳過以下內容。

回顧我們在模運算部分介紹的中國剩餘定理（CRT）。它表明，如果以下同餘式

$x\equiv b{\pmod {n_{1}}}\!$

$x\equiv c{\pmod {n_{2}}}\!$

有解當且僅當 gcd(n₁,n₂) 整除 (b - c)。

這個看似簡單的定理是模 *m*（非素數）運算的關鍵！我們將考慮 *m* 只有兩個素數因子的情況，然後可以推匯出一般情況。

假設 *m* = *p*ⁱ*q*^j，其中 *p* 和 *q* 是不同的素數，那麼 *m* 以下的每個自然數（0，1，2，...，m - 1）都唯一對應於模 *p*ⁱ 和模 *q*^j 的一個同餘系統。這是因為 gcd(pⁱ,q^j) = 1，所以它能整除所有數字。

考慮一個數字 *n*，它對應於

$n\equiv x_{n}{\pmod {p^{i}}}\!$

$n\equiv y_{n}{\pmod {q^{j}}}\!$

對於一些 x_n 和 y_n。如果 *r* ≠ *n*，那麼 *r* 對應於

$r\equiv x_{r}{\pmod {p^{i}}}\!$

$r\equiv y_{r}{\pmod {q^{j}}}\!$

現在，由於 *r* 和 *n* 不同，我們必須有 *x*_r ≠ *x*_n 或者 *y*_r ≠ *y*_n

例如，取$m=12=2^{2}\times 3$，那麼我們可以構建以下表格，顯示$x_{n}$，$y_{n}$ 對於每個 n (0, 1, 2 ... 11)

n	n (mod 22)	n (mod 3)
0	0	0
1	1	1
2	2	2
3	3	0
4	0	1
5	1	2
6	2	0
7	3	1
8	0	2
9	1	0
10	2	1
11	3	2

注意，正如預測的那樣，每個數字都唯一對應於兩個不同的同餘系統：模 2² 和模 3。

練習

1. 考慮 m = 45 = 3² × 5. 完成下面的表格，並驗證任何兩個數字在第二列和第三列中至少有一個位置不同。

n	n (mod 32)	n (mod 5)
0	0	0
1	1	1
2	2	2
...
44	?	?

2. 假設 m = pⁱq^j，n 對應於

$n\equiv x_{n}{\pmod {p^{i}}}\!$

$n\equiv y_{n}{\pmod {q^{j}}}\!$

且 r 對應於

$r\equiv x_{r}{\pmod {p^{i}}}\!$

$r\equiv y_{r}{\pmod {q^{j}}}\!$

是否真的

$n+r\equiv x_{n}+x_{r}{\pmod {p^{i}}}\!$

$n+r\equiv y_{n}+y_{r}{\pmod {q^{j}}}\!$

以及

$nr\equiv x_{n}x_{r}{\pmod {p^{i}}}\!$

$nr\equiv y_{n}y_{r}{\pmod {q^{j}}}\!$

使用 CRT 進行算術

上面的練習 2 為 CRT 如何幫助模 m 算術提供了最明顯的指示。讀者在現階段不必完全理解上面的內容。我們將繼續描述 CRT 如何幫助模 m 算術。簡單來說，CRT 幫助將模 m 運算分解為模 m 的質因子的更小的運算。

像往常一樣，讓我們先考慮一個簡單的例子。設 $m=63=3^{2}\ \times \ 7$，我們看到 m 有兩個不同的質因子。我們應該用兩種方法演示 51 和 13 模 63 的乘法。首先，是標準方法

$51\times 13\!$	$=\!$	$663\!$
	$=\!$	$10\times 63+33\!$
	$\equiv \!$	$33{\pmod {63}}\!$

或者，我們注意到

$51\equiv 6{\pmod {9}}\!$

和

$51\equiv 2{\pmod {7}}\!$

我們可以將上述兩個表示式表示為一個二元組 (6,2)。我們略微濫用符號，寫 51 = (6,2)。類似地，我們寫 13 = (4,6)。當我們對二元組進行乘法運算時，我們按分量相乘，即 (a,b) × (c,d) = (ac,bd)，

$51\times 13\!$	$=\!$	$(6,2)\times (4,6)\!$
	$=\!$	$(24,12)\!$
	$=\!$	$(2\times 9+6,7+5)\!$
	$\equiv \!$	$(6,5)\!$

現在讓我們解決

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

和

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

我們寫 x = 6 + 9a，這是第一個同餘方程，然後

$6+9a\!$	$\equiv \!$	$5{\pmod {7}}\!$
$2a\!$	$\equiv \!$	$6\!$
$a\!$	$\equiv \!$	$3\!$

因此，我們有 a = 3 + 7b，代入回去得到

$x=6+9(3+7b)=33+63b\equiv 33{\pmod {63}}\!$

這與我們用標準方法將 51 和 13 相乘 (mod 63) 得到的結果相同！

讓我們總結一下我們做了什麼。透過將兩個數字（51 和 13）表示為兩個二元組，並按分量相乘，我們最終得到了另一個二元組。根據中國剩餘定理，這個二元組對應著這兩個數字的乘積 (mod m)。

我們將再舉兩個例子。令 $m=88=2^{3}\times 11$，讓我們用兩種方法將 66 和 40 相乘。首先，用標準方法

$66\times 40\!$	$=\!$	$2640\!$
	$=\!$	$30\times 88\!$
	$\equiv \!$	$0{\pmod {88}}\!$

現在用第二種方法，40 = (0,7) 和 66 = (4,0) 以及

$66\times 40\!$	$=\!$	$(0,7)\times (4,0)\!$
	$=\!$	$(0,0)\!$
	$\equiv \!$	$0{\pmod {88}}\!$

對於第二個例子，我們注意到沒有必要只停留在兩個不同的質因數上。我們令 $m=975=3\times 5^{2}\times 13$，並將 900 和 647 (mod 975) 相乘，

$900\times 647\!$	$=\!$	$582300\!$
	$\equiv \!$	$225{\pmod {975}}\!$

對於另一種方法，我們注意到 900 ≡ 0 (mod 3) ≡ 0 (mod 25) ≡ 3 (mod 13)，而 647 ≡ 2 (mod 3) ≡ 22 (mod 25) ≡ 10 (mod 13)，

$900\times 647\!$	$=\!$	$(0,0,3)\times (2,22,10)\!$
	$\equiv \!$	$(0,0,30)\!$
	$\equiv \!$	$(0,0,4)\!$

現在如果我們解以下同餘方程

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

$x\equiv 0{\pmod {25}}\!$

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

那麼我們會得到 x ≡ 225!

為什麼？ 如果說有什麼，將 mod m 中的模運算分解成更小的部分似乎需要不少工作。以乘法為例，首先，我們需要將每個數表示成一個 n 元組（n 是 m 的不同質因數的個數），然後按分量相乘，最後解出得到的 n 個同餘方程。當然，這肯定比直接將兩個數相乘然後將結果模 m 更復雜。那麼為什麼要費心研究它呢？

透過將一個數 m 分解成質因數，我們對模運算的實際工作原理有了更深刻的理解。更重要的是，mod m 中的許多問題可能很難解決，但當分解成更小的部分後，突然變得很容易，例如，對一般 m 的威爾遜定理（下面將討論）。

練習

1. 證明加法也可以按分量進行。

2. 按分量相乘 32 和 84 (mod 134)。

...

尤拉函式

為了討論更一般的形式的威爾遜定理和費馬小定理在 mod m (非素數) 中的應用，瞭解一位著名數學家尤拉的簡單結果會很有幫助。更具體地說，我們想討論一個函式，稱為尤拉函式 (或尤拉 φ)，記作 φ。

φ 函式做的事情非常簡單。對於任何自然數 m，φ(m) 給出 n < m 的個數，使得 gcd(n,m) = 1。換句話說，它計算在 mod m 中有多少個數有逆。我們將首先討論 φ(m) 在簡單情況下的值，然後從基本結果推匯出一般 m 的公式。

例如，令m = 5，則 φ(m) = 4。由於 5 是質數，5 以下的所有非零自然數（1、2、3 和 4）都與其互質。所以，在模 5 中有 4 個數具有逆元。實際上，如果m 是質數，則 φ(m) = m - 1。

我們可以將上述情況推廣到m = p^r，其中p 是質數。在這種情況下，我們嘗試使用計數論證來計算 φ(m)。注意，m 以下有p^r 個自然數（0、1、2 ... p^r - 1），因此 φ(m) = p^r -（n < m 且 gcd(n,m) ≠ 1 的個數）。我們這樣做是因為計算沒有模m 逆元的n 的個數更容易。

模m 中的一個元素n 沒有逆元當且僅當它與m 共有公因子。但m 的所有因子（不等於 1）都是p 的倍數。那麼，在模m 中有多少個p 的倍數呢？我們可以列出它們，它們是

$0,p,2p,\cdots ,p^{r}-p\!$

其中最後一個元素可以寫成 (p^r-1 - 1)p，因此有 $p^{r-1}\!$ 個p 的倍數。因此，我們可以得出結論

$\phi (p^{r})=p^{r}-p^{r-1}\!$

現在我們擁有了推匯出任意m 的 φ(m) 公式所需的所有工具。

根據算術基本定理，任何自然數m 都可以唯一地表示為質數的乘積，即

$m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\!$

其中 p_i 對於 i = 1, 2 ... r 是不同的質數，而 k_i 是正整數。例如，1225275 = 3×5²×17×31²。從這裡開始，讀者應該嘗試推匯出以下結果（CRT 可能會有所幫助）。

尤拉函式 φ

Suppose m can be uniquely expressed as below
  $m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\!$
then
  $\phi (m)=(p_{1}^{k_{1}}-p_{1}^{k_{1}-1})(p_{2}^{k_{2}}-p_{2}^{k_{2}-1})\cdots (p_{r}^{k_{r}}-p_{r}^{k_{r}-1})\!$

利用尤拉函式，我們可以推匯出費馬小定理的更一般情況，即

$a^{\phi (m)}\equiv 1{\pmod {m}}\$

威爾遜定理

一般m 的威爾遜定理指出，模m 中所有可逆元素的乘積

等於 -1，如果m 只有一個質因子，或者m = 2p^k 對於某個質數p

等於 1，對於所有其他情況

模m 的可逆元素是指一個自然數n < m，使得 gcd(n, m) = 1。自逆元素是指其逆元與其自身相同的元素。

在質數p 的威爾遜定理的證明中，1 到p - 1 的所有數都有逆元。對於一般的m 來說，情況並非如此。實際上，可以肯定的是 (m - 1)! ≡ 0 (mod m)，出於這個原因，我們改為考慮模m 中所有可逆元素的乘積。

對於m = p 是質數的情況，我們還利用了 1 和p - 1 是唯一平方後等於 1 的元素這一事實。實際上，對於m = p^k，1 和m - 1（≡ -1）是唯一的自逆元素（見練習）。但對於一般的m 來說，情況並非如此。例如，我們取m = 21。在模 21 算術中，以下每個數都有其自身作為逆元

1, 20, 8, 13

那麼，我們如何說所有可逆元素的乘積等於 1 呢？

我們使用上面描述的 CRT。讓我們考慮m = 2p^k 的情況。根據 CRT，模m 中的每個元素都可以表示為一個二元組 (a,b)，其中a 可以取值為 0 或 1，而b 可以取值為 0、1、... 或p^k - 1。每個二元組都唯一地對應於一對同餘方程，並且可以對乘法進行分量式操作。

利用上述資訊，我們可以輕鬆列出所有自逆元素，因為 (a,b)² ≡ 1 意味著 (a²,b²) = (1,1)，所以a 是模 2 中的可逆元素，而b 是模p^k 中的可逆元素，所以a ≡ 1 或 -1，b ≡ 1 或 -1。但在模 2 中 1 ≡ -1，所以a = 1。因此，在模m = 2p^k 中有 2 個元素是自逆的，它們是 (1,1) = 1 和 (1, -1) = m - 1。所以，在這種情況下，結果與m 只有一個質因子時相同。

對於m 有多個質因子且m≠ 2p^k 的情況。假設m 有n 個質因子，那麼m 可以表示為一個n 元組。假設m 有 3 個不同的質因子，那麼m 的所有自逆元素是

1. (1,1,1)
2. (1,1,-1)
3. (1,-1,1)
4. (1,-1,-1)
5. (-1,1,1)
6. (-1,1,-1)
7. (-1,-1,1)
8. (-1,-1,-1)

它們的乘積是 (1,1,1)，它對應於模m 中的 1。

練習

1. 令p 為質數。證明在模p^k 算術中，1 和p^k - 1 是唯一的自逆元素。

...待續

費馬小定理

如前一節所述，並非每個元素都可逆（即具有逆元）模m。費馬最後定理的廣義版本使用了尤拉函式，它指出

$a^{\phi (m)}\equiv 1{\pmod {m}}\!$

對於所有滿足 gcd(a,m) = 1 的a ≠ 0。這很容易從威爾遜定理的廣義版本中看出。我們使用類似於費馬小定理證明的技術。我們有

$(ab_{1})(ab_{2})\cdots (ab_{\phi (m)})\equiv b_{1}b_{2}\cdots b_{\phi (m)}{\pmod {m}}$

其中 b_i 是模 m 的所有可逆元素。根據威爾遜定理，所有可逆元素的乘積等於，例如，d (= 1 或 -1)。因此我們得到

$a^{\phi (m)}d\equiv d{\pmod {m}}\!$

這實際上是費馬小定理的陳述。

雖然費馬小定理非常簡潔，但在某種程度上它是不精確的。例如，取 m = 15 = 3 × 5，我們知道如果 a 模 15 有逆，則 a^φ(15) = a⁸ ≡ 1 (mod 15)。但 8 太大了，我們只需要 4，這意味著 a⁴ ≡ 1 (mod 15)，對於所有具有逆元的 a（讀者可以驗證）。

卡邁克爾函式 λ(m) 是最小的數字，使得對於可逆的 a，a^λ(m) ≡ 1 (mod m) 。習題集 中的一個問題涉及到這個函式。

練習

...待續

二階扭轉分解

很明顯，分解一個大數可能非常困難。例如，給定 76372591715434667 是兩個素數的乘積，讀者可以分解它嗎？如果沒有好的計算機代數軟體的幫助，這項任務幾乎是不可能的。截至今天，還沒有已知的有效的通用演算法可以將一個數分解成素數因子。

然而，在某些特殊情況下，分解可能很容易。我們將考慮二階扭轉分解方法。模 m 算術中的二階扭轉元素是一個數 a，使得 a² ≡ 1 (mod m)。

讓我們考慮模 21 算術中的一個例子。注意，使用中國剩餘定理，我們可以將模 21 中的任何數表示為一個二元組。我們注意到二階扭轉元素是 1 = (1,1)，13 = (1,-1)，8 = (-1,1) 和 20 = (-1,-1)。我們感興趣的是數字 13 和 8，因為 1 和 20 (≡ - 1) 顯然是二階扭轉的，我們稱這些數字為平凡的二階扭轉。

現在，13 + 1 = (1,-1) + (1,1) = (2,0)。因此 13 + 1 = 14 是一個與 21 有公因子的元素，因為 14 的二元組表示中的第二個分量為零。因此 GCD(14,21) = 7 是 21 的一個因子。

上面的例子非常愚蠢，因為任何人都可以分解 21。但是 24131 怎麼辦呢？分解它並不容易。但是，如果我們知道 12271 是一個非平凡的（即 ≠ 1 或 -1）二階扭轉元素，那麼我們可以得出結論，gcd(12271 + 1,24131) 和 gcd(12271 - 1,24131) 都是 24131 的因子。事實上，gcd(12272,24131) = 59 和 gcd(12270,24131) = 409 都是 24131 的因子。

更一般地，設 m 為一個合數，t 為模 m 的一個非平凡的二階扭轉元素，即 t ≠ 1，-1。那麼

gcd(t + 1,m) 整除 m，並且

gdc(t - 1,m) 整除 m

這可以用中國剩餘定理來解釋。

我們將解釋 m = pq 且 p 和 q 為素數的情況。給定 t 是一個非平凡的二階扭轉元素，則 t 有表示 (1,-1) 或 (-1,1)。假設 t = (-1,1)，則 t + 1 = (-1,1) + (1,1) = (0,2)，因此 t + 1 必須是 p 的倍數，因此 gcd(t,m) = p。在另一種情況下，t - 1 = (-1,1) - (1,1) = (-2,0)，所以 gcd(t - 1,m) = q。

因此，如果我們得到一個非平凡的二階扭轉元素，那麼我們實際上已經找到了一個（甚至可能多個）素數因子，這在分解這個數方面大有幫助。在大多數現代公鑰密碼學應用中，要破解系統，我們只需要分解一個有兩個素數因子的數。在這方面，二階扭轉分解方法非常有效。

當然，找到一個非平凡的二階扭轉元素也不是一件容易的事。所以，網際網路銀行暫時還是安全的。順便說一下，76372591715434667 = 224364191 × 340395637。

練習

1. 給定 18815 是模 26176 的一個二階扭轉元素。分解 26176。

…待續

下一節

下一節： 乘法群

習題集 習題集