如何找到一个大素数

yangchuanju

如何找到一个大素数

引言
我们知道，清一色正整数111…1中含有除2和5以外的所有素数。
1不是素数，1中没有素数。
11是一个素数，11中只有一个素数11。
111是一个合数，其中有2个素数3和37。
1111是一个合数，其中有2个素数11和101。
11111是一个合数，其中有2个素数41和271。……
111…1型清一色正整数是由(10^n-1)/9得到的，不除以9之前是正整数999…9。

10的φ因子：在999…9或111…1中第一次出现的素因子称之。
N=1时，3是9的一个素因子，且9中只有一个素因子3，记φ1(10)=3；
N=2时，11是99或11的一个素因子，尽管99中还有一个素因子3，因为3已在n=1时出现了，故只认为11是99或11的素因子，记φ2(10)=11；
N=3时，37是999或111的一个素因子，尽管999和111中还有一个素因子3，因为3已在n=1时出现了，故只认为37是999或111的素因子，记φ3(10)=37；……
N=4时，有一个φ因子，φ4(10)=101；
N=5时，有二个φ因子，φ5(10)=41、271；
N=6时，有二个φ因子，φ6(10)=7、13；
N=7时，有二个φ因子，φ7(10)=239、4649；……

yangchuanju

如何找到一个大素数
已经知道11111不是素数，如何找到11111中的素因子？用试除法分解是最基本的一种方法。为减少试除次数，我们不必用11111以内的所有素数试除一遍，而是用11111平方根105以内的素数试除即可。
当我们用41试除时发现41可整除11111，至此11111的一个素因子被找到。
11111除以41余271，271是素数还是合数认为不知道。
对于271这个数，我们把它称为清一色正整数11111除以41后的“数根”，大素数就存在于这种“数根”中。
继续用试除法确定，271的平方根等于16.46，只要用16以内的素数2,3,5,7,11,13试除一遍即可。
请注意，对于271我们并不需要真正的再试除了，因为所需素数均小于41，我们直接可确定271是素数了。
还值得注意的是，第一步试除并不必要把105以内素数挨个试，因为11111含5个1，只需要105以内的模5余1的奇素数，进一步转换为模10余1的奇素数11,31,41,61,71,101试除即可。（实际只用11,31,41试除即完成）
271是一个大素数，我们已经找到并确定。
这就是我在本帖中所要说明的找大素数的一种方法。

下面再举一例予以说明。
已经知道1111111不是素数，1111111平方根等于1054，用1054以内模14余1的素数29,43,71……239……，试除之。
当我们用239试除时发现239可整除1111111，至此1111111的一个小素因子239被找到。
1111111除掉239以后，剩余的“数根”是4649，4649的平方根等于68.18<239，不必二次试除，直接断定4649是一个大素数即可。
复查素数表，4649确是一个素数。
注意，如果“数根”的平方根大于或等于已找到的小素数，则必须用试除法继续试除。

蔡家雄

蔡家雄

卢卡斯级数的通项公式

Ln=Round[((1+√3)/√2)^(2^n )/2]

L1=2,
L2=7,
L3=97,
L4=18817=(2^5 -1)(2^5*19 -1)=31*607,
并且：2^31 -1 与 2^607 -1 同为素数。
L5=708158977,

L6=1002978273411373057
   =(2^7 -1)(2^7*61698958748239 -1)
   =127*7897466719774591,
已证：2^127 -1 是素数，

蔡家雄猜想：2^7897466719774591 -1 是大素数。

杨老师如果证明了此大数为真，必将名垂青史，流芳百世。

yangchuanju

10^p-1中存在众多的大素数因子
当n是正整数时，10^n-1和(10^n-1)/9中存在有素因子p的任意次方；
当n是一个素数p时，(10^p-1)/9或是素数，或是素因子不太多的合数，它的素因子往往都是一些大素数。
P=3,  (10^3-1)/9=111=3*37；
P=5,  (10^5-1)/9=11111=41*271；
P=7,  (10^7-1)/9=1111111=239*4649；
P=11,  (10^11-1)/9=21649 × 513239；
P=13,  (10^13-1)/9=53 × 79 × 265371653；
P=17,  (10^17-1)/9=2071723 × 5363222357；……
分解式中的21649， 513239， 265371653，2071723， 5363222357，……都是一些大素数因子。

P值更大时，(10^p-1)/ 9中的素因子更大：
P=29时，(10^p-1)/9=3191 × 16763 × 43037 × 62003 × 77843839397<11>
P=31时，(10^p-1)/9=2791 × 6943319 × 57336415063790604359<20>
P=37时，(10^p-1)/9=2028119 × 247629013 × 2212394296770203368013<22>
P=41时，(10^p-1)/9=83 × 1231 × 538987 × 201763709900322803748657942361<30>
P=43时，(10^p-1)/9=173 × 1527791 × 1963506722254397<16> × 2140992015395526641<19>
P=47时，(10^p-1)/9=35121409 × 316362908763458525001406154038726382279<39>
……

而当p=19，23时(10^p-1)/9分别是19位和23位的大素数；已知当p=2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343 ……时(10^p-1)/9都是素数。

当p等于509时已经被证明(10^509-1)/9不是素数，但至今仍未有人找到它的任何一个素因子；
最小的几个已经被证明不是素数但未被分解式清一色正整数是（包括p=509）：
p=509 (c509), p=557 (c557), p=647 (c647), p=991 (c991), p=1117 (c1117),p=1259 (c1259), p=1447 (c1447), p=1607 (c1607), p=1637 (c1637), p=1663 (c1663)，……

yangchuanju

10^2p-1中存在众多的大素数因子
(10^2p-1)/9=(10^p-1)/9*(10^p+1)，(10^p-1)/9之中含有众多的大素数或大素数因子，上文已经介绍；在(10^p+1)之中同样存在众多的大素数因子。
当p等于2时，10^p+1=101是目前所知道的唯一的100…01中的素数；
当p等于3时，10^p+1=1001=7*11*13；
当p等于5时，10^p+1=100001=11*9091；
当p等于7时，10^p+1=10000001=11*909091；
当p等于11时，10^p+1= 11^2 × 23 × 4093 × 8779；
当p等于13时，10^p+1= 11 × 859 × 1058313049<10>
……
分解式中的9091，909091，4093，8779，1058313049……都是一些大素数因子。
10^p+1总含素因子11，首先去除之，剩余“数根”尚未完全分解的有：
10^347+1 =  11 × 368720813 × 805697219 × 89700105169<11> × [c3411495834...<318> ]
10^353+1 =  11 × 1006029527<10> × 5654000177636083959487421885693964261705 0503<44> × [c1598235487...<300> ]
10^359+1 =  11 × 25849 × 19210610797963667218565939<26> × [c1830721976...<329> ]……

(10^p+1)/11=10^(p-1)-10^(p-2)+……-10+1=9090…9091中也有不少素数，请参阅下文。

yangchuanju

10^n-1中的唯一因子往往是一些更大的素数因子
A040017给出46个10^n-1分解式中的唯一因子，前25个唯一因子是：
1  3
2  11
3  37
4  101
5  9091
6  9901
7  333667
8  909091
9  99990001
10  999999000001
11  9999999900000001
12  909090909090909091
13  1111111111111111111
14  11111111111111111111111
15  900900900900990990990991
16  909090909090909090909090909091
17  100009999999899989999000000010001
18  10000099999999989999899999000000000100001
19  9090909090909090909090909090909090909090909090909091
20  900900900900900900900900900900990990990990990990990990990991
21  909090909090909090909090909090909090909090909090909090909090909091
22  
142857157142857142856999999985714285714285857
142857142855714285571428571428572857143
23  
9999999999999900000000000000
9999999999999900000000000000
9999999999999900000000000001
24  
9999999999999999999999999999999900000000000000000000000000000000
9999999999999999999999999999999900000000000000000000000000000001
(32个9)+(32个0)+(32个9)+(31个0)+1——128位——指数320
25  
109890109890109890109890109890109890109890109890109890109890
10989010989010989010989010989010989010989010989009890
109890109890109890109890109890109890109890109890109890109890
10989010989010989010989010989010989010989011
(18个109890)+09890+(17个109890)+11——217位——指数654

yangchuanju

9090...91型素数
A054416给出10个由n-1组90和1组91（末尾）构成的素数，它们是（n值）：
2, 3, 9, 15, 26, 33, 146, 320, 1068, 1505；
这些素数含在（10^k+1）/11的分解式中，其中的k值分别是（A001562）：
5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011；
与n相比，k=2n+1。
A001562还给出2个更大的9090...91型素数，k=268207, 1600787。

yangchuanju

900...01型素数
A056797给出在9*10^n+1中当n=3,4,5,9,22,27,36,57,62,78,201,537,696,790,905,1038,66886,70500,91836，100613, 127240 时都是素数。
最小的几个素数是：9001,90001,900001,9000000001，……

yangchuanju

99…90…01与111…111
10^n-1等于999…9，共n个9；(10^n-1)/9=111…1，共n个1。
许多清一色正整数111…1的φ因子或复合因子（其中包括较小的φ因子）为99…90…01形式，它们是怎么由111…1变换过来的？
经核查，只有当n是6的倍数时，111…1中才会含有99…90…01形式的φ因子或复合因子，
其中当n=6时，111111中含φ因子91=7*13；91=111111/111/11=1001/11；
当n=12时，111111 111111中含φ因子9901（素数）；9901=111111111111/111111/101=1000001/101；
当n=18时，111111 111111 111111中含φ因子999001=19*52579；999001=111111111111111111/111111111/11/91=1000000001/11/91；
当n=24时，111111…<24>中含φ因子99990001（素数）；99990001=111111…<24>/111111…(12>/10001=1000000000001/(73*137)；
当n=30时，111111…<30>中含复合因子9999900001，φ因子109889011为9999900001的一个因子，109889011=9999900001/91；
111111…<30>/111111…<15>/11=90909090909091=7*13*9091*109889011
109889011=90909090909091/(7*13*9091)=111111…<30>/111111…<15>/11/(91*9091)
当n更大时，(10^n-1)/9的φ因子的变换过程更复杂，不再向下分析。

n        (10^n-1)/9的φ因子或复合因子分解式
6        91=7*13
12        9901=9901素数
18        999001=19*52579
24        99990001=99990001素数
30        9999900001=7*13*211*241*2161
36        999999000001=999999000001素数
42        99999990000001=7*7*13*127*2689*459691
48        9999999900000001=9999999900000001素数
54        999999999000000001=70541929*14175966169
60        99999999990000000001=61*9901*4188901*39526741
66        9999999999900000000001=7*13*599144041*183411838171
72        999999999999000000000001=3169*98641*3199044596370769
78        99999999999990000000000001=7*13*13*157*6397*216451*388847808493
84        9999999999999900000000000001=9901*226549*4458192223320340849
90        999999999999999000000000000001=19*29611*52579*3762091*8985695684401
96        99999999999999990000000000000001=97*206209*66554101249*75118313082913
102        9999999999999999900000000000000001=7*13*291078844423*377526955309799110357
108        999999999999999999000000000000000001=109*153469*59779577156334533866654838281
114        99999999999999999990000000000000000001=7*13*1458973*753201806271328462547977919407
120        9999999999999999999900000000000000000001=99990001*100009999999899989999000000010001