簡介
費馬公式相關
所謂質數或稱素數,就是一個正整數,除了本身和 1 以外並沒有任何其他因子.例如 2,3,5,7 是質數,而 4,6,8,9 則不是,後者稱為合成數.從這個觀點可將整數分為兩種,一種叫質數,一種叫合成數.(有人認為數目字 1 不該稱為質數)著名的高斯「唯一分解定理」說,任何一個整數.可以寫成一串質數相乘的積.
(例1) ,, , , , ,這就是說,任何數都由質數構成的.
(例2) 2=(1×2),3,5,7,11…均為質數.而4,6,8不為質數.(因為最少還有因數2)
由於質數本身的奇異性使人無法一把抓住它出現的規律,抓住它出現的特性甚至不知道它實際分布的情形.簡單來說,給你一個正整數,你竟不可知道它是否是一個質數,即使你用盡了方法,證明它不可能是一個質數,但竟無法分解它,舉例來說:211-1=2047 可以分解成 .267-1 呢 據說美國代數學家 Frank Neloon Cole花了三年多才發現的.自然那時「電腦時代」還未來臨,只能靠無限的耐心與毅力,再加上一副長於計算數目的訓練才弄得出來.但有了電腦似乎好不了多少,數目字加大了,困難依舊.1931年 D.H. Lehmar 證明了 2257-1 是一個大合成數.大!不錯.它等於 231,584,178,474,632,390,847,141,970,017,375,815,706,
539,969,331,281,128,078,915,168,015,826,259,279,871
一個78位數字的大數,到目前仍未有人或電腦能分解它!
因此,雖然知道一個數目是否質數也許沒有多大用處,但仍是很有趣味,最少在找它的過程中會引起很多方法論的問題.
質數的特性
1質數除了2之外,必為奇數.(換句話說,2是最小的質數,也是唯一的偶數)
2「1」不算是質數.
3「算術基本定理」:比1大的任何整數,必可分解為質因數的乘積,且表示的方法是唯一的.
質數的個數與求法
1歐幾里德證明了「質數必有無限個」
2「Eratosthenes」濾套
若要求從2到n的質數,只要檢查n是否可被不大於的質數整除即可.要判斷313是否為質數,則只要檢查313是不是可以被小於或等於17的質數整除即可.
3質數有沒有一種特殊的型式呢
Mersenne質數:型如,若為質數時稱之(但質數不一定型如,
例如就非質數.)目前已知有3, 7, 31, 127,等38個,還在尋找中…
費瑪質數:型如,當n=0到4時.(但質數不一定型如,例
如n=5時,非質數.)
【注】型如稱為「費瑪數」,而費瑪質數只有3 , 5, 17 , 257 , 65537等五個.
4可不可以用一個公式,表示出所有的質數呢
(1)歐拉::在x=0,1,2…40時,可得41個質數
(1)勒真德::在x=0,1,2…28時,可得29個質數
:在x=0,1,2…79時,可得80個質數
:在x=1,2…11000時,可得11000個質數
●但是,沒有一個多項式可表示出所有的質數
為什麼要找質數
「既然質數有無限多個,那么為什麼數學家要投入那么多的心力一直尋找更大的質數呢 」
簡單的說,數學家就和一般人一樣,「你有收藏東西的興趣習慣嗎 」「喜歡在比賽中得到名次嗎 」這個都是理由之一.回答這個問題,可以用幾個方向來說明,
一,這是傳統!
在西元前300年的歐幾里德已經開始這個追求!他在「幾何原本」中提及完全數的概念,其中和麥司尼質數產生了關聯,開啟了研究之門,之後大數學家如費瑪,歐拉,麥司尼,笛卡爾…相繼投入這個追尋的工作中.也就在尋找大的質數的過程中,對基本數論有很大的助益,因此這個尋找的傳統值得被繼續～
二,它的附加價值!
因為美國的政治上的目的,才有把人送上月球的創舉,但是追尋大的質數例如像麥司尼質數,對社會影響的卻是持續不斷的,它的副加價值在於不斷促進科技的進步與人們的日常生活有用的東西材質的研發,也改進教育建設讓生活更有生產力.在尋找並紀錄麥司尼質數的過程中,讓老師可以帶領學生投入研究,這讓學生將研究的精神用於工作上,讓工程或科學的得以進步,當然這只是副加價的一部份而已.
三,人們喜歡美麗且稀少的物品!
如前文提及歐幾里德已經開始這個追求後,它是如此稀少(目前已知有30多個,還在尋找中),不僅如此它也是美麗的;數學上什麼叫作「美麗」 例如人們希望證明是簡短,明了,而且可以紿合舊知識讓你了解新的東西!而麥司尼質數的型式與證明都合符合上述的要求.
四,無上榮耀!
運動選手為什麼不斷追不更高,更快,更遠呢 難道是希望他們在工作上可以使用這些技巧嗎 不是吧,它們都是渴望競爭,為了榮耀(to win)!險峻的峭壁和高山峻岭對於喜歡攀岩,登山的人,有無法抗拒的魅力,數學的探索也是如此,看著無法想像巨大的數字竟是質數時那種心情是相同的,因此繼續尋找下一個的渴望,豈是語言可以形容
人們當然需要務實,但是也需要好奇心和不斷嘗試的精神,才能而不斷進步.
五,對電腦的考驗!
當電腦的發明之後,人們可以藉由電腦的計算去找麥司尼質數,因為檢驗一個已知的質數都要經過十億次以上的計算才會計算出來(以電腦來算當然很快),這時候就是測驗電腦穩不穩定的好時機,Intel的Pentium處理器,就被Thomas Nicely在計算twin prime constant時,找到有bug存在.
六,了解質數分布的情形!
雖然數學不是實驗的科學,但是在我們會用例子去檢驗我們的猜測,當例子愈來愈多時,我們也會更了解事實,而質數的分布情形這是如此,例如高斯在看過質數表之後猜測了質數定理(prime number theorem),這個定理在1896由哈達瑪(Hadamard)及普辛(Pouusin)分別證得:
質數是自然數的一部份,有趣的是,它卻與自然數的個數一樣多,也有無窮多個.兩千多年前,古希臘數學家就從理論上證明了這一點.不過,質數看上去要比自然數少的多.有人統計過,在1到1000之間,有168個質數;在1000到2000之間,有135個質數;在2000到3000之間,有127個質數;而在3000到4000之間,就只有120個質數了,越往後,質數就會越稀少.那么,怎樣從自然數裡把質數給找出來呢 公元前三世紀,古希臘數學家埃拉托塞尼(Eratosthenes)發明了一種很有趣的方法.埃拉托塞尼常把數表寫在塗了白臘的木板上,遇到需要划去的數,就在那個數的位置刺一個孔;隨著合數逐一被劃掉,木板上變得千瘡百孔,像是一個神奇的篩子,篩掉了合數,留下了質數.所以,人們將這種求質數的方法叫做"埃拉托塞尼篩法".
1. 我們把1~100的自然數,按照順序列成一張百數表.(如下表)
2. 首先把1劃掉,因為1既不是質數,也不是合數.
3. 接下來一個數是2,它是最小的質數,應予保留.但2的倍數一定不是質數,應該全部劃掉;也就是從2起,每隔1個數就劃掉1個數.
4. 在剩下的數中,3是第一個未被劃掉的數,它是個質數,應予保留.但3的倍數一定不是質數,應該全部劃掉;也就是從3起,每隔2個數就劃掉1個數.
5. 在剩下的數中,4已被劃掉了,其餘的數,5成為第一個未被劃掉的數,它是質數,也應予以保留.但5的倍數一定不是質數,應該全部劃掉;也就是從5起,每隔4個數就劃掉1個數.
6.仿照步驟1～5,繼續劃下去,數表上最後剩下的就是1~100之間的質數了.
埃拉托塞尼篩法
這種方法是世界上最古老的一種求質數的方法,它的原理很簡單,運用起來也很方便.現在,憑著經過改進後的埃拉托塞尼篩法,數學家們已把10億以內的質數全都篩出來了.怎樣找質數呢 這個問題據說自希臘及中國周朝已有人在問這個難題了.下面是一些初步查詢.
質數是無窮.這很早就證明了.因若 p1=2, p2=3, pn 是最初 n 個質數,則新數目 必由一個不等於 p1, p2, , pn 中任一個質數的新質數所除盡,故而 pn+1 存在了;且
舉例說,
但 30031=59 x 509
證明了 ,不必是質數.
考慮
f(n) 形式中是否有無限個質數存在或 f(p) 中是否有無限合成數存在呢
怎樣證明 n 是一個質數呢
傳統的「篩法」是將任一個數n的可能因子查證,簡化後;只要過濾所有小於的質數即可以了.就是n若是合成數,必有一個小於的質因數.如 3,5,7,11,13,等等.目前零碎地查質數的方法固然有,但仍無一萬全之方.
費馬的猜測
17世紀時,有個法國律師叫費馬(Fermat,1601-1665),他非常喜歡數學,常常利用業餘時間研究高深的數學問題,結果取得了很大的成就,被人稱之為"業餘數學家之王".費馬研究數學時,不喜歡搞證明,喜歡提問題;他憑藉豐富的想像力和深刻的洞察力,提出一系列重要的數學猜想,深刻地影響了數學的發展,他提出的"費馬最後定理",幾百年來吸引了無數的數學家,直到1993年才由中國數學家毛桂成用費馬所說的絕妙證明方法給出了證明.
他在西元1640年提出了一個公式:『 2+1』,他驗算了n等於1到4的情況,發現都是質數以後(如下表),就直接猜測只要n是自然數,這個公式求出來的一定是質數.」
n
2+1
1
2+1=5(質數)
2
2+1=17(質數)
3
2+1=257(質數)
4
2+1=65537(質數)
1. 費馬最喜歡的數學分支是數論,他曾深入研究過質數的性質,他發現了一個有趣的現象.計算 ＝ 它是一個質數嗎 .
2. 那 又是多少呢 它是一個質數嗎 .
3. 再下去, 是多少呢 它是一個質數嗎 .
4. 最後, 是多少呢 它是一個質數嗎
解答:
=5;它是質數.
=17;它是質數.
=257;它是質數.
=65537;它是質數.
費馬當年並沒有繼續算下去,他猜測說:只要n是自然數,由這個公式 得出的數一定都是質數;這是一個很有名的猜想,由於n＝5之後演算起來很麻煩,很少有人去驗證它.
1732年,大數學家歐拉認真研究了這個問題,它發現費馬只要再往下演算一個自然數,就會發現由這個公式得出的數不全是質數.
n＝5時,＝＝4294967297,4294967297可以分解為641×6700417,它不是質數.也就是說,費馬的這個猜想不能成為一個求質數的公式.實際上幾千年來,數學家們一直在尋找這樣的一個公式,一個能求出所有質數的公式;但直到現在,誰也未能找到這樣一個公式,而且誰也未能找到證據,說這樣的公式就一定不存在;這樣的公式存不存在,也就成了一個著名的數學難題.
費馬在數學史上,是一位非常重要的人物,雖然費馬的公式是錯誤的,但是數學家從另一個方向來尋找大質數,也就是之前講完全數時提到的:『如果2-1是一個質數,那么N=2(2-1)一定是個完全數.』於是,數學家們努力驗算不同的 n值,也找出了一些質數,但是由於數字太大,當時又沒有電腦的幫忙,所以很多結果都是錯的.到了十七世紀,一位法國的天主教修士梅森尼提出了:在 n不大於257的情況下,共有十一個質數.雖然他的結果同樣有不少錯誤,但是後人就把『2-1』這種形式的質數叫做『梅森尼質數』.」
費馬定理
費馬一心想要找出一個求質數的公式,結果未能成功.人們發現,倒是他無意提出的另一個猜想,對尋找質數很有用處.
費馬猜測說;如果 是一個質數,那么,對任何自然數n,( )一定能被 整除.這一回費馬猜對了,這個猜想被人稱作費馬小定理.例如:11是質數,2是自然數,所以( )一定能被11整除.
利用費馬定理,這是目前最有效的鑑定質數的方法.要判斷一個數n是不是質數,首先看它能不能整除( ),如果不能整除,它一定是合數;如果能整除,它就"極可能"是質數.現在,在電子計算機上運用這種新方法,要鑑定一個上百位的數是不是質數,一般只要15秒鐘就夠了.
質數公式表
f(x)公式
在100以下令f(x)成合成數的x值
總數
x2-79+1601
80, 81, 84, 89, 96
5
x2+x+41
40,41,44,49, 56, 65, 76,81,82,84,87,89,91,96
14
2x2+29
29, 30, 32, 35, 39,44, 50, 57, 58, 61,63, 65,
25
72,74,76, 84,87, 88, 89,91,92,94,95, 97, 99
6x2+6x+31
29, 30, 31, 34, 36,41,44, 51, 55, 59, 61, 62,
25
64,66, 69,76,80, 84, 86. 87, 88, 92, 93, 97, 99
3x2+3x+23
22,23,27, 30, 38,43, 44,45,46,49, 51, 55, 56, 59,
28
62,66,68, 69,70,78, 85, 87, 88, 89, 91,92,95,96
像質數公式 x2+x+41,我們能找到連續 40 個(由 0 到 39)的質數,有沒有一條質數公式 f=x2+x+b,能使 (b-1) 個連續 x 值使 f(x) 都是質數呢 有人曾用電算機去找,結果查出如果有,則 b 值一定要超過 1,250,000,000,而且最多只有一個.看來這個問題大概解不了.
現在的數學家們在質數這個領域裡,有兩個重要的研究方向:一個是利用各種更有效率的篩法,不斷地往更大的數裡面去搜尋質數;另外就是尋找新的『梅森尼質數』.到西元1996年為止,數學家已經藉由電腦運算,知道1020以內有多少質數了;另一方面,在西元1999年六月,數學家也發現了第三十八個『梅森尼質數』: 26972593-1,這同時也是到目前為止發現的最大質數!它是一個2098960位數.
- -
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
