PTT推薦

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

看板C_Chat標題Re: [問題] 無限多的自然數跟質數誰比較多?作者
E7lijah
(InsfirE喚焰)
時間推噓51 推:53 噓:2 →:99

※ 引述《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 留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.217.58 (臺灣)
PTT 網址

yang56083105/17 00:09嗯嗯 我的答案跟小當家一樣

nahsnib05/17 00:10這個就數學系在分析導論的前幾堂課吧

E7lijah05/17 00:10我先 打那麼多誰看得完

nahsnib05/17 00:10比較有趣的是怎麼證明實數不可數,但又要用反證的

E7lijah05/17 00:13實數不可數的反證法不就是用經典的康托爾對角線證法嗎

ashrum05/17 00:16推這篇

kaj198305/17 00:16不明覺厲

ainamk05/17 00:16這篇就是典型的會把圈外人嚇到對數學更沒興趣的文章…

tkc705/17 00:17對角線那個想了好久才搞清楚他在幹嘛

我當初想通之後覺得這招好屌

thejackys05/17 00:19原po什麼系

也是理學院

cerberus452305/17 00:19這裡是什麼版?

kaj198305/17 00:21這裡本應是廢文板才對

讓人看不懂的文算不算一種廢文

kaj198305/17 00:21現在我搞不懂了

ggchioinder05/17 00:22要考試的時候搞懂過,現在看都忘記了

※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 00:25:04

sadmonkey05/17 00:25任兩個費馬數互質有那麼trivial嗎?

E7lijah05/17 00:26回s大,沒有XD

E7lijah05/17 00:26但再寫下去我怕真的太多

zax841905/17 00:27沒 你那個"反例"已經跟原命題衝突了 原命題已經假設最大

zax841905/17 00:27質數了 在你的例子裡 最大的質數是13 那59跟509就不是一

zax841905/17 00:27個質數 要驗證也是拿2,3,5,7,11,13去驗證才對

yumenemu61005/17 00:29差點忘了這裡是個學術書論壇

NicoNeco05/17 00:30謝啦 你清楚地說明我上篇文章推文的疑惑 證明式不嚴謹

zax841905/17 00:30雖然你知我知天知地知59,509也是質數 但那跟原本假設的"

zax841905/17 00:30質數的最大值"相違背這樣

那我可以說,好 那麼59跟509不是「質數」,而是合數,但30031可以表達成兩個「合數 」的乘積,還是哪裡怪怪的

NicoNeco05/17 00:32zax是用比較通俗的方式說明 這篇是寫成邏輯數學式這樣

※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 00:34:42

hutao05/17 00:35做個每日還這麼哈扣,不曉得以後會不會來0.999_=1

zax841905/17 00:36應該是可以直接說 "到這一步可以證明最大的質數不存在"這

zax841905/17 00:36樣就好吧

zax841905/17 00:36幹 樓上0.999_=1 要開新戰場了嗎XD

E7lijah05/17 00:38要請出戴德金分割了嗎XD

jimmyVanClef05/17 00:38這裡是什麼版阿這麼艱深

zax841905/17 00:38接著肯定就是 1+2+3+....=-1/12 了吧

nahsnib05/17 00:39不是吧,這個真的不艱深啦,連我文組女友都聽得懂了

E7lijah05/17 00:42會來西恰的怎麼可能有女友 我書讀得少 別騙我

mayolane05/17 00:43大哥怎麼這麼電,果然做電化學的個個都是天才

zax841905/17 00:43總而言之 我那個寫法本來就是反證法下的產物 出現明確問

zax841905/17 00:43題or反例=>矛盾 大概是這樣吧 不想再回一篇惹

raincole05/17 00:47第一個證明沒有問題

raincole05/17 00:48你舉出 30031 這個具體例子並不會造成該證明變得不完整

WayThuz05/17 00:49假設質數的數量為有限,那我們只要

WayThuz05/17 00:49作出一個不在上列有限個質數的質數,就可以得到矛盾

WayThuz05/17 00:49從而得知質數有無限個

WayThuz05/17 00:51這應該是zax大大的證明思路

raincole05/17 00:55喔 不對 當我沒說 XD 我仔細看一下原文的字句確實是不太

raincole05/17 00:56嚴謹的 比較好的方式應該是再分兩種情況:N+1 是質數和

raincole05/17 00:56不是質數 然後再分別得到矛盾

E7lijah05/17 00:57同r大 不是說那個證明不行 而是至少補加點敘述才比較完

E7lijah05/17 00:57

greg9032605/17 00:58想起當年待數學系的痛苦回憶了 謝啦

E7lijah05/17 00:59不過我也想過針對這個瑕疵的敘述需不需要這麼計較 畢竟

E7lijah05/17 00:59本來就是反證法推出的錯誤性質了

chordate05/17 00:59用費馬數證是沒錯啦,但是要先證費馬數互質

那就是另一篇了XD

cmrafsts05/17 00:59當然不是1阿,你們聽過p-adic number嗎?(X

大神請說 小弟洗耳恭聽

zax841905/17 01:00樓上是神

※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 01:02:25

chordate05/17 01:11其實也不會太難就證F_n=F_1*F_2*...*F_(n-1)+2

E7lijah05/17 01:12我知道證法 但文章已經太長 這裡寫不下(X

drm34305/17 01:33那一天,大家想起過去的 ptt 是怎樣的狀況

derlin1234505/17 01:46請數學小圈圈放過西恰

thelittleone05/17 01:46我是不是走錯板了0.0

Hosimati05/17 01:54其實就是他寫的不夠仔細,p_n是最大質數且N+1>p_n,故N

Hosimati05/17 01:54+1不是質數,又無法被的有限的n個質數的任一整除,矛盾

chordate05/17 01:55p-adic number就我的理解就是p進位表達(p為質數)

ym95130505/17 01:56看你這篇文我恍神了三次

chordate05/17 01:56同時加上一個特別的距離定義,讓小數點左右兩邊

chordate05/17 01:56都可以是無窮的且收斂

chordate05/17 02:22應該說小數點左邊才對

XFarter05/17 02:33結果整片討論區沒有人提到阿列夫數或 Beth 也是蠻可惜的

weebeer62605/17 03:07去Google了對角線證法,很666

zball05/17 03:270.999.. = 1, 跟 1/9 * 9 = 1 其實是一樣概念 只是很多人

zball05/17 03:29對分數跟有理數理解還不夠而已

XFarter05/17 03:36樓上是認真還是在唬爛? 0.999999...要等於 1 也是需要被

XFarter05/17 03:36嚴格定義的,光序理論就說不通

z93221005/17 03:46不明覺厲,但覺得很厲害。

physicsbest05/17 03:59好文 推

qoo35015405/17 04:11為啥我看這篇文會怪怪的阿

et2263964305/17 06:45抱歉進到數學版了……什麼這是西洽?

fth86205/17 08:00唉呦豆頁好痛

msbdhdfceb05/17 08:05其實反證也可以通俗地解決,如果0.99…循環不等於1,

msbdhdfceb05/17 08:05那兩者之間必然能找到無限多個非零實數,但你用你已

msbdhdfceb05/17 08:05知的國高中數學邏輯去算就會發現你連一個非零實數都

msbdhdfceb05/17 08:05找不到,只會條條大路通向兩者是同一個數

pot123405/17 08:14感覺不出哪裡有瑕疵,59,509比p_n大這件事就違反假設啊

pot123405/17 08:14

zseineo05/17 08:31推個魔法

inmysis05/17 08:31嗯嗯我也是這麼想的

yuanvio05/17 08:35老師我選c

kirimaru7305/17 08:47不管59和509是啥,他們都把原命題打爆了,所以反證法

kirimaru7305/17 08:47還是成立

lolicon05/17 08:51你不是數學系...你也打太多XD

Daha1AG05/17 09:00恩恩對 我也是這麼想的

a148754605/17 09:33推,打這麼多我還是看完了

Aaron100205/17 09:35跟我想的一樣

qaz8636805/17 10:17簡單說 質數若有限個

qaz8636805/17 10:17分別是2,3,5...,p_k 這k個質數

qaz8636805/17 10:17那我們想像2*3*5*...*p_k+1

qaz8636805/17 10:17所產生的數字

qaz8636805/17 10:192*3*5*...*p_k+1

qaz8636805/17 10:19若此數字本身就是質數

qaz8636805/17 10:19因為不能被2,3,5...,p_k

qaz8636805/17 10:19這k個質數整除

qaz8636805/17 10:19所以是新的質數

qaz8636805/17 10:21若數字不是質數 即是合數

qaz8636805/17 10:21則可進行質因數分解

qaz8636805/17 10:21但因為2,3,5,...,p_k都不能整除

qaz8636805/17 10:21所以質因數分解後會產生

qaz8636805/17 10:21新的質數

qaz8636805/17 10:23原本假設質數質數只有k個

qaz8636805/17 10:23但卻可以由此找出新的質數

qaz8636805/17 10:23所以質數不只k個

qaz8636805/17 10:24即為無限個

siro020705/17 10:37原PO舉的那個反例有問題吧?

siro020705/17 10:371 + 2*3*5*7*11*13 = 30031 = 59*509

siro020705/17 10:38從這例子來看 原原PO要的是無法被2 3 5 7 11 13任一質數

siro020705/17 10:39整除 但原PO卻拿出了59 509這個尚未找到的質數來整除

siro020705/17 10:43也就是說透過這種方式 就算能找到兩個質數相乘 那也一定

siro020705/17 10:44是新的質數不包含在原本假設的質數內

siro020705/17 10:51但如果是新的質數 那前提就不是最大的質數了

abcdeffg05/17 10:52同樓上,我認為一開始的證明是沒問題的,20年前我學

abcdeffg05/17 10:52集合論和數論時都是用反證法去說明質數無限多

kirimaru7305/17 11:11我發現了30031和我發現了59或509都是有效的

kirimaru7305/17 11:12原本的假設就只有13

kirimaru7305/17 11:15反證法只要打爆13的臉 他的任務就完成了

kirimaru7305/17 11:17不過敘述上確實可能有不嚴謹的地方,例如你在考卷上寫

kirimaru7305/17 11:18「我們創造了N+1,而它明顯無法被N以下的質數整數」

kirimaru7305/17 11:19那可能會成為扣分的理由 除*

NukAnah05/17 11:19嗯嗯嗯,我也是這樣覺得(根本搞不懂)

kirimaru7305/17 11:19然而原原PO是寫無法被p_n以下的質數整除 所以也沒問題

WildandTough05/17 11:23看完第一點就可以end了 邏輯這麼差還跟人高談闊論=

WildandTough05/17 11:23 = 反證法的假設是質數有限 所以能找到一個最大的

WildandTough05/17 11:23質數 但是卻又能找到一個比這個最大的質數更大的質

WildandTough05/17 11:23數 所以假設不成立 那你的例子是不是能找到比你假

WildandTough05/17 11:23設最大的質數更大的質數? 你與其在這邊發廢文 不

我編輯過文章了,補充我敘述的瑕疵,感謝糾正^^ 我舉的反例是能找到更大的質數沒錯,但不是原原po造出來的數,所以需要另外指定的步 驟才比較完整

WildandTough05/17 11:23如拿發廢文的時間多讀點書

豪 你也加油讀書 別浪費時間回廢文了 嘻嘻

※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 11:45:53

Heptagram05/17 11:44明明就自然數比較多

※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 11:51:40

E7lijah05/17 11:57我成功將每個自然數都對應到一個獨特的質數 所以他們應

E7lijah05/17 11:57該一樣多吧?

aa85120205/17 12:15簡單的數學:出一堆數字讓你昏頭;難的數學:不用數字

aa85120205/17 12:15也能讓你寫不出來

Heptagram05/17 12:19要證明雙射才能一樣吧 質數對應到自然數的方法是什麼

rkl05/17 12:32我很喜歡對角線論證法

E7lijah05/17 12:44不想搞太複雜,質數同時也是自然數,我每個質數a找與他

E7lijah05/17 12:44相等的自然數a',a=a'這樣就是一種質數對應到自然數

comp246805/17 14:24你的引理如果不是假設那一串是全部質數就不會成立

qazwsxedc59705/17 15:03質數對應到自然數的方法就是,第1個質數2對到2,第

qazwsxedc59705/17 15:032個質數3對到3,第3個質數5對到4阿...

qazwsxedc59705/17 15:04第n個質數對到某個自然數n+1

hengsao05/17 16:26看兩句就知道這篇不懂裝懂 到底在幹嘛==

看一句就知道你必是大師 請大師開示點醒我

※ 編輯: E7lijah (106.64.137.67 臺灣), 05/17/2023 19:05:38

comp246805/17 20:04對了 你引理前面那串也不成立 除非那些有限個質數是全部

E7lijah05/18 00:40好像是這樣沒錯 我再補一下敘述

※ 編輯: E7lijah (106.64.137.67 臺灣), 05/18/2023 00:42:39

Vulpix05/18 03:24呃……是要追加前提沒錯,不過沒有這麼彎。只要有算術基本

Vulpix05/18 03:25定理在就好:比1大的整數都能寫出質因數分解。

Vulpix05/18 03:26N+1>1,所以可以用質數p們乘出來,但所有的p都不是因數。

comp246805/18 10:32然後你補了那個敘述後 做跟ZAX一樣的做法就行

CTUST05/18 12:24前半還跟得上,後面就不行了