如何证明形如4n3的素数有无限多个

如何证明形如4n3的素数有无限多个 篇一：证明形如4n+3的素数有无限多个四、证明题（每小题10分，3题共30分）1.证明：形如4n+3（n为非负整数）的素数有无限多个.证明：用反证法若形如4n3的素数为有限个，设为p1,p2,pk.(整个证明的思想是用反正法，先设形如4n+3的素数只有有限个，设为p1,p2,pk，再找到4n+3形式的数p,并且这个p是不等于p1,p2,pk的，这样就与我们假设的有限个就矛盾了)令q4p1p2pk14(p1p2pk1)3，（现在构造一个数q，通过变形我们知道q也是4n+3形式的数，显然qpi,i1,2,.k（若相等则有(4p1p2pi1pi1pk1)pi1，这不可能），若q已经为素数，就找到了不等于p1,p2,pk的素数q，定理已经得证，若q不是素数，我们考虑它的素因数，在下面的步骤）显然pi都除不尽q.（反证法，若能除尽，即piq，而由上面可知14p1p2pkq，则有pi1，矛盾） 若q为素数，而qpi，i1,2,.k，定理已经得证.（这个结论上面的注已经说明）现在考察q不是素数，那么它必有素因数 （一个数能分解为若干素数的乘积） (4l1)(4m1)4(4lmlm)14u1，（此式子说明4n+1形式的乘积还是4n+1的形式） 而q一定不能全是4n1形式素因数，一定还有4n3形式的素因数p， （因为q也是4n+3的形式，若全是4n+1的形式，它们的乘积得不到4n+3的形式，故一定还有4n3形式素因数p. 由假设知q是奇数，它的因数肯定都是奇数，所以它的因数要么是4n+1的形式，要么是4n+3的形式，不可能是4n+2与4n+4的形式（因为这两个还是偶数）且不是p1,p2,pk中的一个，与假设矛盾. （前面已经证明pi都除不尽q，而p是q的因数，因此p能整除q，故p不是p1,p2,pk中的一个）故形如4n3的素数有无限多.（一开始我们假设的是有限个，k个，而现在我们找到了不等于p1,p2,pk的其它的4n+3形式的素数p，顺环往复，这说明有限个的假设不正确，故形如4n+3的素数有无限多个）注：主要步骤就是黑字的部分，后面的彩色的字是我做的注解，做题目的时候可以不写。篇二：论文：关于素数有无穷多个的证明摘要：有关于素数的个数是无穷多个的定理有许多的证明方法，最早的证明要见于欧几里德的名著几何原本第九篇的命题20中：素数的数目比以往任何指定的数目都要多，即素数有无穷多个.*在总结前人证明的基础上用数学归纳法再次证明这一命题. 关键字：最小正约数；fermat数列；合数；调和级数；数学归纳法 1 引言一个大于1的整数，除了1和它本身以外不能被其他正整数整除，就称为素数.通常用字母p、q表示，例如1,2,3,5,7,11,13,17,都是素数.设x1,我们以x表示不超过x的素数个数.不难算出x0x2 53 10 50 415欧几里德的名著几何原本第九篇的命题20证明了: 素数的数目比以往任何指定的数目都要多，即素数有无穷多个:limxx这样把全体素数按大小排列就得出一个无穷数列2=p1p2p3pn后来发现在全体正整数中素数仅占很少一部分.下面我们就来证明一下这个命题.2 引理、定理及证明引理1设整数a1，他的大于1的最小正约数d必为素数. 1d,所以证明 若d不是素数,则由素数定义知,必有整数d,使得1dd , dda但这与d的专家设矛盾.故而引理得证.由此推出: 若a不是素数,则必有da.引理2设有一个无限正整数列 1uu1u2u3s3如果它的任,意两项均互素,则一定有无限多个素数.证明设ds是us的大于1的最小正整数,由此得到一个无限数列d1,d2,ds,.由假设知,它们也是两两互素的,所以是不同的整数,而由引理1知ds均为素数.这样就证明了引理2.引理31设整数a1,则a一定可以表为12raq1q2qr (1)其中qi均为素数, 且q1q2qr,以及整数i01ir证明 当a2时,引理显然成立.设n3,假设引理对所有的a2an均成立.当n为素数时,则引理对于an显然也成立;当n不是素数时设d是n的大于1的最小正约数ndn1.由引理1知d为素数.此外,这时必有2n1n,故由假设知n1可表为(1)的形式,所以n亦可表为这样的形式,有归纳法知引理3成立. 直接推论任一正整数a一定可表为ak2l(2)其中l1,或是不同的素数的乘机, k是正整数.引理4设x2,我们有 3111(3) a1axp1其中求和号分展在所有不超过x的正整数上,连乘号分展在所有不超过x的素数上.证明 设2kx2k1.显然有11111111122kpppppppxpxpx11显然出现在上式右边的乘积中.注意到对于不同的a它们的表达式(1)一定是不同的,这就证明了引理4.定理5 n!与n!1互素. n2证明 首先证明n与n1互素由于它们的最大公因子要整除它们的差,即n1n1,所以最大公因子只可为1,故而n与n1互素.由此得 n2与n21互素, 因为它们的最大公因子只为1.依次可得 n23n1与n23n11互素, 因为它们的最大公因子只为1.即n!与n!1互素.接下来我们开始证明定理 素数的个数是无穷多的证明 方法(一) 3用反证法假设素数只有有限个 即2=p1p2ps设np1p2ps1,d是它的大于1的最小正约数,由引理一知d是素数.把全体素数按大小顺序排列,就得到一个无限数列,我们记为2=p1,p2,ps,ps1,.定理得证方法(二) 3著名的fermat数列fn221n0,1,2, n就是满足引理2中的条件的数列,显然有1f0f1fn下面证明他们两两互素,设n0,k1,由fnk222n2k1 知fnfnk2,设d=fn,fnk,因而必有d2, fn均为奇数,所以d1. 定理得证 方法(三) 3设n2,对任意一个a1an,在它的表达式(2)中一定有:1k1或l使一些不超过n的不同的素数的乘积.这样, k可能取得值得个数,而l所可能取的值的个数不超过以下的组合数之和nnnn12. n12所以必有nn1即 nlog2nn2 定理得证 2n不超过n的素数有n个，所有的k个不超过n的不同的素数的乘积个数为k由此即得所说的结论.方法(四) 3如果只有有限个素数,那么式(3)的右边当x时为一有限数.但是左边的调和级数当x时是发散的.这一矛盾就证明了定理.方法(五)由定理五,得n!与1,2,3,n1,n互素,那么n!1有两种可能(1) n!1为素数;(2) n!1为合数.(1)设an!1为素数,集合ax0xnxn有b个素数 则集合bx0xn!1xn内至少有b+1个素数.(2)设an!1为合数,则在集合b中至少有2个元素可以被a整除 aba可证c=minxx且hhn为素数.且(1)设集合a内有b个素数,则集ax合b内至少有b+1个素数.综合(1)、（2）可得:设集合ax0xnxn有b个素数. 则集合b内至少有b+1个素数.1xn内至少由b+2个素数. 重复上述步骤可得集合c=x0xn!1！继续沿用上述步骤,用数学归纳法可证:设集合ax0xnxn有b个素数.则集合dx0x11，xnn重至少由b+d个素数. n!1！由此:当d时, e=素数的个数b+d=+.故可得素数的个数是无穷多的.(指导老师:王明军)参考文献：1张文鹏.初等数论m.西安:陕西师范大学出版社, 20xx-62欧几里德.几何原本m.北京:人民日报出版社, 20xx-103潘承洞、潘承彪.素数定理的初等证明m.上海:上海科技出版社, 1988-02篇三：素数有无穷多个的几个证明构造法：1.欧几里得证法：证：假设素数只有有限个，设为q1,q2,.qn，考虑p=q1q2.qn+1。显然，p不能被q1,q2,.qn整除。故存在两种情况：p为素数，或p有除q1,q2,.qn以外的其它素因子。无论何种情况，都说明素数不止有限个。假设错误，所以素数有无穷多个5.2.设p1,.,pn是n个两两不同的素数。再设ar是其中任意取定的r个素数的乘积。证明：任一pj(1jn)都不能整除 p1.pn/ar+ar;由此推出素数有无穷多个。证：因为pj若不是ar的因子，必然是p1.pn/ar的因子；或者，pj若是ar的因子，必然不是p1.pn/ar的因子。因此，p1.pn/ar+ar或者是素数，或者除p1,.,pn之外有其它素因子。无论何种情况，都说明素数不止有限个。假设错误，所以素数有无穷多个。3.级数法：假若素数只有有限个p1,.,ps.证明：对任意正整数n必有 11111(1).(1)nppn11s。由此推出素数有无穷多个。 n证：psp111111)(1).(1)p1psp11ps1 n1nn11)1-1p1ps(1111112.).(1.)p1p1psp1ps 1(因为任意正整数都可以表示成素数或素数的乘积） n1n故上式成立。因为级数1n1n递增，趋于正无穷大，由上式n(1p)n11n111.(111)ps可知：素数有无穷多个。（否则，上式右侧为常值）4.fermat数法：设n0,fn=22+1.再设mn.证明：若d1,且dfn,则d不整除nfm.由此推出素数有无穷多个。证：设2m/2n=r,2n=p则当mn时，必有fn22-1=(22+1)(pr-1-pr-2+.-1) mn=(2+1)(1)k1prk=(22+1)q=fm-2. 2nk1由条件可得：dfm-2,又d1,且dfn,故d3.则d不整除fm. 当mn时，假设dfm,推出d不整除fn.由以上命题：假设di均为素数且ni递增，则d1fn1d1不整除fn2;d2fn2d1,d2