高中數學擴充套件/素數

高中數學擴充套件

---

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

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

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

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。

由於計算機非常擅長進行算術運算，我們可以透過簡單地指示計算機用 2、3、5、7 ... 依次除以x來計算出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

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

有用的外部資源

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

>> 下一節： 模算術