※ 引述《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我也不是數學系，有誤煩請糾正

他不就什麼都懂一點蹭一點= =

他說有錯請糾正 我就糾正了

嗯a|b那邊確實該加個b不等於c的條件，或不失一般性直接令b>c 這樣b-c出來是正數比較好看在這裡則對於任何自然數n≧2有p_i|n (p_i能整除n)59跟509那個我也在推文討論了一下，就算此時最大的質數是13，59是合數，那麼30031可以拆成兩個合數乘積，不也有點奇怪嗎

???你們為啥不在整數裡面做

3樓，所以最大的質數不是13啊，你自己就是在舉反例了

你不就是要證明質數無窮多，你已經找到比原先那個還要大的質數了啊

那對你來說此時比13更大的質數是什麼？

在原命題的假設下 當你做到13時就已經結束了 可以直接Q.E.D 本來就沒有59是不是質數合數的問題再往後討論下去就是連命題根本的定義都推翻 沒意義啊

不符合此時質數定義的59？509？還是可以被拆成兩個合數乘積的30031？喔等等你們的數線只到13嗎 13後面都沒有數字？

當能找到不存在於假設集合的質數就足以證明質數無限

因為該原文已經假設13為最大的質數 那你拿出59 509不就

我的想法中，比較好的證明是無限個自然數中只有有限個質數，自然數還是延伸至無限的，所以59 509 30031這些數依然存在，只是它們當下不是定義中的質數

證明了13不為最大的質數? 按照這種方法 永遠都能找到更大的兩個質數來整除

回siro，對啊 所以我在原文提供了59是新的質數的選項，但此時就不是N=30031做為新的最大質數

要先回歸一個原點 反證法簡單說就是要在設定的命題下找bug 根據原命題那就是”13是最大質數” 在此命題的驗證模式下30031就該是一個質數 你”不能夠”去質因數分解更往後的質數 不然就從根本否定原命題了

30031是不是真的質數不是重點也不是瑕疵 反例才重要

回Kae 我不需要“特地”做質因數分解 也就是說我不需要將因數中的59 509指認為質數這看來是要再開一篇解釋的節奏XD

本來就沒跟你保證，這樣作出來的數是不是質數，只是如果是質數，那它肯定比原本最大的質數還大，不是質數的做質因數分解，你也肯定能找到比原本還大的質數

回原po最靠近這推文的編輯對 我證明原來假設是錯的 是反證法沒錯但發生矛盾的是59，不是30031，我就只是覺得原原po的證法多補充一個可能性比較完整

1 + p_1*p_2*...*p_k只是方便你快速了解這數無法整除

重點在於你30031不管是不是質數 他都不能被你原先假設的"最大"質數13整除不對 是不能被你假設的2~13質數整除

欸好吧看來大家還是不太懂我想講什麼 晚上回來再一篇XD我先丟一句話是說，質數最初始的定義是不能被自己跟1以外的數整除，那今天30031不能被2,...,13整除，但能被59整除(此時59是作為「非質數」存在)，那麼30031不符合質數定義，這個證明「尚未」找到比13更大的質數但我們都知道此時只要將新的質數候選人改成59，整個證明就完成了

當30031無法被假設下”所有的質數”給整除時 就已經該命題下是個質數了 去討論59就徹底失去反證法的意義那就直接說17、19 都是質數不是更快？

不是，你有沒真的找到59都沒差，因為這樣建構出來的，保證你肯定會找到比原本還大的質數，至於那個數是啥不太重要

欸所以我想說的是 30031這個數 如果使用「可否被其他質數整除」做質數定義的話，那他是（新的）質數，但如果使用「可否被1跟自己以外的數整除」做質數定義的話，那它不是新的質數，要另外展開這個證法會被挑小毛病的地方就在質數的定義使用上，當然可以死守我上句的第一個定義，只是像我這種怪人就會拿第二個更基本的定義來檢查

探討1 + p_1*p_2*...*p_k是否為質數並非該證明的主題

所以使用這個證法比較無懈可擊的做法是像ae大貼的wiki條目 分兩種情況討論 一定沒有問題探討1 + p_1*p_2*...*p_k是否為質數 就是 這個證明的主題，因為這個證明就是用我發現了1 + p_1*p_2*...*p_k這個更大的「質數」做反證法矛盾點的依據

所以說合數是什麼 = =

不是質數的整數啊

不是，是正整數，而且1既不是質數也不是合數

反正本來就得去補上 1 + p_1*p_2*...*p_k是合數時造成矛盾的情況

應該說因數有1跟自己以外的數的自然數ae大你懂我QQ總之我想講的差不多就是wiki歐幾里得定理條目寫的

@E7lijah 看起來應該是正解，歐幾裡德定理確實沒有要求質數集 P 必定需是否有限，細節的證明還是去看 Wiki 歐幾里德定理

我開始懷疑他在反串了....然後我是數學前叛徒 也就是數學叛徒的叛徒Q_Q

所以她的證明中用到如果q不是質數，那麼存在一個質數因子pp整除q沒有喔 zax大的證明沒有上面這些話這些話就是我覺得需要補充加上去的部分

等等 既然1+p_1*p_2*…p_n這個數不為質數的可能只有「存在比p_n更大的質數」那無論這數是否為質數 元命題都能被推翻吧？我是不太懂啦

我講合數乘積是因為那時候59「還不是」質數啊XD 我們還沒發現他是新的質數不是嗎

我只能說 你糾結的點完全對命題沒有任何影響 59完全不是原命題討論的點 你的"反例"直接是建立在質數有無窮下 跟原命題的質數最大值是13完全是不同的事根據你的論點 我發現17,19,23,29都已經是質數 那我還假設最大質數幹嘛?在"有最大質數為13"的前提下 30031根據這個命題就會是質數 哪管59的事?

欸對欸 歐幾里德沒有使用反證法，它對於 1+all of p_i 的T 和 F 所造成的結果都有後面的討論抱歉 我今天 JPTT 一直被卡登入 文章看一半==

那是數字小的時候你可以手動檢查啊 數字大的時候你用電腦算都很難算

不如你說說怎麼用唯一的質因數表示法來表示30031

有限集合不處理最小上界不會被刁吧

@E7 我覺得中文的歐幾里德 Wiki 寫的比英文的好懂不少，也許可以看一下

學術論壇捏

去考慮p_n+k的存在對反證命題的意義…我是說假如它存在那元命題就是錯的不用反證了 如果他不存在 本來的證明方法就沒問題不是？

那我不用唯一的質因數分解表示30031，我就單純因數分解，不限定因數須為質數欸我先澄清 我沒有反對反證法本身 我是覺得反證法的矛盾發生點需要多補充一句另一個可能ptt今天一直斷+1 我用Pitt也是

不用唯一的質因數分解表示法...你要不要聽聽你在說什麼?

蛤 就不強求質因數分解啊 單純討論因數分解看他所有因數不行嗎所有因數中有不是自己跟1的就是合數啊 不是這樣嗎

所有數都能表示成唯一的質因數表示法 我以為這是國中的常識如果真的做不到 那我想也無法討論下去了。

我沒有要討論做不做得到 我只是沒有要去做而已= =我先用基本的因數分解不行嗎

E7最怪就是命題限定的東西不管 直接跳整體的因式分解

那你要不要先做了 再來說他是合數呢?

不是 我知道你們想幹嘛 你們想要用30031的質因數沒有2~13，所以30031是新的質數

正整數那個在國中比較像神諭吧 國中有教算術基本定理嗎？

集合內的元素搞不定就是反證法成功了

這是質數的性質沒錯

要證這麼基本的東西 就不要再把"常識"搬出來了 用"定理"

啊我想到了 30031用質因數分解定義來看是質數，用列出所有因數分解來看是合數，發生矛盾，證畢 皆大歡喜

摁 你開心就好 記得如果有要教人 不要教別人這樣寫 我改會扣分

好的教授

8要氣ㄅㄨㄅㄨ 證明不完備其實很常見，既然真的想討論雙方就不要用這麼多情緒化用詞。不過我真的覺得 E7 可以發文解釋一下你的方法覺得對的理由，最好比較一下歐幾里德定理跟你的差別，不然很難服眾