看板 C_Chat
作者
標題 Re: [問題] 無限多的自然數跟質數誰比較多？
時間 Wed May 17 00:08:44 2023
作者
標題 Re: [問題] 無限多的自然數跟質數誰比較多？
時間 Wed May 17 00:08:44 2023
※ 引述《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
※ 同主題文章:
05-16 15:33
05-16 19:11
05-16 19:41
Re: [問題] 無限多的自然數跟質數誰比較多？
05-17 00:08
05-17 10:12
05-17 12:08
05-17 14:07
05-18 01:30
05-18 03:10
05-18 04:17
05-18 12:14
05-18 12:52
05-18 23:03
→ : 嗯嗯 我的答案跟小當家一樣1F 05/17 00:09
推 : 這個就數學系在分析導論的前幾堂課吧2F 05/17 00:10
→ : 我先 打那麼多誰看得完3F 05/17 00:10
→ : 比較有趣的是怎麼證明實數不可數，但又要用反證的4F 05/17 00:10
→ : 實數不可數的反證法不就是用經典的康托爾對角線證法嗎5F 05/17 00:13
推 : 推這篇6F 05/17 00:16
推 : 不明覺厲7F 05/17 00:16
→ : 這篇就是典型的會把圈外人嚇到對數學更沒興趣的文章…8F 05/17 00:16
推 : 對角線那個想了好久才搞清楚他在幹嘛9F 05/17 00:17
我當初想通之後覺得這招好屌推 : 原po什麼系10F 05/17 00:19
也是理學院推 : 這裡是什麼版？11F 05/17 00:19
推 : 這裡本應是廢文板才對12F 05/17 00:21
讓人看不懂的文算不算一種廢文→ : 現在我搞不懂了13F 05/17 00:21
推 : 要考試的時候搞懂過，現在看都忘記了14F 05/17 00:22
※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 00:25:04推 : 任兩個費馬數互質有那麼trivial嗎？15F 05/17 00:25
→ : 回s大，沒有XD
但再寫下去我怕真的太多16F 05/17 00:26
但再寫下去我怕真的太多16F 05/17 00:26
→ : 沒 你那個"反例"已經跟原命題衝突了 原命題已經假設最大質數了 在你的例子裡 最大的質數是13 那59跟509就不是一個質數 要驗證也是拿2,3,5,7,11,13去驗證才對18F 05/17 00:27
推 : 差點忘了這裡是個學術書論壇21F 05/17 00:29
推 : 謝啦 你清楚地說明我上篇文章推文的疑惑 證明式不嚴謹22F 05/17 00:30
→ : 雖然你知我知天知地知59,509也是質數 但那跟原本假設的"質數的最大值"相違背這樣23F 05/17 00:30
那我可以說，好 那麼59跟509不是「質數」，而是合數，但30031可以表達成兩個「合數」的乘積，還是哪裡怪怪的
→ : zax是用比較通俗的方式說明 這篇是寫成邏輯數學式這樣25F 05/17 00:32
※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 00:34:42推 : 做個每日還這麼哈扣，不曉得以後會不會來0.999_=126F 05/17 00:35
→ : 應該是可以直接說 "到這一步可以證明最大的質數不存在"這樣就好吧
幹 樓上0.999_=1 要開新戰場了嗎XD27F 05/17 00:36
幹 樓上0.999_=1 要開新戰場了嗎XD27F 05/17 00:36
→ : 要請出戴德金分割了嗎XD30F 05/17 00:38
推 : 這裡是什麼版阿這麼艱深31F 05/17 00:38
→ : 接著肯定就是 1+2+3+....=-1/12 了吧32F 05/17 00:38
推 : 不是吧，這個真的不艱深啦，連我文組女友都聽得懂了33F 05/17 00:39
→ : 會來西恰的怎麼可能有女友 我書讀得少 別騙我34F 05/17 00:42
→ : 大哥怎麼這麼電，果然做電化學的個個都是天才35F 05/17 00:43
→ : 總而言之 我那個寫法本來就是反證法下的產物 出現明確問題or反例=>矛盾 大概是這樣吧 不想再回一篇惹36F 05/17 00:43
推 : 第一個證明沒有問題
你舉出 30031 這個具體例子並不會造成該證明變得不完整38F 05/17 00:47
你舉出 30031 這個具體例子並不會造成該證明變得不完整38F 05/17 00:47
推 : 假設質數的數量為有限，那我們只要
作出一個不在上列有限個質數的質數，就可以得到矛盾
從而得知質數有無限個
這應該是zax大大的證明思路40F 05/17 00:49
作出一個不在上列有限個質數的質數，就可以得到矛盾
從而得知質數有無限個
這應該是zax大大的證明思路40F 05/17 00:49
推 : 喔 不對 當我沒說 XD 我仔細看一下原文的字句確實是不太嚴謹的 比較好的方式應該是再分兩種情況：N+1 是質數和不是質數 然後再分別得到矛盾44F 05/17 00:55
→ : 同r大 不是說那個證明不行 而是至少補加點敘述才比較完整47F 05/17 00:57
推 : 想起當年待數學系的痛苦回憶了 謝啦49F 05/17 00:58
→ : 不過我也想過針對這個瑕疵的敘述需不需要這麼計較 畢竟本來就是反證法推出的錯誤性質了50F 05/17 00:59
→ : 用費馬數證是沒錯啦，但是要先證費馬數互質52F 05/17 00:59
那就是另一篇了XD推 : 當然不是1阿，你們聽過p-adic number嗎?(X53F 05/17 00:59
大神請說 小弟洗耳恭聽→ : 樓上是神54F 05/17 01:00
※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 01:02:25→ : 其實也不會太難就證F_n=F_1*F_2*...*F_(n-1)+255F 05/17 01:11
→ : 我知道證法 但文章已經太長 這裡寫不下(X56F 05/17 01:12
推 : 那一天，大家想起過去的 ptt 是怎樣的狀況57F 05/17 01:33
推 : 請數學小圈圈放過西恰58F 05/17 01:46
推 : 我是不是走錯板了0.059F 05/17 01:46
推 : 其實就是他寫的不夠仔細，p_n是最大質數且N+1>p_n，故N+1不是質數，又無法被的有限的n個質數的任一整除，矛盾60F 05/17 01:54
→ : p-adic number就我的理解就是p進位表達（p為質數）62F 05/17 01:55
推 : 看你這篇文我恍神了三次63F 05/17 01:56
→ : 同時加上一個特別的距離定義，讓小數點左右兩邊
都可以是無窮的且收斂
應該說小數點左邊才對64F 05/17 01:56
都可以是無窮的且收斂
應該說小數點左邊才對64F 05/17 01:56
推 : 結果整片討論區沒有人提到阿列夫數或 Beth 也是蠻可惜的67F 05/17 02:33
推 : 去Google了對角線證法，很66668F 05/17 03:07
推 : 0.999.. = 1, 跟 1/9 * 9 = 1 其實是一樣概念 只是很多人對分數跟有理數理解還不夠而已69F 05/17 03:27
推 : 樓上是認真還是在唬爛？ 0.999999...要等於 1 也是需要被嚴格定義的，光序理論就說不通71F 05/17 03:36
推 : 不明覺厲，但覺得很厲害。73F 05/17 03:46
推 : 好文 推74F 05/17 03:59
推 : 為啥我看這篇文會怪怪的阿75F 05/17 04:11
推 : 抱歉進到數學版了……什麼這是西洽？76F 05/17 06:45
推 : 唉呦豆頁好痛77F 05/17 08:00
推 : 其實反證也可以通俗地解決，如果0.99…循環不等於1，那兩者之間必然能找到無限多個非零實數，但你用你已知的國高中數學邏輯去算就會發現你連一個非零實數都找不到，只會條條大路通向兩者是同一個數78F 05/17 08:05
→ : 感覺不出哪裡有瑕疵，59，509比p_n大這件事就違反假設啊？82F 05/17 08:14
推 : 推個魔法84F 05/17 08:31
推 : 嗯嗯我也是這麼想的85F 05/17 08:31
推 : 老師我選c86F 05/17 08:35
推 : 不管59和509是啥，他們都把原命題打爆了，所以反證法還是成立87F 05/17 08:47
推 : 你不是數學系...你也打太多XD89F 05/17 08:51
推 : 恩恩對 我也是這麼想的90F 05/17 09:00
--
作者 E7lijah 的最新發文:
![]()
續上篇：#1dJ9pSlG(PC_Shopping) 養成好習慣要附來源： *本片涉及諸多強烈嚴厲的遣詞與法律用詞，所以某些翻譯會附上原文供參考 這集篇幅會著重所有力氣在NZXT租賃/訂閱的契約條款 …220F 126推![]()
來源：GN YT 2024轉眼間就快過去了 又到了GN評選今年最佳〇〇 XX的時候 這篇是年度最佳〇〇CPU 因為GN是美國媒體 所以價格、性價比方面會以北美零售時價來考量 整體最佳：AMD R7 …86F 45推 2噓- 來源：MSI官網新聞稿 nt-145012 縮網址： 原文： Recently, we received a user report indicating damage to an AMD Ryze …160F 73推 3噓
![]()
如題 LCK#1連續兩年都倒在八強 如果像去年JDG打T1一樣 兩強巔峰對決 輸的精采就算了 但兩年#1都是自己醜了送下去 請問今年韓華倒了 最大的鍋到底是誰= =? 1. 整把0作用的多爛 2. …82F 53推 3噓![]()
來源： 耶穌的開頭： 這顆CPU最讚的點是其優異的能效 第二讚的點是 它不是intel做的XDD (此文中的能效=能耗比，兩詞會交替使用) 先說結論： 能耗比非常優秀 但AMD可能太注重能耗比 因而 …215F 100推
點此顯示更多發文記錄