目次

1. Abstract
2. Proof

1. Abstract

Primality of 10¹⁶⁵⁷-9 was proved by Primality proving program based on Pocklington's theorem on August 18, 2003.

2. Proof

input

99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999991
2
3
5
7
11
13
19
37
47
73
101
137
139
277
829
1289
1657
2393
2531
3169
4969
9901
31051
52579
98641
111781
333667
1569889
99990001
1469409649
1984699441
86239064881
37916801893
999999000001
18371524594609
22361420916001
57623262784777
109908191603107
143574021480139
203864078068831
549797184491917
3199044596370769
41168686909062457
143409436964525899
536430531035337769
757108543129939106221
11111111111111111111111
831759677425747570837717
24649445347649059192745899
1595352086329224644348978893
4181003300071669867932658901
38115215074391056784287931569
117680633072620952134930832292859
19108466176791400681292709171992566565029
823799348530495507269035013254489287846904557
1880709802856952955373413305337158032187793270681
11033517351146841676953477818524172302174982813132058195800613488154982399
41784371500167158378186418717091934768077726285039694944003301299623485206849143\
75257
10776547730206021548358735954380169948015708115427100064296791127608890484017725\
60028378495799359646781326368530020399986158679489264953
18003769621913060301122917933414381320096623470379432954163083912593089383447122\
83476688413836335732872748878636782356980191059016837916879951860992805108531754\
82536415661788140280313983951913282899507942705199140855931731062932727709213500\
1873261549867109
0
0

output

Primality proving program based on Pocklington's theorem
  powered by GMP 4.1.2
  version 0.2.1 by M.Kamada
n=999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999991
f[0]=2
f[1]=3
f[2]=5
f[3]=7
f[4]=11
f[5]=13
f[6]=19
f[7]=37
f[8]=47
f[9]=73
f[10]=101
f[11]=137
f[12]=139
f[13]=277
f[14]=829
f[15]=1289
f[16]=1657
f[17]=2393
f[18]=2531
f[19]=3169
f[20]=4969
f[21]=9901
f[22]=31051
f[23]=52579
f[24]=98641
f[25]=111781
f[26]=333667
f[27]=1569889
f[28]=99990001
f[29]=1469409649
f[30]=1984699441
f[31]=86239064881
f[32]=37916801893
f[33]=999999000001
f[34]=18371524594609
f[35]=22361420916001
f[36]=57623262784777
f[37]=109908191603107
f[38]=143574021480139
f[39]=203864078068831
f[40]=549797184491917
f[41]=3199044596370769
f[42]=41168686909062457
f[43]=143409436964525899
f[44]=536430531035337769
f[45]=757108543129939106221
f[46]=11111111111111111111111
f[47]=831759677425747570837717
f[48]=24649445347649059192745899
f[49]=1595352086329224644348978893
f[50]=4181003300071669867932658901
f[51]=38115215074391056784287931569
f[52]=117680633072620952134930832292859
f[53]=19108466176791400681292709171992566565029
f[54]=823799348530495507269035013254489287846904557
f[55]=1880709802856952955373413305337158032187793270681
f[56]=11033517351146841676953477818524172302174982813132058195800613488154982399
f[57]=41784371500167158378186418717091934768077726285039694944003301299623485206\
84914375257
f[58]=10776547730206021548358735954380169948015708115427100064296791127608890484\
01772560028378495799359646781326368530020399986158679489264953
f[59]=18003769621913060301122917933414381320096623470379432954163083912593089383\
44712283476688413836335732872748878636782356980191059016837916879951860992805108\
53175482536415661788140280313983951913282899507942705199140855931731062932727709\
2135001873261549867109
prime factor check
f[0] is a definitely prime factor of n-1
f[1] is a definitely prime factor of n-1
f[2] is a definitely prime factor of n-1
f[3] is a definitely prime factor of n-1
f[4] is a definitely prime factor of n-1
f[5] is a definitely prime factor of n-1
f[6] is a definitely prime factor of n-1
f[7] is a definitely prime factor of n-1
f[8] is a definitely prime factor of n-1
f[9] is a definitely prime factor of n-1
f[10] is a definitely prime factor of n-1
f[11] is a definitely prime factor of n-1
f[12] is a definitely prime factor of n-1
f[13] is a definitely prime factor of n-1
f[14] is a definitely prime factor of n-1
f[15] is a definitely prime factor of n-1
f[16] is a definitely prime factor of n-1
f[17] is a definitely prime factor of n-1
f[18] is a definitely prime factor of n-1
f[19] is a definitely prime factor of n-1
f[20] is a definitely prime factor of n-1
f[21] is a definitely prime factor of n-1
f[22] is a definitely prime factor of n-1
f[23] is a definitely prime factor of n-1
f[24] is a definitely prime factor of n-1
f[25] is a definitely prime factor of n-1
f[26] is a definitely prime factor of n-1
f[27] is a probably prime factor of n-1
f[28] is a probably prime factor of n-1
f[29] is a probably prime factor of n-1
f[30] is a probably prime factor of n-1
f[31] is a probably prime factor of n-1
f[32] is a probably prime factor of n-1
f[33] is a probably prime factor of n-1
f[34] is a probably prime factor of n-1
f[35] is a probably prime factor of n-1
f[36] is a probably prime factor of n-1
f[37] is a probably prime factor of n-1
f[38] is a probably prime factor of n-1
f[39] is a probably prime factor of n-1
f[40] is a probably prime factor of n-1
f[41] is a probably prime factor of n-1
f[42] is a probably prime factor of n-1
f[43] is a probably prime factor of n-1
f[44] is a probably prime factor of n-1
f[45] is a probably prime factor of n-1
f[46] is a probably prime factor of n-1
f[47] is a probably prime factor of n-1
f[48] is a probably prime factor of n-1
f[49] is a probably prime factor of n-1
f[50] is a probably prime factor of n-1
f[51] is a probably prime factor of n-1
f[52] is a probably prime factor of n-1
f[53] is a probably prime factor of n-1
f[54] is a probably prime factor of n-1
f[55] is a probably prime factor of n-1
f[56] is a probably prime factor of n-1
f[57] is a probably prime factor of n-1
f[58] is a probably prime factor of n-1
f[59] is a probably prime factor of n-1
F=f[0]*f[1]^4*f[2]*f[3]*f[4]*f[5]*f[6]*f[7]*f[8]*f[9]*f[10]*f[11]*f[12]*f[13]*f[\
14]*f[15]*f[16]*f[17]*f[18]*f[19]*f[20]*f[21]*f[22]*f[23]*f[24]*f[25]*f[26]*f[27\
]*f[28]*f[29]*f[30]*f[31]*f[32]*f[33]*f[34]*f[35]*f[36]*f[37]*f[38]*f[39]*f[40]*\
f[41]*f[42]*f[43]*f[44]*f[45]*f[46]*f[47]*f[48]*f[49]*f[50]*f[51]*f[52]*f[53]*f[\
54]*f[55]*f[56]*f[57]*f[58]*f[59]
n-1=F*R
F=907952321475960193115902083337974460412022161500387803160784292627929577294779\
88490663690000000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000907952321475960193115902083337974460412022\
16150038780316078429262792957729477988490663689999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999909204767852403980688409791666202553958797783849961\
21968392157073720704227052201150933630999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999909204767852403\
980688409791666202553958797783849961219683921570737207042270522011509336310
R=110137941866199297837331906669612231445432737795528588553922221468847211784663\
81200191072696692978887220955221692216820977923038357025844328216460640558855652\
20205532496707482105457207145705796293649348347209294953684772100900264713843097\
41551991747506907006910477906884591378639177250943842966289485743838979116176354\
83700947248280129142426028571275477586296980308427285303856938156453303639544669\
8896682015801034680134141555417025586876461842721509797332600793729
F is greater than R
main proof
2^(n-1)=1 (mod n)
gcd(2^((n-1)/f[0])-1,n)=n
3^(n-1)=1 (mod n)
gcd(3^((n-1)/f[0])-1,n)=1
gcd(2^((n-1)/f[1])-1,n)=1
gcd(2^((n-1)/f[2])-1,n)=1
gcd(2^((n-1)/f[3])-1,n)=n
gcd(3^((n-1)/f[3])-1,n)=1
gcd(2^((n-1)/f[4])-1,n)=1
gcd(2^((n-1)/f[5])-1,n)=1
gcd(2^((n-1)/f[6])-1,n)=1
gcd(2^((n-1)/f[7])-1,n)=1
gcd(2^((n-1)/f[8])-1,n)=1
gcd(2^((n-1)/f[9])-1,n)=1
gcd(2^((n-1)/f[10])-1,n)=1
gcd(2^((n-1)/f[11])-1,n)=1
gcd(2^((n-1)/f[12])-1,n)=1
gcd(2^((n-1)/f[13])-1,n)=1
gcd(2^((n-1)/f[14])-1,n)=1
gcd(2^((n-1)/f[15])-1,n)=1
gcd(2^((n-1)/f[16])-1,n)=1
gcd(2^((n-1)/f[17])-1,n)=1
gcd(2^((n-1)/f[18])-1,n)=1
gcd(2^((n-1)/f[19])-1,n)=1
gcd(2^((n-1)/f[20])-1,n)=1
gcd(2^((n-1)/f[21])-1,n)=1
gcd(2^((n-1)/f[22])-1,n)=1
gcd(2^((n-1)/f[23])-1,n)=1
gcd(2^((n-1)/f[24])-1,n)=1
gcd(2^((n-1)/f[25])-1,n)=1
gcd(2^((n-1)/f[26])-1,n)=1
gcd(2^((n-1)/f[27])-1,n)=1
gcd(2^((n-1)/f[28])-1,n)=1
gcd(2^((n-1)/f[29])-1,n)=1
gcd(2^((n-1)/f[30])-1,n)=1
gcd(2^((n-1)/f[31])-1,n)=1
gcd(2^((n-1)/f[32])-1,n)=1
gcd(2^((n-1)/f[33])-1,n)=1
gcd(2^((n-1)/f[34])-1,n)=1
gcd(2^((n-1)/f[35])-1,n)=1
gcd(2^((n-1)/f[36])-1,n)=1
gcd(2^((n-1)/f[37])-1,n)=1
gcd(2^((n-1)/f[38])-1,n)=1
gcd(2^((n-1)/f[39])-1,n)=1
gcd(2^((n-1)/f[40])-1,n)=1
gcd(2^((n-1)/f[41])-1,n)=1
gcd(2^((n-1)/f[42])-1,n)=1
gcd(2^((n-1)/f[43])-1,n)=1
gcd(2^((n-1)/f[44])-1,n)=1
gcd(2^((n-1)/f[45])-1,n)=1
gcd(2^((n-1)/f[46])-1,n)=1
gcd(2^((n-1)/f[47])-1,n)=1
gcd(2^((n-1)/f[48])-1,n)=1
gcd(2^((n-1)/f[49])-1,n)=1
gcd(2^((n-1)/f[50])-1,n)=1
gcd(2^((n-1)/f[51])-1,n)=1
gcd(2^((n-1)/f[52])-1,n)=1
gcd(2^((n-1)/f[53])-1,n)=1
gcd(2^((n-1)/f[54])-1,n)=1
gcd(2^((n-1)/f[55])-1,n)=1
gcd(2^((n-1)/f[56])-1,n)=1
gcd(2^((n-1)/f[57])-1,n)=1
gcd(2^((n-1)/f[58])-1,n)=1
gcd(2^((n-1)/f[59])-1,n)=1
n is definitely prime
39.359 sec.