数学建模社区-数学中国

标题: 素数判定式的推导与应用 [打印本页]

---

作者: 素数516466    时间: 2012-2-17 16:53
标题: 素数判定式的推导与应用

素数判定式

海南省乐东县保显学校  陈泽辉

数字，它是那么的简单，那么的朴素。可以说人类认识世界是从认识数字开始的，但是不知道是哪一天开始，人类偏要把数字分成偶数与奇数，还把奇数分出素数与奇合数。也许是人类与生俱来就是开拓自然的“鬼斧神工”吧，在漫漫岁月中，人类就是智慧的奴隶，永不休止地去发现与创新自然。
5 x7 l4 U5 _, D: x2 N) B. u在人类认识数字、运用数字的历史长河里，有一种数——素数（只有1和它本身两个正因数的数），它始终披着炫丽的迷彩，犹如雨后的彩虹，总把七彩的美丽展现在人类的眼前，却不让人类捕捉。一直以来，素数以它那深邃、神秘、鬼魅的性情舞弄着人类的智慧，众多的数学先辈、伟大的数学家们对它束手无策，至今还任之逍遥、任之“香眠”。笔者爱好估摸与想像，在一次偶阅中得识《哥德巴赫猜想》简介，便对探究素数产生的极大的兴趣，经过几年的探究，自以为得一快捷探求与判明素数的方法，望投缘者给予描眉点睛：
0 W$ ^0 H7 H5 f6 g( Y' y+ ~1 o% u一、素数判定式
若n、x、y为非0正自然数，有n≠2xy+x+y时，则数A=2n+1为素数。如n=1、2、3、5、6、8、9、11……等等时，均不属于正整数集合2xy+x+y，因此数A=2n+1即3、5、7、11、13、17、19……等等为素数。而n=4、7、10、12、13、16、17……等等时，属于正整数集合2xy+x+y，因此数A=2n+1即9、15、21、27、33、35……等等为奇合数。理论证明素数个数无限：因为全体非0自然数并非能用数集2xy+x+y表示，也就是说非0正整数集合包含数集2xy+x+y或说数集2xy+x+y属于非0正整数集合的子集，所以在非0正整数集合中，永远存在n≠2xy+x+y，因此素数A=2n+1永远有无限多个。
二、素数判定式的推导与论证
在所有的自然中，一个数非偶数即为奇数。奇数可用2n+1表示，在奇数中，一个数要么是合数要么就是素数，也就是说当N为自然数时，2n+1要么是合数要么是素数。笔者把奇数A=2 n +1中的n称判定素数的因子，也就是说若数A为合数时，称n为非素数因子；若数A为素数时，称n为素数因子（素因子）。比如15=2×7+1是合数，则称7为非素数因子；而31=2×15+1为素数，则称15为素数因子，等等。所以要判明某一非0自然数是否为素数还是合数，只需去判定它的因子是否为素数因子或非素数因子便可。（为了便于说明，以下n、x、y字母所表示的数值皆为非0正自然数）。
关于素数判定式，可以从两个方面来推导：首先，设一个奇合数为A=2 n +1，它有两个奇因数分别为P=2x+1与T=2y+1，则会有2 n +1=（2x+1）（2y+1）=4xy+2x+2y+1=2×（2xy+x+y）+1，即有n =2xy+x+y时，数A为合数。反之若n≠2xy+x+y，则数A必为素数。这是素数判定式的反例证明，如果需从无究的角度上来进一步举证，则可通过下面第二种方法得之。
4 {7 U# z4 u- d1 t) A其次，我们有知奇合数必定是由两个奇数相乘构成，如15=3×5、539=7×49……等，因此笔者把奇合数分为有因数3、5、7、9……（2N+1）进行分类整理：
1 t, @0 C0 e; \5 ~0 \+ V1、以2×1+1=3为最小因数的奇合数有：3×3、3×5、3×7、3×9……3×（2y+1），设这时有x=1、y=1、2……n无究，则通式为（2x+1）（2y+1）。该奇合数链的素数判定因子依次为4、7、10、13……n，因为数链第1项为4，每递增一项值增大3，因此该奇合数链的素数判定因子链通项式为：3y+1=(2x+1)y+x,即为2xy+x+y。①
* B/ X4 p- \! F2 ~2、以2×2+1=5为最小因数的奇合数有：5×5、5×7、5×9、5×11……5×（2y+1），设这时有x=2、y=1、2……n无究，则通式为（2x+1）（2y+1）。该奇合数链的素数判定因子依次为12、17、22、27……n。因为数链第1项为12，每递增一项值增大5，因此该素数判定因子链通项式为：5y+2=(2x+1)y+x,即为2xy+x+y。    ②
3、以2×3+1=7为最小因数的奇合数有：7×7、7×9、7×11、7×13……7×（2y+1），设这时有x=3、y=1、2……n无究，则通式为（2x+1）（2y+1）。该奇合数链的素数判定因子依次为24、31、38、45……。因为数链第1项为24，每递增一项值增大7，因此该素数判定因子链通项式为：7y+3=(2x+1)y+x,即为2xy+x+y。  ③
……                 ……
M、以2×（2n+1）+1=N为最小因数的奇合数有：N×N、N×（N+2）、N×（N+4）、N×（N+6）……[2×（2n+1）+1]×[2×（2n+1）+1+2m] [2×（2n+1）+1]×[2×（2n+1+m）+1],因为（2n+1+m）所表示同样是任意自然数，而2×（2n+1+m）+1仍然是一个奇数，所以这时若设有x=（2n+1）、那么y=（2n+1+m）=1、2……n无究依然成立，则上面通式可为（2x+1）（2y+1）。该奇合数链的素数判定因子依次为2 x（x +1）、2 x（x +1）+（2 x +1）×1、2 x（x +1）+（2 x +1）×2、2 x（x +1）+（2 x +1）×3……2 x（x +1）+（2 x +1）×n。因为数链第1项为2 x（x +1），每递增一项值增大2 x +1，因此该素数判定因子链通项式为：（2 x +1）y+ x，即为2xy+x+y。     第M式
因此，若有一个奇数A=2 n +1，它的素数判定因子n要是等于（2 x +1）y+ x或2xy+x+y，那么该数为合数；反之若有一个奇数A=2 n +1，它的素数判定因子n要是不等于（2 x +1）y+ x或2xy+x+y，那么该数为素数。因此得素数判定式：若有n、x、y为非0自然数时，且有n≠2xy+x+y时，则数A=2n+1为素数。
0 L- x( y9 v( ?证明1：有n=1时，数A=2N+1=2×（2xy+x+y）+1=2×（3y+1）+1=6y+3=3×（2y+1），此时数A是3的倍数，能整除3；有n=2时，数A=2N+1=2×（4y+2+y）+1=8y+4+2y+1=10y+5=5×（2y+1），此时数A是5的倍数，能整除5；……有N=n时，数A=2N+1=2×（4ny+n+y）+1=4ny+2n+2y+1=（2n+1）（2y+1），此时数A是（2n+1）的倍数，能整除（2n+1）。
/ {. G& d, o! x+ f* O9 L证明2： 若有n、x、y为非0任意自然数，假设n=2xy+x+y为任意自然数， 那么：①、根据n=2xy+x+y得 ，当2x+1=1时，x与前提“有n、x、y为非0任意自然数”相矛盾。②、根据n=2xy+x+y得 ，当2x+1为奇合数时，则n- x必不能为素数（因为一个素数不能整除合数），如果n- x不能为素数，说明n取值不能为任意自然数，这与前提“有n、x、y为非0任意自然数”相矛盾。③、根据n=2xy+x+y得 ，当2x+1素数时，则n- x必为素数且与2x+1相等，这时“y=1， n=3x+1”， 这与前提“有n、x、y为非0任意自然数”相矛盾。综合上面三点可知2xy+x+y不能全等于非0自然数n ，或者说非0自然数n包含2xy+x+y，所以在非0自然数列中，2xy+x+y只是偶数或奇数的子集，也就是说n≠2xy+x+y永远存在，因此素数个数永远无限。
因此判定一个奇数A是否为素数，只要用数A=2 n +1的素数判定因子n代入关系式2xy+x+y里即能判明。用n不等于或等于2xy+x+y的前题来判定奇数是否是素数，此法只是一种素数判别式，它不能等同用于探寻第n个素数是几，但此法相较于试商法或X X 筛法，却能通过数字的缩放而尽大地简化了计算过程，从而达到更快判寻素数的效果，特别是此方法若用于计算机编程，更能体现出它的实用性。（而孪生素数判定式则是素数判定式的精装版）
# q9 ]+ E- L$ v  |/ d5 p  K, c三、非素数因子规律表
5 l  ?4 F* t+ @* \4 U0 \$ y$ J7 F& R把能整除3、5、7、9……2n+1奇合数的非素数因子整合成表，使得每个非素数因子都有相应坐标位置（如图表）。

非素数判定因子汇总表

Y行 9 b  v) M5 y; c# h$ ^+ w X列   q, n: s3 c, }( d file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image004.gif	1	2	3	4	5	……	X
1	4
2	7	12
3	10	17	24
4	13	22	31	40
5	16	27	38	49	60
6	19	32	45	58	71	……
7	22	37	52	67	82	……	2 X（2 X +1）
8	25	42	59	76	93	……	2 X（2 X +1）+（2 X +1）×(Y-X)
9	28	47	66	85	104	……	2 X（2 X +1）+（2 X +1）×(Y-X)
……	……	……	……	……	……	……	……
Y	3 Y +1	5 Y +2	7 Y +3	9 Y +4	11 Y +5	……	2xy+x+y

( _  |. I/ \* l; h, X3 m# P: g. W第1列为能整除3奇合数的非素数因子集合……第X列为能整除2X+1合数的非素数因子集合；同理，第y行因子表示为能整除奇合数2 X +1的第y个奇合数的因子。不难得出当x=y时，非素数因子的通项式为2x（2x+1）或2y（2y+1），且在同一列式的（或同一行）因子数中，每增一行（或列）时，非素数因子增大2x+1（或2y+1）值。比如从点（x，y）起，每增一行数时非素数因子便增大（2x+1）×1值；每增二行数时非素数因子便增大（2x+1）×2值；……每增K行数时非素数因子便增大（2x+1）×K值；所以此表里任意非素数因子均可表示为：
$ p6 \/ D# S; Y8 g( l& ]①、2 x（x+1）+（2x+1）×K（x 为非0自然数，K=Y-X为任意自然数）。
②、当x=y时（即行与列相交），非素数因子数集合可表示为2x（2x+1）或2y（2y+1）。
3 k& {: C) Y7 l! H" ^③、当行与列的关系为y =x+1时，表中素数判定因子数集合可表示为y =2 x 2+4 x +1。
④、当行与列的关系为y =x+2时，表中素数判定因子数集合可表示为y =2 x 2+6 x +2。
……
, v: Y1 r7 h/ ^. z" L! d⑤、当行与列的关系为y =x+ K时（K=Y-X为任意自然数），表中素数判定因子数集合可表示为y =2 x2+（2+2K）x+K。
5 [" E" M" l/ T  w! m所以此非素数判定因子汇总表内容丰富，任你如何横竖、斜对的推敲，都能找出相应的关系式，值得去发掘，这对于探究或判别素数应该有用处。
四、素数判定式的几个运用
综上所述，笔者介绍以下几种素数判别式的使用方法（或许是大数的分解法）：
4 g2 x$ P2 O' }5 `& a2 \①、根据判别式2xy+x+y，若数2N+1的因子N=2xy+x+y即若有 （整除）时，N为非素数因子，则数2N+1有一个因数为2x+1。如49=2×24+1，把N =24代入 ，当x=1时，不能整除；当x=2时，不能整除；当x=3时，能整除，得出49是合数，有因数为2x+1=2×3+1=7。而83=2×41+1，把N =41代入 ，当x=1、2、3、4、5、6、7（最大取7，因为当取值时x=8时，y﹤1无意义），均不能整除，因此83为素数……
+ x6 s# Z% O7 P* a②、根据列表所示，有素数判定因子通式2 x（x+1）+（2x+1）×K（K=X-Y），如有奇合数为2N+1，那么得出 ，若有K为自然数时（整除），N为非素数因子，则合数2N+1有一个因数为2x+1。如119=2×59+1，把59代入 ，当x=1、2时不能整除，当x=3时，该式K值等于5（K=5整除），因此N（59）为非素数因子，119为奇合数，它的两个因数为（2x+1）与2（x+K）+1（注：x+K=Y），即2×3+1=7与2×（3+5）+1=17；而199=2×99+1，把因子99代入 ，当x=1、2、3、4、5、6（最大取6，因为当取值时x=7时，y﹤1无意义），均不能整除，因此199为素数……
③、据非素数因子通式N=2 x（x+1）+（2x+1）×K（K=X-Y），可知若N为非素数因子时，则K永远小于N。根据N=2 x（x+1）+（2x+1）×K，得出二次方程2 x2+2x+2K x +K-N=0，化简得一个关于x的二次方程：2 x2+（2+2K ）x +（K-N）=0。该方程的两个根为x=[-（2+2K）±√4（K2+2N+1）]/4，如若方程有整数根，即x有整数解时，则数2N+1为合数，此时（K2+2N+1）必有完全平方根；反之，如若（K2+2N+1）没有完全平方根，那么x没有整数解，则数2N+1为素数。事实上当N、K为自数数时，（K2+2N+1）必是形如（a+1）2的完全平方式，因此（K2+2N+1）定有完全平方根。因为在非素数因子列表中，K值永远小于N，因此只要有在K＜N时，（K2+2N+1）能开出整数平方根或配成完全平方式，此时数A=2N+1为合数，如91=2×45+1，在K=3﹤45有32+2×45+1=（9+1）2，所以91为奇合数，它的两个因数为2×K+1=7和（9+1）+K=13……；而数97=2×48+1，在K﹤48的数集内（K2+2N+1）没有完全平方根，有且仅有K=48时（K2+2N+1）才有完全平方根，素数判定因子式中“K值永远小于N”相矛盾，因此97是素数。……
五、运用素数判定式试找特定合数前的素数个数
根据非素数判定因子汇总表，我们大致可以找到特定数N2=2×[2 x（x+1）]+1前的素数个数：如若32=9=2×[2 ×1×（1+1）]+1，数9为最小的奇合数，所以它（9=2×4+1）前面有4-1=3个奇素数（3、5、7）；如若52=25=2×[2 ×2×（2+1）]+1，因为小于2×2前还有1×3、1×2、1×1共3组，则奇合数25（25=2×12+1）前面有12-4=8个奇素数（3、5、7、11、13、17、19、23）；如若72=49=2×[2 ×3×（3+1）]+1，因为小于3×3前还有1×7、1×6、1×5、1×4、1×3、1×2、1×1、2×4、2×3、2×2共10组（因在2xy+x+y框架内，当x=1、y=8时2xy+x+y的值大于x=3、y=3时的值，因此1×8不属排除之列；而2×1、3×2、3×1亦有1×2、2×3、1×3，所以也不属排除之列），当则奇合数49（25=2×24+1）前面有24-10=14个奇素数（3、5、7、11、13、17、19、23、29、31、37、41、43、47）；……此法只为估摸计算素数个数，仅供参考，但是否可用于论证“n2与（n+1）2之间至少必有一个素数”的猜想呢？欢迎来到博客http://107681778.blog.163.com/

" @- r9 B: q6 `0 A! \) m% B

) F6 s" |' ^6 h/ A
. U5 p9 D& l  U1 r6 l4 l: K

0 i. ~5 p( ~" R: @0 q- c; l% h. V$ f2012年2月

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5