為什麼這篇自然數表鄉民發文收入到精華區：因為在自然數表這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者E7lijah (InsfirE喚焰)看板C_Chat標題Re: [問題] 無限多的自然數跟質數...
自然數表 在 BeautyExchange.com.hk Instagram 的精選貼文
2021-09-24 16:09:58
最近難得看見歌神張學友頻頻露面，沒有巡迴演出的他留港給本地歌迷發放福利，與Gin Lee推出合唱歌《日出時讓街燈安睡》，旋律悠揚寓意深刻，說的，是一個關於加油、又無需太加油的故事。 【鬆手不佔有 方可擁有】 現代人很忙碌，忙碌著擁有、忙碌著得到，總以為擁有就等於富有，卻時時忘了自己是為了甚麼而擁有...
※ 引述《zax8419 (小火馬)》之銘言：
: 直接說結論: 一樣多
: 姑且身為一個有靠數學招搖撞騙的小廢廢 應該可以提供個簡單的解答
: 但我知道西洽存在112數學系拿卷畢業 然後現在應該在國外讀博的版友
: 偶而也有112數學系畢業 然後讀電機碩的版友
: 相比之下我就只是個廢物Q_Q
: 關於自然數與質數誰比較多 這個驗證方式應該分為兩個步驟
: 1.質數是否為無限多個?
: 2.若質數為無限多個 那質數與自然數如何比較?
: 首先1.
: 質數有無限多個。
: 其證明方式非常簡單 用最基本的反證法即可
: 因"質數有無限多個"與"質數為有限多個"為相反的命題
: 故先假設"質數為有限多個"
: 則我們可以從小到大 將所有質數編號 p_1,p_2,p_3......p_n p_n為最大的質數
: 而若我們寫出一個大數N為所有質數的乘積
: 則會發現N+1不能被以上所有的質數給整除(餘數皆為1)
: 那麼就可以得出N+1亦為一個質數 且比p_n還要大 與最初的命題矛盾
: 所以可以得知"質數有無限多個" Q.E.D
: 再來2.
: 無限多個的自然數 與 無限多個的質數 其數量一樣多
: 非常簡單
: 我們可以說
: "第一個"自然數為1 "第一個"質數為2
: "第二個"自然數為2 "第二個"質數為3
: "第三個"自然數為3 "第三個"質數為5
: ......
: 以此類推
: 所有"第N個"自然數都可以對應到一個數 同時"第N個"質數亦可對應到一個數
: 那麼儘管有點違反直覺 但實際上論"個數" 則自然數的個數與質數的個數是一樣多的
: 或者說 只要能找到任何一個無法同時存在有"第M個"自然數 但沒有"第M個"質數的狀況
: 就能說自然數的個數 與 質數的個數不相同
: 這種概念在所有的"可數集合"均成立
: 進階一點就像"有理數的的個數"也與"正整數的個數"是一樣多的
: 但是當命題拉到不是可數集合的時候 就不會那麼簡單了
: 就像無理數的個數有無限多個 正整數的個數也有無限多個
: 但無理數的個數卻是遠大於正整數的個數
: 不過要去說明就懶了 大概也沒人在乎
: 數學嘛 就是這麼反直覺 唉
其實你第一個證明有點瑕疵
令 N = 1 + p_1*p_2*...*p_k的作法
我能舉個反例：
1 + 2*3*5*7*11*13 = 30031 = 59*509
此時N可以表達成兩個不為{1,N}元素的自然數之乘積
不符合質數的定義，新造出的N不是質數
你當然可以說那我不管N了，此時59與509反而是你新發現的質數
但原本的證明敘述仍有瑕疵就是了，需要補充此時新的最大質數候選人換人這件事
有一個概念相似但比較嚴謹的證明：
同樣假設只存在有限k個質數p_1, p_2,..., p_i,..., p_k
i屬於{1, 2,..., k}
則對於任何自然數n≧2
有p_i|n (p_i能整除n)
這邊需要一個引理：
若a|b，且a|c
並假設b>c (感謝comp大糾正)
則a|(b-c)
這個證明很簡單
令b = x*a
c = y*a
b-c = (x-y)*a，其中x,y皆為整數
得a|(b-c)
回到質數無限多個的證明
令n = 1 + p_1*...*p_i*...*p_k
可推得p_i|(n-1)
再結合前述的p_i|n
我們有p_i|[n-(n-1)]=1，即p_i|1
但p_i必定≧2，不可能整除1，明顯矛盾
得證質數的數量不可能有限，即質數有無限個
再回到質數跟自然數是否一樣多的問題
數學上比較兩個集合的個數大小，可以用一一對應原則
概念上就是班上有40個人，老師不需要從1數到40
只要視線快速掃過每個座位都有人，就能確認座位數=人數
令R跟S為某兩個集合
若你能找到一個一一對應關係使每個R的元素對應到S
則|R|≦|S| (|R|代表R集合的大小)
而當|R|≦|S|與|R|≧|S|同時成立時，
則|R|=|S|
也就是說你若能R→S和S→R兩個方向上都找到一一對應關係的話，
那麼R跟S這兩個集合的大小相同
以上敘述對有限集合與無限集合皆適用
現在我們令N為自然數集合，P為質數集合
明顯地，|P|≦|N|，每個質數都能對應到一個自然數
所以我們只需要證明每個自然數也能對應到一個質數，
就能說明質數的數量跟自然數一樣多
這可以用費馬數做證明：
第n個費馬數可以表達成
F_n = 2^(2^n) + 1
已知任兩個費馬數皆互質，即任兩個費馬數的最大公因數是1，
也就是說任兩個費馬數必不會有共享的質因數
那麼對於每個費馬數F_n，我找出他最小的質因數P_n，
這個P_n必不等於其他費馬數F_m的最小質因數P_m
於是，對每個自然數n，我能對應到一個費馬數F_n，又再對應到一個質數P_n
我找到了將每個自然數都對應到一個質數的方法
所以|N|≦|P|
再結合|P|≦|N|
得證|P|=|N|，即質數的個數與自然數一樣多
btw我也不是數學系，有誤煩請糾正
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.217.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1684253332.A.27F.html
→ yang560831: 嗯嗯 我的答案跟小當家一樣05/17 00:09
推 nahsnib: 這個就數學系在分析導論的前幾堂課吧05/17 00:10
→ E7lijah: 我先 打那麼多誰看得完05/17 00:10
→ nahsnib: 比較有趣的是怎麼證明實數不可數，但又要用反證的05/17 00:10
→ E7lijah: 實數不可數的反證法不就是用經典的康托爾對角線證法嗎05/17 00:13
推 ashrum: 推這篇05/17 00:16
推 kaj1983: 不明覺厲05/17 00:16
→ ainamk: 這篇就是典型的會把圈外人嚇到對數學更沒興趣的文章…05/17 00:16
推 tkc7: 對角線那個想了好久才搞清楚他在幹嘛05/17 00:17
我當初想通之後覺得這招好屌推 thejackys: 原po什麼系05/17 00:19
也是理學院推 cerberus4523: 這裡是什麼版？05/17 00:19
推 kaj1983: 這裡本應是廢文板才對05/17 00:21
讓人看不懂的文算不算一種廢文→ kaj1983: 現在我搞不懂了05/17 00:21
推 ggchioinder: 要考試的時候搞懂過，現在看都忘記了05/17 00:22
※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 00:25:04推 sadmonkey: 任兩個費馬數互質有那麼trivial嗎？05/17 00:25
→ E7lijah: 回s大，沒有XD05/17 00:26
→ E7lijah: 但再寫下去我怕真的太多05/17 00:26
→ zax8419: 沒 你那個"反例"已經跟原命題衝突了 原命題已經假設最大05/17 00:27
→ zax8419: 質數了 在你的例子裡 最大的質數是13 那59跟509就不是一 05/17 00:27
→ zax8419: 個質數 要驗證也是拿2,3,5,7,11,13去驗證才對 05/17 00:27
推 yumenemu610: 差點忘了這裡是個學術書論壇 05/17 00:29
推 NicoNeco: 謝啦 你清楚地說明我上篇文章推文的疑惑 證明式不嚴謹 05/17 00:30
→ zax8419: 雖然你知我知天知地知59,509也是質數 但那跟原本假設的" 05/17 00:30
→ zax8419: 質數的最大值"相違背這樣 05/17 00:30
那我可以說，好 那麼59跟509不是「質數」，而是合數，但30031可以表達成兩個「合數」的乘積，還是哪裡怪怪的
→ NicoNeco: zax是用比較通俗的方式說明 這篇是寫成邏輯數學式這樣 05/17 00:32
※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 00:34:42推 hutao: 做個每日還這麼哈扣，不曉得以後會不會來0.999_=1 05/17 00:35
→ zax8419: 應該是可以直接說 "到這一步可以證明最大的質數不存在"這05/17 00:36
→ zax8419: 樣就好吧 05/17 00:36
→ zax8419: 幹 樓上0.999_=1 要開新戰場了嗎XD 05/17 00:36
→ E7lijah: 要請出戴德金分割了嗎XD05/17 00:38
推 jimmyVanClef: 這裡是什麼版阿這麼艱深 05/17 00:38
→ zax8419: 接著肯定就是 1+2+3+....=-1/12 了吧 05/17 00:38
推 nahsnib: 不是吧，這個真的不艱深啦，連我文組女友都聽得懂了05/17 00:39
→ E7lijah: 會來西恰的怎麼可能有女友 我書讀得少 別騙我 05/17 00:42
→ mayolane: 大哥怎麼這麼電，果然做電化學的個個都是天才 05/17 00:43
→ zax8419: 總而言之 我那個寫法本來就是反證法下的產物 出現明確問 05/17 00:43
→ zax8419: 題or反例=>矛盾 大概是這樣吧 不想再回一篇惹 05/17 00:43
推 raincole: 第一個證明沒有問題 05/17 00:47
→ raincole: 你舉出 30031 這個具體例子並不會造成該證明變得不完整 05/17 00:48
推 WayThuz: 假設質數的數量為有限，那我們只要 05/17 00:49
→ WayThuz: 作出一個不在上列有限個質數的質數，就可以得到矛盾 05/17 00:49
→ WayThuz: 從而得知質數有無限個 05/17 00:49
→ WayThuz: 這應該是zax大大的證明思路 05/17 00:51
推 raincole: 喔 不對 當我沒說 XD 我仔細看一下原文的字句確實是不太 05/17 00:55
→ raincole: 嚴謹的 比較好的方式應該是再分兩種情況：N+1 是質數和05/17 00:56
→ raincole: 不是質數 然後再分別得到矛盾 05/17 00:56
→ E7lijah: 同r大 不是說那個證明不行 而是至少補加點敘述才比較完05/17 00:57
→ E7lijah: 整 05/17 00:57
推 greg90326: 想起當年待數學系的痛苦回憶了 謝啦05/17 00:58
→ E7lijah: 不過我也想過針對這個瑕疵的敘述需不需要這麼計較 畢竟 05/17 00:59
→ E7lijah: 本來就是反證法推出的錯誤性質了 05/17 00:59
→ chordate: 用費馬數證是沒錯啦，但是要先證費馬數互質05/17 00:59
那就是另一篇了XD推 cmrafsts: 當然不是1阿，你們聽過p-adic number嗎?(X 05/17 00:59
大神請說 小弟洗耳恭聽→ zax8419: 樓上是神 05/17 01:00
※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 01:02:25→ chordate: 其實也不會太難就證F_n=F_1*F_2*...*F_(n-1)+2 05/17 01:11
→ E7lijah: 我知道證法 但文章已經太長 這裡寫不下(X 05/17 01:12
推 drm343: 那一天，大家想起過去的 ptt 是怎樣的狀況 05/17 01:33
推 derlin12345: 請數學小圈圈放過西恰 05/17 01:46
推 thelittleone: 我是不是走錯板了0.0 05/17 01:46
推 Hosimati: 其實就是他寫的不夠仔細，p_n是最大質數且N+1>p_n，故N 05/17 01:54
→ Hosimati: +1不是質數，又無法被的有限的n個質數的任一整除，矛盾 05/17 01:54
→ chordate: p-adic number就我的理解就是p進位表達（p為質數） 05/17 01:55
推 ym951305: 看你這篇文我恍神了三次 05/17 01:56
→ chordate: 同時加上一個特別的距離定義，讓小數點左右兩邊 05/17 01:56
→ chordate: 都可以是無窮的且收斂 05/17 01:56
→ chordate: 應該說小數點左邊才對 05/17 02:22
推 XFarter: 結果整片討論區沒有人提到阿列夫數或 Beth 也是蠻可惜的 05/17 02:33
推 weebeer626: 去Google了對角線證法，很666 05/17 03:07
推 zball: 0.999.. = 1, 跟 1/9 * 9 = 1 其實是一樣概念 只是很多人 05/17 03:27
→ zball: 對分數跟有理數理解還不夠而已 05/17 03:29
推 XFarter: 樓上是認真還是在唬爛？ 0.999999...要等於 1 也是需要被 05/17 03:36
→ XFarter: 嚴格定義的，光序理論就說不通05/17 03:36
推 z932210: 不明覺厲，但覺得很厲害。 05/17 03:46
推 physicsbest: 好文 推05/17 03:59
推 qoo350154: 為啥我看這篇文會怪怪的阿 05/17 04:11
推 et22639643: 抱歉進到數學版了……什麼這是西洽？05/17 06:45
推 fth862: 唉呦豆頁好痛 05/17 08:00
推 msbdhdfceb: 其實反證也可以通俗地解決，如果0.99…循環不等於1， 05/17 08:05
→ msbdhdfceb: 那兩者之間必然能找到無限多個非零實數，但你用你已 05/17 08:05
→ msbdhdfceb: 知的國高中數學邏輯去算就會發現你連一個非零實數都 05/17 08:05
→ msbdhdfceb: 找不到，只會條條大路通向兩者是同一個數 05/17 08:05
→ pot1234: 感覺不出哪裡有瑕疵，59，509比p_n大這件事就違反假設啊 05/17 08:14
→ pot1234: ？ 05/17 08:14
推 zseineo: 推個魔法 05/17 08:31
推 inmysis: 嗯嗯我也是這麼想的 05/17 08:31
推 yuanvio: 老師我選c 05/17 08:35
推 kirimaru73: 不管59和509是啥，他們都把原命題打爆了，所以反證法 05/17 08:47
→ kirimaru73: 還是成立 05/17 08:47
推 lolicon: 你不是數學系...你也打太多XD 05/17 08:51
推 Daha1AG: 恩恩對 我也是這麼想的 05/17 09:00
推 a1487546: 推，打這麼多我還是看完了 05/17 09:33
推 Aaron1002: 跟我想的一樣 05/17 09:35
→ qaz86368: 簡單說 質數若有限個 05/17 10:17
→ qaz86368: 分別是2,3,5...,p_k 這k個質數05/17 10:17
→ qaz86368: 那我們想像2*3*5*...*p_k+1 05/17 10:17
→ qaz86368: 所產生的數字05/17 10:17
→ qaz86368: 2*3*5*...*p_k+1 05/17 10:19
→ qaz86368: 若此數字本身就是質數05/17 10:19
→ qaz86368: 因為不能被2,3,5...,p_k 05/17 10:19
→ qaz86368: 這k個質數整除 05/17 10:19
→ qaz86368: 所以是新的質數 05/17 10:19
→ qaz86368: 若數字不是質數 即是合數 05/17 10:21
→ qaz86368: 則可進行質因數分解 05/17 10:21
→ qaz86368: 但因為2,3,5,...,p_k都不能整除 05/17 10:21
→ qaz86368: 所以質因數分解後會產生 05/17 10:21
→ qaz86368: 新的質數 05/17 10:21
→ qaz86368: 原本假設質數質數只有k個 05/17 10:23
→ qaz86368: 但卻可以由此找出新的質數 05/17 10:23
→ qaz86368: 所以質數不只k個 05/17 10:23
→ qaz86368: 即為無限個 05/17 10:24
推 siro0207: 原PO舉的那個反例有問題吧? 05/17 10:37
→ siro0207: 1 + 2*3*5*7*11*13 = 30031 = 59*509 05/17 10:37
→ siro0207: 從這例子來看 原原PO要的是無法被2 3 5 7 11 13任一質數 05/17 10:38
→ siro0207: 整除 但原PO卻拿出了59 509這個尚未找到的質數來整除 05/17 10:39
→ siro0207: 也就是說透過這種方式 就算能找到兩個質數相乘 那也一定 05/17 10:43
→ siro0207: 是新的質數不包含在原本假設的質數內05/17 10:44
→ siro0207: 但如果是新的質數 那前提就不是最大的質數了 05/17 10:51
推 abcdeffg: 同樓上，我認為一開始的證明是沒問題的，20年前我學05/17 10:52
→ abcdeffg: 集合論和數論時都是用反證法去說明質數無限多 05/17 10:52
推 kirimaru73: 我發現了30031和我發現了59或509都是有效的05/17 11:11
→ kirimaru73: 原本的假設就只有13 05/17 11:12
推 kirimaru73: 反證法只要打爆13的臉 他的任務就完成了 05/17 11:15
推 kirimaru73: 不過敘述上確實可能有不嚴謹的地方，例如你在考卷上寫 05/17 11:17
→ kirimaru73: 「我們創造了N+1，而它明顯無法被N以下的質數整數」 05/17 11:18
→ kirimaru73: 那可能會成為扣分的理由 除* 05/17 11:19
推 NukAnah: 嗯嗯嗯，我也是這樣覺得（根本搞不懂） 05/17 11:19
→ kirimaru73: 然而原原PO是寫無法被p_n以下的質數整除 所以也沒問題 05/17 11:19
噓 WildandTough: 看完第一點就可以end了 邏輯這麼差還跟人高談闊論= 05/17 11:23
→ WildandTough: = 反證法的假設是質數有限 所以能找到一個最大的 05/17 11:23
→ WildandTough: 質數 但是卻又能找到一個比這個最大的質數更大的質 05/17 11:23
→ WildandTough: 數 所以假設不成立 那你的例子是不是能找到比你假 05/17 11:23
→ WildandTough: 設最大的質數更大的質數？ 你與其在這邊發廢文 不 05/17 11:23
我編輯過文章了，補充我敘述的瑕疵，感謝糾正^^我舉的反例是能找到更大的質數沒錯，但不是原原po造出來的數，所以需要另外指定的步
驟才比較完整
→ WildandTough: 如拿發廢文的時間多讀點書 05/17 11:23
豪 你也加油讀書 別浪費時間回廢文了 嘻嘻※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 11:45:53
→ Heptagram: 明明就自然數比較多 05/17 11:44
※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 11:51:40→ E7lijah: 我成功將每個自然數都對應到一個獨特的質數 所以他們應 05/17 11:57
→ E7lijah: 該一樣多吧？ 05/17 11:57
→ aa851202: 簡單的數學：出一堆數字讓你昏頭；難的數學：不用數字 05/17 12:15
→ aa851202: 也能讓你寫不出來 05/17 12:15
推 Heptagram: 要證明雙射才能一樣吧 質數對應到自然數的方法是什麼 05/17 12:19
推 rkl: 我很喜歡對角線論證法 05/17 12:32
→ E7lijah: 不想搞太複雜，質數同時也是自然數，我每個質數a找與他 05/17 12:44
→ E7lijah: 相等的自然數a'，a=a'這樣就是一種質數對應到自然數 05/17 12:44
推 comp2468: 你的引理如果不是假設那一串是全部質數就不會成立 05/17 14:24
→ qazwsxedc597: 質數對應到自然數的方法就是，第1個質數2對到2，第 05/17 15:03
→ qazwsxedc597: 2個質數3對到3，第3個質數5對到4阿... 05/17 15:03
→ qazwsxedc597: 第n個質數對到某個自然數n+1 05/17 15:04
噓 hengsao: 看兩句就知道這篇不懂裝懂 到底在幹嘛== 05/17 16:26
看一句就知道你必是大師 請大師開示點醒我※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 19:05:38
→ comp2468: 對了 你引理前面那串也不成立 除非那些有限個質數是全部 05/17 20:04
→ E7lijah: 好像是這樣沒錯 我再補一下敘述05/18 00:40
※ 編輯: E7lijah (106.64.137.67 臺灣), 05/18/2023 00:42:39推 Vulpix: 呃……是要追加前提沒錯，不過沒有這麼彎。只要有算術基本 05/18 03:24
→ Vulpix: 定理在就好：比1大的整數都能寫出質因數分解。 05/18 03:25
→ Vulpix: N+1>1，所以可以用質數p們乘出來，但所有的p都不是因數。 05/18 03:26
→ comp2468: 然後你補了那個敘述後 做跟ZAX一樣的做法就行 05/18 10:32
推 CTUST: 前半還跟得上，後面就不行了 05/18 12:24