高中數學擴充套件/素數

高中數學擴充套件

---

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

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

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

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，而 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

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 的素數被稱為 梅森素數，以法國僧侶/業餘數學家命名。

有用的外部資源

• "素數頁面。素數研究、記錄和資源"

>> 下一節： 模運算