[代數] 質數無限多個證明

看板Math作者 (QQ)時間9年前 (2017/01/07 00:54), 9年前編輯推噓0(0推 0噓 29→)
留言29則, 5人參與, 最新討論串1/1
有關質數無限多個的證明 採用反證法的話 一堆資料都採用以下脈絡 ---- 假設質數只有n個 依序排成p_1<p_2<...<p_n 令P=p_1*p_2*...*p_n +1 則發現1.所有質數(p_i,i=1~n)都不整除P 2.1,P整除P 所以P也是質數 矛盾 ---- 覺得怪怪的地方在於1.2.能直接推論P是質數嗎?? 根據定義 要說明P是質數 是要證明P只能被1,P整除 但是"1.所有質數(p_i,i=1~n)都不整除P"沒有直接告訴這點吧?? 是否嚴格來說 還要從"所有質數(p_i,i=1~n)都不整除P" 去證明 "P只能被1,P整除" 因此 採用從反證中再使用反證法 假設存在合數N, 2<=N<=P-1 使得N整除P 再來因為N是合數所以N=a*b，而且a,b又只能是合數(若是為某個p_i則矛盾) 但是會沒完沒了a=x*y, x,y又只能是合數 blabla 最後收尾可能是要用2^m會衝到無限大去做矛盾吧 整個變得好麻煩 但是我就覺得沒有那麼顯然@@ (不能用到"對某個合數N，必定存在某個質數整除他" 應該說 如果這個當已知就結束了 也可以說我證的那串就是這句話的證明) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.173.160.83 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1483721672.A.A74.html
→
01/07 00:58, , 1F
你應該看到敘述有錯吧= = 正確敘述是P=p1*p2*..+1
01/07 00:58, 1F
→
01/07 00:59, , 2F
若P是質數 那就造出一個更大的質數 若P不是質數則因
01/07 00:59, 2F
→
01/07 00:59, , 3F
為他有一個不為P1,P2,...Pn的質因數 因此還是得到一
01/07 00:59, 3F
→
01/07 01:00, , 4F
個新質數 因此質數有無限多個
01/07 01:00, 4F
這一樣呀 你寫的"若P不是質數則因為他有一個不為P1,P2,...Pn的質因數"正是我的疑問 不過這一切都可以用樓下Opp大提的那個正整數唯一質因數分解定理解決 難怪大家都直接推論過去了 我再去翻翻書看這個定理的證明會不會以"質數無限個"當已知 不會的話就OK了 謝謝上下兩位!
→
01/07 01:10, , 5F
a,b是合數, 且存在唯一分解(按大小),如果分解出來的
01/07 01:10, 5F
→
01/07 01:11, , 6F
質數在p1,...pn中, 矛盾
01/07 01:11, 6F
→
01/07 01:11, , 7F
若分解出來質數不在p1,...pn中, 亦矛盾
01/07 01:11, 7F
→
01/07 01:12, , 8F
(這是根據算術基本定理的結果)
01/07 01:12, 8F
→
01/07 01:14, , 9F
所以a,b是1或P, 代表P仍是質數
01/07 01:14, 9F
※ 編輯: znmkhxrw (1.173.160.83), 01/07/2017 01:23:13
→
01/07 01:23, , 10F
上面這行寫錯, 所以不存在 N = a*b
01/07 01:23, 10F
→
01/07 01:24, , 11F
可以分解P
01/07 01:24, 11F
→
01/07 03:41, , 12F
志豪看到你記錯，他會很桑勳
01/07 03:41, 12F
→
01/07 03:42, , 13F
而且我覺得一樓敘述還是錯的，應該是假設質數有限多
01/07 03:42, 13F
→
01/07 03:43, , 14F
個，則可假設最大的質數為Pn，今設P=P1*...*Pn+1
01/07 03:43, 14F
→
01/07 03:44, , 15F
則P不可被任意Pi for i in 1~n整除，P為質數。假設
01/07 03:44, 15F
→
01/07 03:44, , 16F
不成立
01/07 03:44, 16F
→
01/08 12:22, , 17F
證明這個哪需要唯一質因數分解，不是只需要同餘唯一
01/08 12:22, 17F
→
01/08 12:22, , 18F
就好了嗎？
01/08 12:22, 18F
→
01/08 12:23, , 19F
甚至也不需要同餘唯一這麼強，只要證明用某個寫法會
01/08 12:23, 19F
→
01/08 12:23, , 20F
餘一的數字絕對不可能換個寫法就餘零整除就夠了
01/08 12:23, 20F
→
01/08 13:34, , 21F
需要的是「整數必有質因數」，這個不難證啊。
01/08 13:34, 21F
願聞其詳 算術基本定理可以直接推論V大你說的 但是直接說明你那句話是如何辦到的?? ※ 編輯: znmkhxrw (111.255.22.79), 01/08/2017 15:21:26
→
01/09 15:47, , 22F
給定d>0, ∀n∈Z, ∃q,r∈Z, 使得 n = d*q + r
01/09 15:47, 22F
→
01/09 15:51, , 23F
q,r 唯一並且 0 ≦ r ＜ n
01/09 15:51, 23F
→
01/09 15:52, , 24F
Euclidean division, 上面我只是方便舉所以用比較強
01/09 15:52, 24F
→
01/09 15:53, , 25F
證明只用到整數良續性
01/09 15:53, 25F
→
01/10 14:44, , 26F
忘記排除1,0,-1這幾個無聊的整數(0好像不用排除)。
01/10 14:44, 26F
→
01/10 14:45, , 27F
2有質因數，假設2~k都有質因數，一旦k+1可以分解就
01/10 14:45, 27F
→
01/10 14:46, , 28F
可以確定k+1有質因數。不能分解的k+1自己就是質數，
01/10 14:46, 28F
→
01/10 14:46, , 29F
所以也有質因數。強數學歸納法就可以了。
01/10 14:46, 29F
‣ 更多 znmkhxrw 的文章
文章代碼(AID): #1ORyl8fq (Math)