※ 引述《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
并假设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我也不是数学系，有误烦请纠正

嗯嗯 我的答案跟小当家一样

这个就数学系在分析导论的前几堂课吧

我先 打那么多谁看得完

实数不可数的反证法不就是用经典的康托尔对角线证法吗

推这篇

不明觉厉

这篇就是典型的会把圈外人吓到对数学更没兴趣的文章…

对角线那个想了好久才搞清楚他在干嘛

原po什么系

这里是什么版？

这里本应是废文板才对现在我搞不懂了

要考试的时候搞懂过，现在看都忘记了

任两个费马数互质有那么trivial吗？

回s大，没有XD但再写下去我怕真的太多

没 你那个"反例"已经跟原命题冲突了 原命题已经假设最大质数了 在你的例子里 最大的质数是13 那59跟509就不是一个质数 要验证也是拿2,3,5,7,11,13去验证才对

差点忘了这里是个学术书论坛

谢啦 你清楚地说明我上篇文章推文的疑惑 证明式不严谨

虽然你知我知天知地知59,509也是质数 但那跟原本假设的"质数的最大值"相违背这样

zax是用比较通俗的方式说明 这篇是写成逻辑数学式这样

做个每日还这么哈扣，不晓得以后会不会来0.999_=1

应该是可以直接说 "到这一步可以证明最大的质数不存在"这样就好吧干 楼上0.999_=1 要开新战场了吗XD

要请出戴德金分割了吗XD

这里是什么版阿这么艰深

接着肯定就是 1+2+3+....=-1/12 了吧

不是吧，这个真的不艰深啦，连我文组女友都听得懂了

会来西恰的怎么可能有女友 我书读得少 别骗我

大哥怎么这么电，果然做电化学的个个都是天才

总而言之 我那个写法本来就是反证法下的产物 出现明确问题or反例=>矛盾 大概是这样吧 不想再回一篇惹

第一个证明没有问题你举出 30031 这个具体例子并不会造成该证明变得不完整

假设质数的数量为有限，那我们只要作出一个不在上列有限个质数的质数，就可以得到矛盾从而得知质数有无限个这应该是zax大大的证明思路

喔 不对 当我没说 XD 我仔细看一下原文的字句确实是不太严谨的 比较好的方式应该是再分两种情况：N+1 是质数和不是质数 然后再分别得到矛盾

同r大 不是说那个证明不行 而是至少补加点叙述才比较完整

想起当年待数学系的痛苦回忆了 谢啦

不过我也想过针对这个瑕疵的叙述需不需要这么计较 毕竟本来就是反证法推出的错误性质了

用费马数证是没错啦，但是要先证费马数互质

当然不是1阿，你们听过p-adic number吗?(X

楼上是神

其实也不会太难就证F_n=F_1*F_2*...*F_(n-1)+2

我知道证法 但文章已经太长 这里写不下(X

那一天，大家想起过去的 ptt 是怎样的状况

请数学小圈圈放过西恰

我是不是走错板了0.0

其实就是他写的不够仔细，p_n是最大质数且N+1>p_n，故N+1不是质数，又无法被的有限的n个质数的任一整除，矛盾

p-adic number就我的理解就是p进位表达（p为质数）

看你这篇文我恍神了三次

同时加上一个特别的距离定义，让小数点左右两边都可以是无穷的且收敛应该说小数点左边才对

结果整片讨论区没有人提到阿列夫数或 Beth 也是蛮可惜的

去Google了对角线证法，很666

0.999.. = 1, 跟 1/9 * 9 = 1 其实是一样概念 只是很多人对分数跟有理数理解还不够而已

楼上是认真还是在唬烂？ 0.999999...要等于 1 也是需要被严格定义的，光序理论就说不通

不明觉厉，但觉得很厉害。

好文 推

为啥我看这篇文会怪怪的阿

抱歉进到数学版了……什么这是西洽？

唉呦豆页好痛

其实反证也可以通俗地解决，如果0.99…循环不等于1，那两者之间必然能找到无限多个非零实数，但你用你已知的国高中数学逻辑去算就会发现你连一个非零实数都找不到，只会条条大路通向两者是同一个数

感觉不出哪里有瑕疵，59，509比p_n大这件事就违反假设啊？

推个魔法

嗯嗯我也是这么想的

老师我选c

不管59和509是啥，他们都把原命题打爆了，所以反证法还是成立

你不是数学系...你也打太多XD

恩恩对 我也是这么想的

推，打这么多我还是看完了

跟我想的一样

简单说 质数若有限个分别是2,3,5...,p_k 这k个质数那我们想像2*3*5*...*p_k+1所产生的数字2*3*5*...*p_k+1若此数字本身就是质数因为不能被2,3,5...,p_k这k个质数整除所以是新的质数若数字不是质数 即是合数则可进行质因子分解但因为2,3,5,...,p_k都不能整除所以质因子分解后会产生新的质数原本假设质数质数只有k个但却可以由此找出新的质数所以质数不只k个即为无限个

原PO举的那个反例有问题吧?1 + 2*3*5*7*11*13 = 30031 = 59*509从这例子来看 原原PO要的是无法被2 3 5 7 11 13任一质数整除 但原PO却拿出了59 509这个尚未找到的质数来整除也就是说透过这种方式 就算能找到两个质数相乘 那也一定是新的质数不包含在原本假设的质数内但如果是新的质数 那前提就不是最大的质数了

同楼上，我认为一开始的证明是没问题的，20年前我学集合论和数论时都是用反证法去说明质数无限多

我发现了30031和我发现了59或509都是有效的原本的假设就只有13反证法只要打爆13的脸 他的任务就完成了不过叙述上确实可能有不严谨的地方，例如你在考卷上写“我们创造了N+1，而它明显无法被N以下的质数整数”那可能会成为扣分的理由 除*

嗯嗯嗯，我也是这样觉得（根本搞不懂）

然而原原PO是写无法被p_n以下的质数整除 所以也没问题

看完第一点就可以end了 逻辑这么差还跟人高谈阔论== 反证法的假设是质数有限 所以能找到一个最大的质数 但是却又能找到一个比这个最大的质数更大的质数 所以假设不成立 那你的例子是不是能找到比你假设最大的质数更大的质数？ 你与其在这边发废文 不如拿发废文的时间多读点书

明明就自然数比较多

我成功将每个自然数都对应到一个独特的质数 所以他们应该一样多吧？

简单的数学：出一堆数字让你昏头；难的数学：不用数字也能让你写不出来

要证明双射才能一样吧 质数对应到自然数的方法是什么

我很喜欢对角线论证法

不想搞太复杂，质数同时也是自然数，我每个质数a找与他相等的自然数a'，a=a'这样就是一种质数对应到自然数