---

※ 引述《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反而是你新發現的質數
但原本的證明敘述仍有瑕疵就是了

有一個概念相似但比較嚴謹的證明：
同樣假設存在有限個質數p_1, p_2,..., p_i,..., p_k
i屬於{1, 2,..., k}
則對於任何自然數n≧2
有p_i|n (p_i能整除n)

這邊需要一個引理：
若a|b，且a|c
則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 (臺灣)
※ 作者: E7lijah 2023-05-17 00:08:44
※ 文章代碼(AID): #1aOwgK9_ (C_Chat)
※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1684253332.A.27F.html