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

[comp2468 (ilikemiku)]

※ 引述《E7lijah (InsfirE喚焰)》之銘言：
: ※ 引述《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的時候
自然數集合 |N 跟質數集合 |P
各自的最小下界inf  1 跟2 對應
將1跟2各自放進 一個集合 A_1 跟B_1
架構 N=2 的二個集合
是{a in |N but a not in A_1}
跟{n in |P but n not in B_1}
一樣各自取inf 做對應
N=M 時
N=M+1 一樣可以做
所以一樣?

其實沒有特別記得 這樣做行不行

: : 就能說自然數的個數 與 質數的個數不相同
: : 這種概念在所有的"可數集合"均成立
: : 進階一點就像"有理數的的個數"也與"正整數的個數"是一樣多的
: : 但是當命題拉到不是可數集合的時候 就不會那麼簡單了
: : 就像無理數的個數有無限多個 正整數的個數也有無限多個
: : 但無理數的個數卻是遠大於正整數的個數
: : 不過要去說明就懶了 大概也沒人在乎
: : 數學嘛 就是這麼反直覺 唉
歡迎成為 數學教徒(?)

: 其實你第一個證明有點瑕疵
: 令 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反而是你新發現的質數
: 但原本的證明敘述仍有瑕疵就是了
你看看別人的假設
要所有的質數
那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 c 都是a的時候會成立嗎?
b c有額外條件吧?
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我也不是數學系，有誤煩請糾正

--
克蘇魯?
https://imgur.com/eAa4UOI
https://www.ptt.cc/bbs/C_Chat/M.1658237873.A.160.html

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.53.201 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1684289543.A.6F4.html
推 yang560831: 他不就什麼都懂一點蹭一點= =
→ comp2468: 他說有錯請糾正 我就糾正了
※ 編輯: comp2468 (101.12.53.201 臺灣), 05/17/2023 10:31:38
推 E7lijah: 嗯a|b那邊確實該加個b不等於c的條件，或不失一般性直接
→ E7lijah: 令b>c 這樣b-c出來是正數比較好看
→ E7lijah: 在這裡
→ E7lijah: 則對於任何自然數n≧2
→ E7lijah: 有p_i|n (p_i能整除n)
→ E7lijah: 59跟509那個我也在推文討論了一下，就算此時最大的質數
→ E7lijah: 是13，59是合數，那麼30031可以拆成兩個合數乘積，不也
→ E7lijah: 有點奇怪嗎
→ cmrafsts: ???你們為啥不在整數裡面做
→ comp2468: 3樓，所以最大的質數不是13啊，你自己就是在舉反例了
推 Bugquan: 你不就是要證明質數無窮多，你已經找到比原先那個還要大
→ Bugquan: 的質數了啊
推 E7lijah: 那對你來說此時比13更大的質數是什麼？
推 KaedeHondo: 在原命題的假設下 當你做到13時就已經結束了 可以直
→ KaedeHondo: 接Q.E.D 本來就沒有59是不是質數合數的問題
→ KaedeHondo: 再往後討論下去就是連命題根本的定義都推翻 沒意義啊
→ E7lijah: 不符合此時質數定義的59？509？還是可以被拆成兩個合數
→ E7lijah: 乘積的30031？
→ E7lijah: 喔等等你們的數線只到13嗎 13後面都沒有數字？
我以為妳只是一時轉不過來 原來是真不懂= =
你自己 "假設" 最大的質數是13好嗎?
那30031 不能被2~13的質數整除的時候其實證明就結束了
你只是又找了二個數 也不能被 2~13的質數整除 矛盾的點變多而已
然後最大的質數依舊不是13阿


→ storyo11413: 當能找到不存在於假設集合的質數就足以證明質數無限
推 siro0207: 因為該原文已經假設13為最大的質數 那你拿出59 509不就
→ E7lijah: 我的想法中，比較好的證明是無限個自然數中只有有限個質
→ E7lijah: 數，自然數還是延伸至無限的，所以59 509 30031這些數依
→ E7lijah: 然存在，只是它們當下不是定義中的質數
→ siro0207: 證明了13不為最大的質數? 按照這種方法 永遠都能找到更
→ siro0207: 大的兩個質數來整除
※ 編輯: comp2468 (59.124.14.100 臺灣), 05/17/2023 11:05:10
→ E7lijah: 回siro，對啊 所以我在原文提供了59是新的質數的選項，
→ E7lijah: 但此時就不是N=30031做為新的最大質數
所以你證明了你的假設是錯的
這不就是反證法?
※ 編輯: comp2468 (59.124.14.100 臺灣), 05/17/2023 11:06:13
推 KaedeHondo: 要先回歸一個原點 反證法簡單說就是要在設定的命題下
→ KaedeHondo: 找bug 根據原命題那就是”13是最大質數” 在此命題的
→ KaedeHondo: 驗證模式下30031就該是一個質數 你”不能夠”去質因
→ KaedeHondo: 數分解更往後的質數 不然就從根本否定原命題了
→ storyo11413: 30031是不是真的質數不是重點也不是瑕疵 反例才重要
→ E7lijah: 回Kae 我不需要“特地”做質因數分解 也就是說我不需要
→ E7lijah: 將因數中的59 509指認為質數
→ E7lijah: 這看來是要再開一篇解釋的節奏XD
你要試著做啊@@
至少你要確認 2~13的質數不在質因數中就做完了
不過我建議你先了解一下條件跟證明@@
※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 11:17:49
推 Bugquan: 本來就沒跟你保證，這樣作出來的數是不是質數，只是如果
→ Bugquan: 是質數，那它肯定比原本最大的質數還大，不是質數的做質
→ Bugquan: 因數分解，你也肯定能找到比原本還大的質數
推 E7lijah: 回原po最靠近這推文的編輯
→ E7lijah: 對 我證明原來假設是錯的 是反證法沒錯
→ E7lijah: 但發生矛盾的是59，不是30031，我就只是覺得原原po的證
→ E7lijah: 法多補充一個可能性比較完整
你會說是59 就是你沒看懂他在證明什麼
→ storyo11413: 1 + p_1*p_2*...*p_k只是方便你快速了解這數無法整除
→ siro0207: 重點在於你30031不管是不是質數 他都不能被你原先假設的
→ siro0207: "最大"質數13整除
→ siro0207: 不對 是不能被你假設的2~13質數整除
→ E7lijah: 欸好吧看來大家還是不太懂我想講什麼 晚上回來再一篇XD
※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 11:19:58
→ E7lijah: 我先丟一句話是說，質數最初始的定義是不能被自己跟1以
→ E7lijah: 外的數整除，那今天30031不能被2,...,13整除，但能被59
→ E7lijah: 整除(此時59是作為「非質數」存在)，那麼30031不符合質
→ E7lijah: 數定義，這個證明「尚未」找到比13更大的質數
→ E7lijah: 但我們都知道此時只要將新的質數候選人改成59，整個證明
→ E7lijah: 就完成了
呃 所以你不知道所有合數可以寫成質數的乘積這件事嗎?
12=2^2*3 類似這樣
這是她證明的核心
所有比最大質數大的整數a
都應該可以寫成

a=p_1^n_1*p_2^n_2...p_m^n_m
其中 n_i, i in [1,m] 是大於等於0的整數


推 KaedeHondo: 當30031無法被假設下”所有的質數”給整除時 就已經
→ KaedeHondo: 該命題下是個質數了 去討論59就徹底失去反證法的意義
→ KaedeHondo:  那就直接說17、19 都是質數不是更快？
推 aegius1r: https://en.wikipedia.org/wiki/Euclid%27s_theorem
推 Bugquan: 不是，你有沒真的找到59都沒差，因為這樣建構出來的，保
→ Bugquan: 證你肯定會找到比原本還大的質數，至於那個數是啥不太重
→ Bugquan: 要
※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 11:31:58
→ E7lijah: 欸所以我想說的是 30031這個數 如果使用「可否被其他質
→ E7lijah: 數整除」做質數定義的話，那他是（新的）質數，但如果使
→ E7lijah: 用「可否被1跟自己以外的數整除」做質數定義的話，那它
→ E7lijah: 不是新的質數，要另外展開
→ E7lijah: 這個證法會被挑小毛病的地方就在質數的定義使用上，當然
→ E7lijah: 可以死守我上句的第一個定義，只是像我這種怪人就會拿第
→ E7lijah: 二個更基本的定義來檢查
→ storyo11413: 探討1 + p_1*p_2*...*p_k是否為質數並非該證明的主題
→ E7lijah: 所以使用這個證法比較無懈可擊的做法是像ae大貼的wiki條
→ E7lijah: 目 分兩種情況討論 一定沒有問題
→ E7lijah: 探討1 + p_1*p_2*...*p_k是否為質數 就是 這個證明的主
→ E7lijah: 題，因為這個證明就是用我發現了1 + p_1*p_2*...*p_k這
→ E7lijah: 個更大的「質數」做反證法矛盾點的依據
→ arcanite: 所以說合數是什麼 = =
→ E7lijah: 不是質數的整數啊
推 Bugquan: 不是，是正整數，而且1既不是質數也不是合數
推 aegius1r: 反正本來就得去補上 1 + p_1*p_2*...*p_k是合數時
→ aegius1r: 造成矛盾的情況
→ E7lijah: 應該說因數有1跟自己以外的數
→ E7lijah: 的自然數
→ E7lijah: ae大你懂我QQ
推 E7lijah: 總之我想講的差不多就是wiki歐幾里得定理條目寫的
那就不是反證法阿
他的證明跟歐幾里得的不一樣阿@@
你們有在看ZAX的假設嗎?

他是已經找了一個最大質數p_n當上界
歐幾里得的是 任意有限個數的質數集合

所以她的證明中用到
如果
q不是質數，
那麼存在一個質數因子p
p整除q

但所有p_1~p_n 都不能整除q 所以矛盾
p_1~p_n 在這裡的假設是 "所有"質數

歐幾里得的是任意有限個數的質數集合
前提有差啊

所以歐幾里得的假設會有
乘起來是不是質數的問題
因為他這裡不是指所有的質數
但ZAX的假設p_n是最大的
而且乘起來+1 一定大於p_n
所以只要p_1~p_n 都不能整除q就結束了

你們講的完全是不同東西好嗎@@?


※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 12:02:35
推 XFarter: @E7lijah 看起來應該是正解，歐幾裡德定理確實沒有要求質
→ XFarter: 數集 P 必定需是否有限，細節的證明還是去看 Wiki 歐幾里
→ XFarter: 德定理
從他說出是反證法的時候就不是歐幾里得定理了@@
wiki上有說 不要搞混了
並不是證法相似就是一樣
※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 12:08:08
推 zax8419: 我開始懷疑他在反串了....
→ zax8419: 然後我是數學前叛徒 也就是數學叛徒的叛徒Q_Q
我應該算被踢出來吧QQ
我一開始以為他只是有個點沒想通
我開始懷疑他根本不知道自己在講什麼
反串的話是高級反串
我被吊到了QQ
推 E7lijah: 所以她的證明中用到
→ E7lijah: 如果
→ E7lijah: q不是質數，
→ E7lijah: 那麼存在一個質數因子p
→ E7lijah: p整除q
→ E7lijah: 沒有喔 zax大的證明沒有上面這些話
→ E7lijah: 這些話就是我覺得需要補充加上去的部分
對 他是沒有講
但跟你前面講的那些什麼合數乘積
是完全不同事情
推 mouscat: 等等 既然1+p_1*p_2*…p_n這個數不為質數的可能只有「存
→ mouscat: 在比p_n更大的質數」那無論這數是否為質數 元命題都能被
→ mouscat: 推翻吧？我是不太懂啦
在原命題中 1+p_1*p_2*…p_n這個數不為質數

但產生矛盾
所以有最大質數不成立
所以是無上限的
可以一直創造出來
※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 12:18:37
→ E7lijah: 我講合數乘積是因為那時候59「還不是」質數啊XD 我們還沒
→ E7lijah: 發現他是新的質數不是嗎
→ zax8419: 我只能說 你糾結的點完全對命題沒有任何影響 59完全不是
→ zax8419: 原命題討論的點 你的"反例"直接是建立在質數有無窮下 跟
→ zax8419: 原命題的質數最大值是13完全是不同的事
→ zax8419: 根據你的論點 我發現17,19,23,29都已經是質數 那我還假設
→ zax8419: 最大質數幹嘛?
→ zax8419: 在"有最大質數為13"的前提下 30031根據這個命題就會是質
→ zax8419: 數 哪管59的事?
他一直糾結在 那個數可以因式分解 很奇怪@@
矛盾的點就在
q不是質數，那麼存在一個質數因子p
p整除q
但你在這個假設會找到一個q找不到這個p
所以矛盾
根據反證法就是 無限大

→ XFarter: 欸對欸 歐幾里德沒有使用反證法，它對於 1+all of p_i 的
→ XFarter:  T 和 F 所造成的結果都有後面的討論
→ XFarter: 抱歉 我今天 JPTT 一直被卡登入 文章看一半==
Jptt今天真的一直斷 很奇怪1
→ E7lijah: 那是數字小的時候你可以手動檢查啊 數字大的時候你用電
→ E7lijah: 腦算都很難算
所以她架構一個數字 來證明不是嗎?
※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 12:27:38
→ zax8419: 不如你說說怎麼用唯一的質因數表示法來表示30031
→ pot1234: 有限集合不處理最小上界不會被刁吧
→ XFarter: @E7 我覺得中文的歐幾里德 Wiki 寫的比英文的好懂不少，
→ XFarter: 也許可以看一下
→ zax8419: 要記得前提是質數只到13喔
推 curance: 學術論壇捏
推 mouscat: 去考慮p_n+k的存在對反證命題的意義…我是說假如它存在
→ mouscat: 那元命題就是錯的不用反證了 如果他不存在 本來的證明方
→ mouscat: 法就沒問題不是？
應該說 在他的假設下 就是不存在 所以有那個證法證明矛盾
→ E7lijah: 那我不用唯一的質因數分解表示30031，我就單純因數分解，
→ E7lijah: 不限定因數須為質數
他的矛盾點就在 找不到那個唯一的質因數分解
所以我說你沒看懂
※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 12:32:47
→ E7lijah: 欸我先澄清 我沒有反對反證法本身 我是覺得反證法的矛盾
→ E7lijah: 發生點需要多補充一句另一個可能
→ E7lijah: ptt今天一直斷+1 我用Pitt也是
→ zax8419: 不用唯一的質因數分解表示法...你要不要聽聽你在說什麼?
→ E7lijah: 蛤 就不強求質因數分解啊 單純討論因數分解看他所有因數
→ E7lijah: 不行嗎
→ E7lijah: 所有因數中有不是自己跟1的就是合數啊 不是這樣嗎
→ zax8419: 所有數都能表示成唯一的質因數表示法 我以為這是國中的常
→ zax8419: 識
→ zax8419: 如果真的做不到 那我想也無法討論下去了。
※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 12:34:32
推 E7lijah: 我沒有要討論做不做得到 我只是沒有要去做而已= =
→ E7lijah: 我先用基本的因數分解不行嗎
→ storyo11413: E7最怪就是命題限定的東西不管 直接跳整體的因式分解
→ zax8419: 那你要不要先做了 再來說他是合數呢?
→ E7lijah: 不是 我知道你們想幹嘛 你們想要用30031的質因數沒有2~13
→ E7lijah: ，所以30031是新的質數
推 arrenwu: 正整數那個在國中比較像神諭吧 國中有教算術基本定理嗎？
→ storyo11413: 集合內的元素搞不定就是反證法成功了
→ E7lijah: 這是質數的性質沒錯
推 aegius1r: 要證這麼基本的東西 就不要再把"常識"搬出來了 用"定理"
其實也沒錯 應該把要用的定理引出來
或者直接證明也行
用強數學歸納法證明
2~N 都有質因數分解
所以假設N+1 = a*b
若存在 a b都是大於二的自然數
則 N+1 有質因數分解
a 的質因數分解*b的質因數分解
若a or b 只能是1
則N+1是質數

唯一的質因數分解就把二個質因數分解相除=1就可以證明
→ E7lijah: 啊我想到了 30031用質因數分解定義來看是質數，用列出所
→ E7lijah: 有因數分解來看是合數，發生矛盾，證畢 皆大歡喜
→ zax8419: 摁 你開心就好 記得如果有要教人 不要教別人這樣寫 我改
→ zax8419: 會扣分
→ E7lijah: 好的教授
※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 12:54:15
推 XFarter: 8要氣ㄅㄨㄅㄨ 證明不完備其實很常見，既然真的想討論雙
→ XFarter: 方就不要用這麼多情緒化用詞。
→ XFarter: 不過我真的覺得 E7 可以發文解釋一下你的方法覺得對的理
→ XFarter: 由，最好比較一下歐幾里德定理跟你的差別，不然很難服眾
我剛剛認真看了一下後續 發現他的前提就是錯的

: 有一個概念相似但比較嚴謹的證明：
: 同樣假設存在有限個質數p_1, p_2,..., p_i,..., p_k
: i屬於{1, 2,..., k}
: 則對於任何自然數n≧2
: 有p_i|n (p_i能整除n)
抱歉 沒這引理
除非你假設 那些是所有的質數
他要講歐幾里德定理的話就不能用這個引理證明
不然他自己的反例就是這個引理的反例阿

※ 編輯: comp2468 (61.220.74.62 臺灣), 05/17/2023 14:06:56
推 XFarter: 上面的假設其實沒有 Quantifier 讀的也蠻痛苦的，但我決
→ XFarter: 定還是維持吃瓜就好了==
→ XFarter: 我指 E7 的原文
推 Hosimati: zax的證明不就矛盾的部分沒有寫仔細而已，怎麼這麼糾結
→ zax8419: 我是知道我寫的沒有很完整 不過本來就打算寫科普簡略向
→ zax8419: 只不過不完整的部分絕對不是合數部分就是了
就是沒講質因數分解存在且唯一這個而已@@
※ 編輯: comp2468 (203.204.43.142 臺灣), 05/17/2023 22:44:37