高中數學擴充套件/素數/文字

簡介

素數（簡稱素數）是一個自然數，它恰好有兩個除數：它本身和數字 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

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

有用的外部資源

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