※ 引述《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 可以发文解释一下你的方法觉得对的理由，最好比较一下欧几里德定理跟你的差别，不然很难服众