有關質數的一些小知識

2021-02-19 教數學的螢火蟲

#素數不是吃素的#  #數學啟蒙#  有關質數的一些有趣小知識

之前，我寫過兩篇介紹素數的小文章

【給你多少個數字， 只用乘法可以得到全部正整數？——聊聊質數（素數）】給你多少個數字， 只用乘法可以得到全部正整數？ ——聊聊質數（素數）

【有關質數的兩個有名猜想（1）——哥德巴赫猜想】有關質數的兩個有名猜想之一——哥德巴赫猜想

今天我再就「素數有無窮多個」以及素數的一些有趣的知識介紹給大家。

首先，讓我們再一次重溫100以內的素數。

觀察這個表，你會發現什麼？最簡單的觀察結果是，

1、從十位數開始，素數的個位數字不可能是2、4、5、6、8、0。

 這個很容易證明，個位數字是2、4、6、8、0的數字都是偶數，可以被2整除，個位數字是5的數字可以被5整除。 

2、2是唯一的偶素數。

還有什麼觀察結果嗎？二十以內素數有8個，佔到了40%的比例。100以內的素數一共有25個，佔25%。然後再讓我們來看看1～1000有幾個素數吧！ 

（1000以內的素數表）

有168個，共佔1～1000的16.8%。你肯定也發現了，素數在全體整數中所佔的比例越來越低了，換句話說，素數越來越稀少了！

那是不是某個數字之後，就再也沒有素數了呢？也就是說會不會素數是有限個呢？ 

（歐幾裡得的《幾何原本》，跨越時空的偉大著作）

不會的，歐幾裡得在《幾何原本》中給出了一個完美的證明。

首先假設素數有有限個，那麼就存在一個最大素數，我們用N表示這個最大素數。這就意味著在N之後，再也沒有素數了。那麼我們現在來看這樣一個數字：

M= 1*2*3*…*N+1  

它是1到N的所有數字的乘積再加上1的和， 顯然是大於N的。 根據假設，所有的素數在1～N的範圍內，所以這個數字為非素數（又稱為合數）。根據算術基本定理，任何一個合數，都可以表示為若干個素數的乘積，也就是說，一個合數是能夠被某個比它小的素數整除的。

可是，我們同時也發現，從2～N的所有素數除以M，餘數都是1。 只有1和M才可以整除M。根據素數的定義， M顯然是一個素數。這就和我們由素數有限假設得到的結論「所有素數不大於N」矛盾了！也和我們根據假設得到的，M 是一個合數矛盾了！ 因此我們的邏輯推理的起點——「素數有有限個」就是錯的，是不成立的。因此，素數有無窮多個。 

（以極坐標形式排列的素數，形成美麗的螺旋）

歐幾裡得的證明和上述的思路是一致的，但要更加簡潔一些，為了便於理解和減少符號，我稍做了改動。總的來說，這個證明思路實在是太妙了！可以算是數學史上最著名的反證法證明之一了！

我之前也提到過，無窮多個素數，要全部找出來，靠一個一個驗證是不可能的。比如 判斷728587是否為質數。

首先做一下估算， 800*800=640000， 900*900=810000；

再進一步估算 820*820=672400 ，860*860=739600；

所以我們從820 開始一個個驗證大於820的每一個整數是否整除728587，通過不停的驗證，最終發現827整除728587，商是881。

通過這個例子，我們不難發現，在計算機發明之前，驗證一個大數是不是質數需要進行很多次的乘法、除法運算，還是比較困難的。特別是對於一些極其巨大的數字，運算量就更加大了。 

 那換一個思路，能不能找到一個什麼公式， 這個公式能計算出包含所有的素數呢？

目前，還沒有這樣的公式。但大牛人歐幾裡得觀察發現， 2的素數次方 減去1 例如 

2的2次方 -1 =3，    2的3次方-1=7

2的5次方-1=31  ，  2的7次方-1=127 

都是素數。看到這裡你一定會猜測，你也許會這樣猜測：

是不是所有的素數都可以寫成 「2的素數次方減去1   」。這個容易驗證， 11， 17 都不能這樣寫，所以顯然這個猜測是不對的；

那麼退一步，是不是：2的素數次方減去1   都是素數呢？   

這樣的猜測是很棒的，但正如著名學者胡適所說，做學問要「大膽假設，小心求證」。這個結論還需要進一步證明或者找出反例。

這個問題的答案是，一部分是，但不都是。例如，人們發現， 2的67次方減去1 就不是質數。

不過，這倒是為我們尋找素數提供了一個好辦法。 如果不用這個思路，那麼我們需要一個個驗證，得到素數，現在如果我們只想得到一個儘可能大的素數，我們就可以嘗試用這樣的步驟：

1、找到已知的一個很大的素數p；

2、求2的p次方減去1；

3、驗證這個數是不是素數。

這實在比一個一個數驗證 來的快多了！目前為止人類找到的最大素數——2的74207281次方減去1，就是利用這個公式得到的。

最後需要指出的是，這類可以寫成

2的素數次方減去1

的素數我們把它們稱為梅森（Mersenne）素數，以紀念研究這類素數的17世紀法國數學家Martin Mersenne。 

相關焦點

  • 數學小知識 | 判斷質數的方法
    （規定1即不是質數也不是合數）。自古以來，數學家們就想弄明白：自然數中到底有多少個質數，質數的分布有什麼規律，如何去尋找質數。步驟如下:❶ 先把1刪除；❷ 讀取數列中當前最小的數2，再把2的倍數刪除；❸ 讀取數列中當前最小的數3，再把3的倍數刪除；❹ 依次進行下去，直到把所求範圍內的數均讀取完。
  • 長沙小升初數學必背基礎知識:質數
    在長沙小升初的備考過程中，數學科目需要記憶的知識雖然不多，但往往差之毫厘失之千裡。所以在備考數學的過程中，大家一定要把基礎知識和公式準確的記憶下來。長沙奧數網編輯整理了長沙小升初階段數學必背的基礎知識，供小升初學生參考。 　　什麼叫質數？ 　　質數又稱素數。
  • 最小的質數最小的合數 最小的質數和最小的合數是多少
    最小的質數是2，最小的合數是4。質數是指在大於1的自然數中，除了1和它本身以外不再有其他因數的自然數。合數是指在大於1的整數中除了能被1和本身整除外，還能被其他數(0除外)整除的數。
  • 樹上微精讀——自然數的質數判定,合數分解與孿生質數分布
    閱讀本書只需具備一些初等數論知識。儘管本書探討的是世界難題，但對於不具備高深數論知識的普通數學愛好者而言，大家不僅能讀懂書中全部內容，而且能學會在自己的計算機中進行大數的數性判定和分解，從而激發人們對學習數論的興趣。同時本書也是能夠激發數論工作者創新靈感的一本參考書。
  • 教程資源|判斷質數和合數程序
    在數學中經常會看到質數和合數，但很多人卻不知道什麼是質數，什麼是合數？根據算術基本定理，每一個比1大的整數，要麼本身是一個質數，要麼可以寫成一系列質數的乘積;而且如果不考慮這些質數在乘積中的順序，那麼寫出來的形式是唯一的，最小的質數是2。質數又稱素數，個數是無窮的，一個大於1的自然數，除了1和它本身外，不能被其他自然數整除，換句話說就是該數除了1和它本身以外不再有其他的因數。
  • 何時攻破質數難題,探尋神奇的質數
    在汽車變速箱齒輪的設計上，相鄰的兩個大小齒輪齒數設計成素數，以增加兩個齒輪內兩個相同的齒相遇嚙合次數的最小公倍數(即是這兩個齒輪齒數的乘積，兩個素數的最小公倍數就是它們的乘積)，這可以防止有的齒經常和另一個齒輪的某一齒單一接觸(特別是當這個齒設計有一些小的缺陷時，任何機械工程都是有一些小誤差的)，可增強耐用度、減少故障。
  • 暖心春運,安全是最小「質數」
    暖心春運，安全是最小「質數」時間：2017-01-24 22:57   來源：川北在線原創（guangyuanol.cn）   責任編輯：毛青青 川北在線核心提示：暖心春運，安全是最小質數 前一段時間，數學家張益唐的孿生素數猜想在網絡上爆炸性傳播，讓我們對質數這一概念有了更深的理解。
  • 最小的質數是什麼?最小的合數是什麼? 自然數中最小的質數是多少最...
    最小的質數是2，最小的合數是4。質數又被稱為素數，指的是一個大於1的自然數，除了1和它自身外，不能被其他自然數整除的數，反之則被稱為合數。分為偶數和奇數，合數和質數等。(挪威數學家布朗，1920年)　　4、一個偶數必定可以寫成一個質數加上一個合成數，其中合數的因子個數有上界。(瑞尼，1948年)　　5、一個偶數必定可以寫成一個質數加上一個最多由5個因子所組成的合成數。後來，有人簡稱這結果為 (1 + 5)(中國潘承洞，1968年)　　6、一個充分大偶數必定可以寫成一個素數加上一個最多由2個質因子所組成的合成數。
  • 質數與合數的暢想
    >第一環節：概念理解T：今天來學習質數與合數，關於質數與合數，你能夠提出什麼問題呢？（孩子自己各寫兩個質數和合數）T：1到底是質數還是合數？質數與合數 第三集 知識鞏固第三環節知識鞏固T：認識了這麼多質數和合數，在百數表中找到所有的質數（s嘗試尋找）T：可以通過排除進行尋找先排除1，再排除2的倍數（2除外），然後5的倍數（2除外），3的倍數（3除外），7的倍數（7除外）……最後得到
  • 數學基礎概念 | 質數、合數!
    合數是由若干個質數相乘而得到的。所以，質數是合數的基礎，沒有質數就沒有合數。這也說明了前面所提到的質數在數論中有著重要地位。歷史上曾將1也包含在質數之內，但後來為了算術基本定理，最終1被數學家排除在質數之外，而從高等代數的角度來看，1是乘法單位元，也不能算在質數之內，並且，所有的合數都可由若干個質數相乘而得到。
  • 一部與孤獨有關的電影——《質數的孤獨》
    「質數只能被一和它自身整除。在自然數的無窮序列中，它們處於自己的位置上，和其他所有數字一樣，被前後兩個數字擠著，但它們彼此間的距離卻比其他數字更遠一步……在質數當中還有一些更加特別的成員，數學家稱之為『孿生質數』，它們是離得很近的一對質數，幾乎是彼此相鄰。」以上是原著中的描述，用在馬蒂亞和愛麗絲身上再貼切不過。
  • 教師招聘數學《 質數和合數》說課稿
    接下來我將對學情進行分析：小學階段的學生他們年齡偏小，活潑好動，想像力豐富，以具體的形象思維為主，在課堂表現活躍，希望得到老師的認可，同時他們注意力集中時間短，易被外界環境分散注意力;另一方面從知識儲備方面來看，在前面已經學習了因數和倍數，對數的特點以及數與數之間的關係有了一定的認識，為本堂課的學習打下了基礎。
  • 質數的最小間隔有上限,人的奮鬥沒有上限 |張益唐的故事
    數學家的成果往往很難向大眾介紹，因為僅僅聽懂他們在研究什麼問題都需要很多背景知識。而且張益唐是當代人，一般而言，越往後的就離普通人越遠。然而，張益唐卻是個大大的反例，他的研究成果是很容易解釋的。容易到什麼程度呢？小學水平就夠了！首先，大家都知道什麼是質數（prime number），對吧？質數就是只能被1和自己整除的自然數，也被稱為素數。
  • 孤獨得像質數一樣
    質數指的是只能被1與自身整除的自然數，由最小的2開始，往後是3，5，7…… 與質數相對的概念是合數，在2與3之後，質數便永遠被一個或多個合數隔開。    在小說的男主人公馬蒂亞眼中，自己就是一個「孤獨而多疑」的質數。小學三年級時，他與低智商、愛尖叫的妹妹一同去參加生日聚會。由於害怕妹妹給自己丟臉，馬蒂亞半途把她留在街頭，不料妹妹從此失蹤。
  • 質數、合數
    合數是由若干個質數相乘而得到的。所以，質數是合數的基礎，沒有質數就沒有合數。這也說明了前面所提到的質數在數論中有著重要地位。歷史上曾將1也包含在質數之內，但後來為了算術基本定理，最終1被數學家排除在質數之外，而從高等代數的角度來看，1是乘法單位元，也不能算在質數之內，並且，所有的合數都可由若干個質數相乘而得到。
  • 128.質數的生成
    128．質數的生成 　　在證明某數是否為質數時，最基本的問題就是：確定某數是否為質數的唯一方法，就是找出其因數．長久以來，人們一直想找出表示質數的「公式」，但都徒勞無功．下面介紹一些前人努力的結果．
  • 《質數的孤獨》:孤獨的,不僅僅是質數
    》，[意]保羅·喬爾達諾著，文錚譯，上海譯文出版社2011年3月第一版，26.00元微涼的初秋，讀完《質數的孤獨》，眼前似乎已滿是片片翻飛舞動的落葉，掩卷嘆息之際，心中也不禁泛起些許蕭瑟的涼意。保羅·喬爾達諾則在《質數的孤獨》中描述了孤獨的一代，他們出生成長在上個世紀80年代後，生活和平富足，卻由於各種原由拒絕與世界溝通，或被世界排斥，而不得不如質數一樣，永遠孤獨。義大利80後帥哥保羅·喬爾達諾是粒子物理學博士出身，處女作《質數的孤獨》一經出版便獲得義大利最高文學獎斯特雷加獎，顯示了他獨特的文學才華。作為小說，《質數的孤獨》結構簡單，故事情節清晰明了，讀起來流暢自如。
  • 數學課堂 | 什麼是質數和合數?
    例如，2、3、5、7 都是質數。2 是最小的質數。100 以內的質數：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97。（1） 查質數表。常見 100 以內質數表、1000 以內質數表。（2） 用試除法去判斷。用 2、3、5、7 等質數去試除。
  • 為什麼2是質數?1不是質數?
    基本上，了解自然數後，先知道奇數和偶數，然後就是質數和合數。質數某種意義上說是自然數的骨架。
  • 用Python判斷質數的嘗試
    問如何判定117是不是質數呢？我們會考慮分解117。分解的過程其實是將這個數逐個地去試驗性除以2、3、5、……，只要能被整除，那麼就不是質數，如果一直找不到可以整除的數，那麼就是質數。問題二：在數學上，進行質數判斷的計算，不會一直算到N-1這個數，只會算到N/2。因為除「1」以外，2是最小的因子了。如果N，能夠找到大於N/2的因子的話，那麼另外一個因子就會小於2，這是不可能存在的。因此在循環的時候，我們計算到N/2就夠了，在程序運行上講，可以節省很大的運行時間。這在程序設計上是非常必要的。