Re: [問題] 無限多的自然數跟質數誰比較多？

※ 引述《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