素数定理另证

《关于素数公式素数定理哥德巴赫猜想的初等证明》素数公式是指对于给定的正整数n，小于等于n的素数的个数近似等于n/ln(n)，其中ln(n)表示自然对数。

素数定理是指当n趋向于无穷大时，小于等于n的素数的个数π(n)近似等于n/ln(n)。

公式中的π(n)表示小于等于n的素数的个数。

哥德巴赫猜想是指任意大于2的偶数都可以表示为两个素数之和。

首先证明素数公式。

定义函数S(n)为小于等于n的素数的个数。

我们需要证明当n趋向于无穷大时，S(n)在数学意义下近似等于n/ln(n)。

我们知道，当n越趋近于无穷大时，自然对数ln(n)也趋近于无穷大。

设m为一个足够大的正整数，使得ln(n) >= m。

我们将区间[2,n]均分为m个子区间，每个子区间的长度为(L=n-2)/m。

对于每个子区间，我们选择一个整数ni作为代表，使得ni落在这个子区间内，并且ni是最接近该子区间中点的整数。

由于n趋向于无穷大，我们可以得到ni一定存在。

我们定义T(m)为小于等于n的素数中，满足ni是素数的个数。

显然T(m) <= S(n)，因为ni只是小于等于n的素数中的一个子集。

我们对于每一个ni都检查它是否是素数，最简单的方法是对所有小于等于√ni的正整数k，检查ni是否能被k整除。

若存在整数k使得ni被k整除，则ni不是素数；若不存在这样的整数k，则ni是素数。

现在我们来估计T(m)的上界。

对于每个ni，我们需要进行√ni次的整除运算。

所以，总的运算次数为Sqrt(n1) + Sqrt(n2) + ... +Sqrt(nm)。

由于ni是区间中点附近的整数，所以我们可以将每个Sqrt(ni)近似为Sqrt(L/m) = Sqrt((n-2)/m)。

所以总的运算次数可以近似为m*Sqrt(L/m) = (n-2)*Sqrt(m/(n-2))。

当n趋向于无穷大时，这个运算次数的上界也趋于无穷大。

所以S(n)在数学意义下近似等于n/ln(n)。

素数公式素数公式，在数学领域中，表示一种能够仅产生素数的公式。

即是说，这个公式能够一个不漏地产生所有的素数，并且对每个输入的值，此公式产生的结果都是素数。

根据素数的一个定义：“若自然数n不能被不大于根号n任何素数整除，则n是一个素数”。

[1]这个公式可以一个不漏地产生所有素数，而不会混入一个合数。

例如29，29不能被不大于根号29的素数2，3，5整除，29=2×14+1=3×9+2=5×5+4。

29小于7²=49，所以29是一个素数。

目录1 多项式形式的素数公式2 丢番图方程形式的素数公式3 带高斯函数的素数公式3.1 Mills 公式3.2 威尔逊定理的利用3.3 另一个用高斯函数的例子4 递推关系5 其他公式6 参见7 参考文献多项式形式的素数公式可以证明，一个多项式P(n)，如果不是常数的话，不会是一个素数公式。

证明很简单：假设这样的一个多项式P(n)存在，那么P(1)将是一个素数p。

接下来考虑P(1+ kp)的值。

由于，我们有。

于是P(1 + kp)是p的倍数。

为了使它是素数，P(1 + kp)只能等于p。

要使得这对任意的k都成立，P(n)只能是常数。

应用代数数理论，可以证明更强的结果：不存在能够对几乎所有自然数输入，都能产生素数的非常数的多项式P(n)。

欧拉在1772年发现，对于小于40的所有自然数，多项式P(n) = n2 + n + 41的值都是素数。

对于前几个自然数n = 0, 1, 2, 3……，多项式的值是41, 43, 47, 53, 61, 71……。

当n等于40时，多项式的值是1681=41×41，是一个合数。

实际上，当n能被41整除的时候，P(n)也能被41 整除，因而是合数。

这个公式和所谓的质数螺旋（en:Ulam spiral）有关。

实际上，欧拉发现了这样一个事实：a0+0=a1,a1+2=a2,a2+4=a3,a3+6=a4,...,a（a0）.到a(a0)一项就是合数,其它都是素数。

算术基本定理关于质和计算基本定理的问题一、知识大于1的整数n总有两个不同的正约数：1和n.若n仅有两个正约数（称n没有正因子），则称n为质数（或素数）.若n有真因子，即n可以表示为a⋅b的形式（这里a,b 为大于1的整数），则称n为合数.正整数被分为三类：数1，素数类，合数类关于素数的一些重要理论1.大于1的整数必有素约数.2.设p为素数，n为任意一个整数，则或者p整除n，或者p与n互素. 事实上，p与n的最大公约数(p,n)必整除p，故由素数的定义推知，或者(p,n)=1，或者(p,n)=p，即或者p与n互素，或者p|n.3.设p为素数，a,b为整数.若p|ab，则a,b中至少有一个数被p整除. 事实上，若p 不整除a和b，由性质2知，p与a和b均互素，从而p与ab互素。

这与已知的p|ab矛盾.特别地：若素数p整除an(n≥1)，则p|a4.定理1 素数有无限多个 (公元前欧几里得给出证明)证明：（反证法）假设只有k个素数，设它们是p1，p2，，pk。

记N=p1p2 pw+1。

（N不一定是素数）由第一节定理2可知，p有素因数p，我们要说明p≠pi,1≤i≤k从而得出矛盾事实上，若有某个i,1≤i≤k使得p≠pi,则由p|N=p1p2 pw+1推出p|1，这是不可能的。

因此在p1，p2，，pk之外又有一个素数p，这与假设是矛盾的。

所以素数不可能是有限个。

5.引理1 任何大于1的正整数n可以写成素数之积，即n=p1p2 pm (1)其中pi,1≤i≤m是素数。

证明当n=2时，结论显然成立。

假设对于2≤n≤k，式(1)成立，我们来证明式(1)对于n=k+1也成立，从而由归纳法推出式(1)对任何大于1的整数n成立。

如果k+1是素数，式(1)显然成立。

如果k+1是合数，则存在素数p与整数d，使得k+1=pd。

由于2≤d≤k，由归纳假定知存在素数q1,q2, ql，使得d=q1,q2, ql，从而k+1=pq1,q2, ql。

质数五（四）薛雅元质数又称素数。

指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。

换句话说，只有两个正因数（1和自己）的自然数即为素数。

比1大但不是素数的数称为合数。

1和0既非素数也非合数。

合数是由若干个质数相乘而得到的。

所以，质数是合数的基础，没有质数就没有合数。

这也说明了前面所提到的质数在数论中有着重要地位。

历史上曾将1也包含在质数之内，但后来为了算术基本定理，最终1被数学家排除在质数之外，而从高等代数的角度来看，1是乘法单位元，也不能算在质数之内，并且，所有的合数都可由若干个质数相乘而得到。

F5=4294967297=641×6700417，它并非质数，而是一个合数！更加有趣的是，以后的Fn值，数学家再也没有找到哪个Fn值是质数，全部都是合数。

目前由于平方开得较大，因而能够证明的也很少。

现在数学家们取得Fn的最大值为：n=1495。

这可是个超级天文数字，其位数多达10^10584位，当然它尽管非常之大，但也不是个质数。

质数和费马开了个大玩笑！这又是一个合情推理失败的案例！梅森素数17世纪还有位法国数学家叫梅森，他曾经做过一个猜想：2^p-1 ，当p是质数时，2^p-1是质数。

他验算出了：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2^p-1是质数。

p=2，3，5，7时，2^p-1都是素数，但p=11时，所得2047=23×89却不是素数。

还剩下p=67、127、257三个梅森数，由于太大，长期没有人去验证。

梅森去世250年后，美国数学家科勒证明，2^67-1=193707721×761838257287，是一个合数。

这是第九个梅森数。

20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。

质数排列得这样杂乱无章，也给人们寻找质数规律造成了困难。

现在，数学家找到的最大的梅森数是一个有9808357位的数：2^32582657-1。

费马小定理素数判定蒙哥马利算法(强烈推荐）2009-11-07 12:42费马小定理素数判定蒙哥马利算法约定：x%y为x取模y，即x除以y所得的余数，当x<y时，x%y=x，所有取模的运算对象都为整数。

x^y表示x的y次方。

乘方运算的优先级高于乘除和取模，加减的优先级最低。

见到x^y/z这样，就先算乘方，再算除法。

A/B，称为A除以B，也称为B除A。

若A%B=0，即称为A可以被B整除，也称B可以整除A。

A*B表示A乘以B或称A乘B，B乘A，B乘以A……都TMD的一样，靠！复习一下小学数学公因数：两个不同的自然数A和B，若有自然数C可以整除A也可以整除B，那么C就是A和B的公因数。

公倍数：两个不同的自然数A和B，若有自然数C可以被A整除也可以被B整除，那么C就是A和B的公倍数。

互质数：两个不同的自然数，它们只有一个公因数1，则称它们互质。

费马是法国数学家，又译“费尔马”，此人巨牛，他的简介请看下面。

不看不知道，一看吓一跳。

/BasicStudy/LearnColumn/Maths/shuxuejiashi/j12.htm费马小定理：有N为任意正整数，P为素数，且N不能被P整除（显然N和P互质），则有：N^P%P=N(即：N的P次方除以P的余数是N)但是我查了很多资料见到的公式都是这个样子：(N^(P-1))%P=1后来分析了一下，两个式子其实是一样的，可以互相变形得到，原式可化为：(N^P-N)%P=0(即：N的P次方减N可以被P整除，因为由费马小定理知道N的P次方除以P的余数是N)把N提出来一个，N^P就成了你N*(N^(P-1))，那么(N^P-N)%P=0可化为：(N*(N^(P-1)-1))%P=0请注意上式，含义是：N*(N^(P-1)-1)可以被P整除又因为N*(N^(P-1)-1)必能整除N（这不费话么!）所以，N*(N^(P-1)-1)是N和P的公倍数，小学知识了^_^又因为前提是N与P互质，而互质数的最小公倍数为它们的乘积，所以一定存在正整数M使得等式成立：N*(N^(P-1)-1)=M*N*P两边约去N，化简之：N^(P-1)-1=M*P因为M是整数，显然：(N^(P-1)-1)%P=0即：N^(P-1)%P=1============================================积模分解公式先有一个引理，如果有：X%Z=0，即X能被Z整除，则有：(X+Y)%Z=Y%Z这个不用证了吧...设有X、Y和Z三个正整数，则必有：(X*Y)%Z=((X%Z)*(Y%Z))%Z想了很长时间才证出来，要分情况讨论才行：1.当X和Y都比Z大时，必有整数A和B使下面的等式成立：X=Z*I+A（1）Y=Z*J+B（2）不用多说了吧，这是除模运算的性质！将（1）和（2）代入(X*Y)modZ得：((Z*I+A)(Z*J+B))%Z乘开，再把前三项的Z提一个出来，变形为：(Z*(Z*I*J+I*A+I*B)+A*B)%Z（3）因为Z*(Z*I*J+I*A+I*B)是Z的整数倍……晕，又来了。

n与2n之间必有素数的最简证明【题目】n与2n之间必有素数的最简证明【导言】素数是数论中一个极为重要的概念。

它指的是大于1且只能被1和自身整除的正整数。

素数的性质一直以来都备受数学家的关注和研究。

其中，一个有趣且重要的结论是：对于任意给定的正整数n，n与2n 之间必定存在至少一个素数。

本文将以从简到繁的方式，给出这一结论的最简证明。

【正文】1. 我们首先从基本概念开始，回顾一下素数的定义。

根据定义，素数大于1且只能被1和自身整除。

要证明n与2n之间必有素数，我们需要说明这个区间中不存在任何被除了1和自身以外的数整除的数。

2. 考虑区间[n, 2n]中的所有自然数。

我们可以通过反证法来证明这个区间内至少存在一个素数。

假设区间中不存在素数，即区间中的所有数都可以被除了1和自身以外的数整除。

这意味着，对于区间中的任意一个数x，存在另一个数y（y不等于1和自身），使得x能被y整除。

3. 现在我们观察一下这个数y。

根据前面的假设，y不是素数，因此它可以被除了1和自身以外的数整除。

我们将y表示为y = p * q，其中p和q均为大于1的整数。

4. 根据上一步骤的观察，我们可以得到下列等式：n ≤ x = p * q ≤ 2n。

我们将这个等式进行简化，得到n / q ≤ p ≤ 2n / q。

5. 注意到n和q是已知的正整数，而p是一个大于1的整数。

我们可以看到，当q的取值范围在(1, n)之间时，p的取值范围在(n/q, 2n/q)之间。

6. 我们现在来观察一下p的范围。

根据上述推导，当q在(1, n)之间取值时，p的取值范围在(n/q, 2n/q)之间。

我们可以将p的范围继续简化为(1, 2)。

7. 如果p的取值范围在(1, 2)之间，那么p的取值只能是2。

我们可以得到一个结论：当q的取值在(1, n)之间时，p的取值只能是2。

也就是说，只有当q取值在(1, n)之间时，等式p * q = x才有可能成立。

1.3素数及算术基本定理 知识扫描：1. 素数的定义以及一些基本性质。

大于1的整数n 至少有两个不同的正约数：1和n 。

如果n 没有大于1而小于n 的约数，则称n 是素数。

如果n 有大于1而小于n 的约数，即n 可表示为a b 的形式，则称n 为合数。

（1） 大于1的整数必有素因子（2） 既为偶数又为素数的正整数只有一个，它就是2.（3） 设p 为素数，n 是任意整数，则或者p 整除n ，或者p 与n 互素。

（4） 设p 是素数，,a b 是整数，如果/p ab ，则,a b 中至少有一个被p 整除。

证明：如果p 不整除,a b ，则p 与a 和b 均互素，从而p 与a b 互素，矛盾！（5） 素数有无穷多个。

用反证法证明这个命题，假设素数只有有限个，1212122,3,,1,1.,,(1),/1.k k k i p p p N p p p N N p p p p p p i k p ===+>≤≤ 设是全部素数，考虑显然故有素因子因是全部素数，故必等于某个从而这不可能，因此素数有无穷多个。

2. 唯一分解定理：每个大于1的正整数均可分解成有限个素数的积。

如果不计素因数在乘积中的次序，则其分解方式是唯一的，即1212kk n p p p = a a a，其中i p 是质数，i a 是正整数，1i k ≤≤。

（证明为推理说明性的，可自己来做） 3. n 的约数的标准分解，设n 的标准分解为1212kkn p p p = aa a则正整数d 是n 的约数的充分必要条件是其标准分解为1212kkd p p p = b b b0,1,2,,i i i k ≤≤= b a4. ()()()()()()()()()()()()()()()1212112211212=+1+1+11111+1=+1+1+1kk k ki k k n r n n n n n r n n p p p p p p k r n =+++++++++ 的正约数的个数及正约数的和：记是的正约数的个数，是的正约数之和，且的标准分解式为上式，则有下面给出证明：由于指数有种选取且彼此独立，又由唯一分解定理知指数所有可能的选取产生种不同的约数，因此由乘法原理知即：个数与选取方aaad a a a d b a b b b a a a ()()()()12122k k n n dp p p = 式相等的证明，只需要把展开就可发现形如：的数恰恰出现一次，也就是左右两边相等，命题得证。

素数有无穷多个证明用反证法来证明【序言】数学是一门充满无限魅力的学科，而素数则是数学世界中一道闪亮的珍宝。

在古老的数学领域中，素数一直以来都是备受研究与探索的对象。

素数的奥秘由来已久，其中最具代表性的问题之一就是"素数是否有无穷多个？"这一问题一直困扰着数学家们。

然而，通过反证法的证明，我们能得出结论：素数是无穷多的。

【正文】1. 反证法的基本原理反证法是一种证明方法，通常用于证明矛盾陈述的无效性。

它的基本思想是假设待证明的命题不成立，然后通过推理得出矛盾的结论，从而证明原命题的正确性。

在素数有无穷多个的证明中，我们也将运用反证法来推理。

2. 假设素数只有有限多个我们假设所有素数只有有限多个，即存在一个由所有素数构成的有限集合。

令其为P={p_1, p_2, p_3, ..., p_n}，其中p_n是最大的素数。

3. 构造新的素数考虑一个数M=p_1 * p_2 * p_3 * ... * p_n + 1。

根据我们的假设，M 必然不是素数，因为它不能被集合P中的任何一个素数整除。

这就引出了矛盾。

4. 矛盾的推理我们将M进行因式分解，得到M=(p_1 * p_2 * p_3 * ... * p_n + 1) = p_1 * p_2 * p_3 * ... * p_n + 1。

可以看出，M除以任何一个素数p_i 后，余数都是1。

这意味着M不是任何一个已知素数的倍数，也就是说M不能被P集合中的任何素数整除。

5. 得出矛盾结论根据反证法的思想，由于M不是素数，那么M必须是另一个新的素数。

但这与我们假设的P集合包含了所有素数矛盾，因为M是一个不在P集合中的素数。

【总结】通过反证法的证明，我们得出结论：素数是无穷多的。

这个证明方法的关键在于构造了一个新的数M，它不属于已知的素数集合，也不是已知素数中的任何一个的倍数。

我们可以推断出，素数并不是有限的，而是无限的。

素数的无穷性证明不仅仅是数学知识的一部分，更具有哲学层面上的深意。

目 录引 言一、素数无穷性的若干典型证明方法（一）欧几里德与素数无穷性（二）欧拉与素数无穷性（三）费马数性质与素数无穷性（四）拓扑学与素数无穷性二、中国剩余定理与素数无穷性本文总结参考文献致 谢引 言素数，又称质数，最小的素数是，不存在最大的素数，素数的个数无穷。

研究素数无穷性象征了人类对其智慧的极限挑战，这是两千多年的世界数学史上最优美的定理之一，也是后来算数大厦蓬勃发展的可靠奠基石。

素数无穷性课题研究，千百年来都吸引着很多的数学专家和数学爱好者孜孜不倦的对其进行思考和探究追求。

历史上曾经出现若干种不同的证明方法，年前，欧几里德首先应用反证法来证明了素数无穷。

欧拉同样应用反证法并加入分析原理予以证明。

费马应用费马数的性质，由费马数的无限性性质从侧面让素数无穷得到证明。

以上这些证明研究中有些简便易懂，有些方法闪烁着智慧的光芒，因此足以表明其在数论中的独特的作用和不可替代的地位。

本文将论述给出这个问题的几种具有典型意义的证明方法，并结合这几种方法谨慎引入中国剩余定理予以新的证明方法。

一、素数无穷性的若干典型证明方法（一）欧几里德与素数无穷性假设素数有限，有限集合为，再令。

大于素数集合中所有素数的乘积[1]，素数集合类，接下来分情况进行讨论。

1.若为素数。

是比 中任意元素都大的素数，由此素数无穷得到证明。

2.若为合数。

引理1[2]，假如一个整数可以整除和，且，那么就一定能整除和差为。

由整除，即存在整数因子；也能整除，即存在整数因子，即。

所以。

由于为整数，所以，显然有。

所以， 。

由于为整数，所以显然能够整除。

据引理1可得，任意合数存在一个素因子，不妨令为，那么也能整除，如果假设，则也整除的积。

即是，而 而素数大于等于的素数不存在能整数的数。

同理若等等，结果同上。

此时的素数不包括在之中。

综上，不管为素数还是合数，都找到的素数之外的素数。

所以,素数无穷得到证明。

（二）欧拉与素数无穷性假设素数个数有限，令为，再设新数，由上面引理可知，，任意取一个数到的所有自然数为，共存在四种情况：第一种情况，当为质数时，，第二种情况，当为合数时，则可表示为，则，第三种情况，当时，，第四种情况，当时，。

威尔逊定理及证明
给威尔逊爵⼠跪了
1、内容
⾸先，介绍⼀下什么是威尔逊定理：
1、p为素数。

2、(p-1)! ≡ -1 (mod p)。

有1和2互为充要条件。

2、证明
就证明1为2的充分条件吧。

定义集合A={2,3,4,......,p-2}，如果对于A中每⼀个元素a，均存在A中另⼀个元素b，使得ab ≡ 1 (mod p)，且a不同时，b⼀定不同，则命题⼀定成⽴。

先证对于A中每⼀个元素a，均存在A中另⼀个元素b，使得ab ≡ 1 (mod p)。

⾸先，显然1 ≤ b ≤ p-1。

然后，假设b == 1，则ab = a ≠ 1，不成⽴；再假设b == p-1，则ab = a*(p-1) = ap-a ≡ p-a (mod p)，若p-a == 1的话，须满⾜a == p-1，不成⽴。

得证。

再证不同的a对应的b不相同。

假设存在两个不同的a对应的b相同，再假设这两个a分别为a1，a2(a1 < a2)。

则有(a2-a1)*b ≡0 (mod p)。

⽽(a2-a1)、b均⼩于p且p为素数，故显然不成⽴。

全球最大的悖论出自素数论！它会出现1+0=0，1+1=0和0+0=1这三种情况。

请国、内外素数专家全球最大的悖论出自素数论！它会出现1+0=0，1+1=0和0+0=1这三种情况。

请国、内外素数专家等式两边可以同时约去0，也就是说分母可以为0求函式公式，条件1+0=1，0+1=1，0+0=0，1+1=0，如A1为0，B1为1，C1显示为1前部分看明白的，后部分没完全理解你的意思！如A1为0，B1为1，C1显示为1，这个没怎么看懂。

我理解是A1是变数，数值为0，B1也是变数，数值为1，C1= A1+B1，所以他的值是1？是这样理解不？0和1算素数吗？什么是素数？不是。

质数（prime number）又称素数，有无限个。

一个大于1的自然数，除了1和它本身外，不能被其他自然数（质数）整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。

素数比如2 3 5 7 11 13求一个演算法问题 0+0=0; 1+0=1;0+1=2;1+1=3;#include <stdio.h>int main(){int id;int a[2];printf("请输入第一个位置是否有人（有输入1，没有输入0）:");scanf("%d",&a[0]);printf("\n请输入第二个位置是否有人（有输入1，没有输入0）:");scanf("%d",&a[1]);if(a[0]==0 &&a[1]==0){id=0;printf("\nid=%d",id);}if(a[0]==1 &&a[1]==0){id=1;printf("\nid=%d",id);}if(a[0]==0 &&a[1]==1){id=2;printf("\nid=%d",id);}if(a[0]==1 &&a[1]==1){id=3;printf("\nid=%d",id);}return 0;}0,1,2是素数么素数，又称质数，是只有两个正因子（1和自己）的自然数。