目次

  1. Abstract
  2. Proof

1. Abstract

Primality of (2·101204+1)/3 was proved by Primality proving program based on Pocklington's theorem on August 17, 2003.

2. Proof

input

66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
6667
2
3
11
29
101
239
173
281
3613
4649
338669
909091
1527791
57009401
121499449
2182600451
821856609631
13403893556831
1963506722254397
212057054080446499
2140992015395526641
120525789336558438197
7306116556571817748755241
62997514894345258734433816429
6798855735656881396055959081077830421892567
2923500556298303355222653948542706598448925085853709961673200056984872843366529
17520889308448176299236543876085057549177040060630786419006322010941244780445558\
87071171166365583553287053602700568010683873135238140340718711012045219107751867\
190380847
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=666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
66666666666666666666666666666666666666666666666666666666666666666666666666666666\
666667
f[0]=2
f[1]=3
f[2]=11
f[3]=29
f[4]=101
f[5]=239
f[6]=173
f[7]=281
f[8]=3613
f[9]=4649
f[10]=338669
f[11]=909091
f[12]=1527791
f[13]=57009401
f[14]=121499449
f[15]=2182600451
f[16]=821856609631
f[17]=13403893556831
f[18]=1963506722254397
f[19]=212057054080446499
f[20]=2140992015395526641
f[21]=120525789336558438197
f[22]=7306116556571817748755241
f[23]=62997514894345258734433816429
f[24]=6798855735656881396055959081077830421892567
f[25]=29235005562983033552226539485427065984489250858537099616732000569848728433\
66529
f[26]=17520889308448176299236543876085057549177040060630786419006322010941244780\
44555887071171166365583553287053602700568010683873135238140340718711012045219107\
751867190380847
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 probably prime factor of n-1
f[13] is a probably prime factor of n-1
f[14] is a probably prime factor of n-1
f[15] is a probably prime factor of n-1
f[16] is a probably prime factor of n-1
f[17] is a probably prime factor of n-1
f[18] is a probably prime factor of n-1
f[19] is a probably prime factor of n-1
f[20] is a probably prime factor of n-1
f[21] is a probably prime factor of n-1
f[22] is a probably prime factor of n-1
f[23] is a probably prime factor of n-1
f[24] is a probably prime factor of n-1
f[25] is a probably prime factor of n-1
f[26] is a probably prime factor of n-1
F=f[0]*f[1]*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]
n-1=F*R
F=508973598015527827864711361608875212608753236719417444765349269299710878445812\
07245800966139158885679840640336224548875212608753236719417444765349269299710878\
44581207245800457165560870152012775624862940000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000050897359801552782\
78647113616088752126087532367194174447653492692997108784458120724580096613915888\
56798406403362245488752126087532367194174447653492692997108784458120724580045716\
556087015201277562486294
R=130982563587969826218754201503291570265268097069583309585225468550024035265865\
45470413791088164625525706517443703018053764910888126649334467196166178046093142\
46994033223952473403018269577246175694343610593362116819691471970781233932070046\
46337274028709470862592369568684118244455147078810153452215047832089621776932901\
39614341144167840806227175657677620869087800879564409438114458842872640925707722\
46101183222387706220439541092660496265539208455760087699440522789836951045664700\
47752570733170615292514440132188113707593845588397316568478224025878247072098651\
17074050321123928285254010839576844137529943411608257821084877243908155346694250\
07176349622336010144926577165734266694276656528283215176210839839
F is not greater than R
main proof
2^(n-1)=1 (mod n)
gcd(2^((n-1)/f[0])-1,n)=1
gcd(2^((n-1)/f[1])-1,n)=n
3^(n-1)=1 (mod n)
gcd(3^((n-1)/f[1])-1,n)=1
gcd(2^((n-1)/f[2])-1,n)=1
gcd(2^((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
R=2Fs+r, 1<=r<2F
s=128673239730574192164769233776633859423380828551719210883718853122609672045246\
27320967119904264164983931107482479837481482517472694483805192623774889827579904\
2378164400740275172904515465438469069531532
r=363362248852048547352242482875889173588660909210695212876322372218281030604107\
86345648401433976544261841591805486008630545348363490514577070047230281854602169\
27172378538885151423682890523766014109542684118047950676039901891983779229772194\
53649409830723850909809043362865041736017569874960708858349078370534791830715533\
86110483326483669511825824176527067285254374076817093051881781174616315453013033\
89140585378418832655255576307878225319742131875055336678434263832462946464354860\
981859022973608709195023
let D be discriminant of (mF+1)(2F^2+(r-m)F+1)>=N+1
D=F^2((F(2F+r))^2-4(N-F(2F+r)))=128045105352794800324125458555887804143465800666\
94578872627417489384568283111490002645905913979273852507580056830075780666152470\
23594798151113012478435486918030400205844437176674228043609773469777435303075845\
20635648428856749102683775597803282124075381413841587131140727817339733281850514\
30442860833529090903373135419027771487583419226204485499192578125310007576018073\
87650696489338702814159745625500339040528313636108287974300347407095454126500821\
08684965392279797738777756425320775613831492002260512779580694653705148700672430\
65084220127707777848949265635524832795493018458763558086273507092355070597163177\
89376790148561480680419847199803634642731675034597071748423866408077660751696461\
43238736802670676601815454762994312945962643536658153673937418353264551331594913\
17084669124569016827691245603294276012884672160828764504916972507972367322710860\
37854212224450370602252913259190119174265749714574889399030886397274152180580372\
47062737843114743737196441518139019236086580942321183147077308489995407531287098\
83333453070230784856498523830438212390001553005846998148881465401690350086756021\
44977110467870820275051429534494017350186906273764209452368953852742233566216964\
55557256205786281133629619801360277457803076525795933934609455889260267418597491\
13973659614527699065486783668083437039245628976828048944958659409330971419105778\
20528876290446534319091902826253277217819377098519636941544607755826538898672263\
61451438495057705307926527101405310763632731037671299857903239351110113704296141\
88374796017149434245456552258002281247180541067073167815474373865713197996349587\
13069859427910281660255206845412563122063359134947776121112398923867747796125988\
03167448557194886925978784840996622821832820835205090189443365591538561561875107\
81377934812145461208786013790204961462123293188640004981179172030210354659385078\
53351090477514244640753181035940574925663917458169142983670665450578094651254400\
84279739330232841177647606492241600167370926574935832446050290856321394323373111\
29934759716705326767979507481660296164543369842830476665981621128829716904186910\
55759109990532957277232626573067875948896085586961018121555631940754589768983159\
33058131873008785581744209249569317663241111667003381449029205192115964331523955\
96848815564791469369582003970100454174778351352013307182988143087900975712900959\
08874897456891655290845835064455870645269437311669918242101704021667385987477804\
85499334345176839095526415741365386857370361518971008590495293213708514711022972\
03227444948464688398705640896330891023883734329305261962682225245354951890992535\
28037189851666399135466274733969471715881609671258323403688884180499619775481987\
10917719266677842710867158079543553512518733352478823381951661641074180575533634\
28263924355226864370964116448663853771403672638281156391692097128615936453482376\
85017258050496609498502996494474499995210850370499368830731072801850007090092994\
29851396679695879053551028628431168812636478886701825007651550103847754351450979\
79571074997375759007568073496180466122719180263545222155412152868732437945935340\
3264
m=max(1,ceil((F^2(2F+r)-isqrt(D))/2F^2))=1
(mF+1)(2F^2+(r-m)F+1)=3578339074945173503074123839259645525101988916234010655541\
41422353521247885027715628665722906767875194971471089576632686744764739567564282\
36881072565205904598122301480501410625788846732505045376529269361956125194850797\
33755149503103050028655627934678206061502615221824031365069016989635089252686950\
18410623602478632562506890938273333431446565634823785193525840524461154753460348\
29496411744457259843625213594340756391145105910615456324559855025606639098242159\
23657765689334993497318287249383392288361583529157163028872873098073146115270988\
39752712827528531658240139052088985260241532077628198578214497732252520236220464\
92683588593447099466948409359874238195044034919366208674089827241152189101170284\
42001108871385150719601560387823022164873057212369387662968221550121768727641134\
49165467893926112194771051165386054932111664358234227205210248762852914077333435\
27832740735002288759425844776493627809793982189646493619651884472343190773138753\
38739785748618581798627531276451930692426498292288510901230205865713183431677369\
12579746964115149519967445141631965356233918254530859937600562765434464170193968\
37356745718406302716894041282054166978242935557370519422649524284073197028089907\
25458564115103326812664391819615029866280626801340313091657828881026671602070854\
52298203053701068187127782208917071177195265388661759230229219838798938269099276\
29400067678763464917216451880640569820764572787075991105212719653522502413686143\
22673699555314754227390011252748593957862147147859573765326408633633447789765384\
92241595
(mF+1)(2F^2+(r-m)F+1) is greater than n
s is not zero
r^2-8s=1320321238908180558680772798828357908042983806821139208152810081094382685\
53127694927790009698061876676129474578010436798890780886616796845197680846847207\
54376277352533825155310644731627499675441075207994998757598200120104987919630277\
98973826919121895074796119837616983724794726447168291998401566592945023422842724\
12883825756042717621978692784188933305591904678817328177066958231723723728071834\
66508518761858599390145090758268646624626050544356241017569397494445457133754602\
66950664125169939499299630289255337737688328797176731381585388096807471205321504\
19476707939829508156740219591614170247531509323562613396340949822630959635566565\
80430849492529120514438548248294300799873727172097453537228096948820465394541457\
42654177477500647023315726895037401966704723837458868253029453215307131638787970\
26201326049133409661815219023497289329116637004160041907829638572010097148204348\
20252367223322405351573356329862842921193810091646352056712254281709354032300548\
890038592097621070788511906062591687355796091718273
r^2-8s=x^2+y, 0<=y<2x+1
x=363362248852048547352242482875889173588660909210695212876322372218281030604107\
86345648401433976544261841591805486008630545348363490514577070047230281854602169\
27172378538885151423682890523766014109542684118047950676039901891983779229772194\
53649409830723850909809043362865041736017569874960708858349078370534791830715533\
86110483326483669511825824176527067285254374076817093051881781174616315453013033\
89140585378418832655255576307878225319742131875055336678434263832462946464354860\
981859022973608709195022
y=726724497704097094704484965751778347177321818421390425752644744436562061208215\
72691296802867953088523683183610972017261090696726981029154140094460563709204338\
54344757077770302847365781047532028219085368236095901352079803783967558459544389\
07298819661447701819618086725730083472035139749921417716698156638130991876971713\
99039427950836630269781182068916597699811239903825412340143860492458934982614735\
79566682158239278311992551217940891935068853848119487150476188639610687006508338\
727594322439464862137789
r^2-8s is not a square
n is definitely prime
7.156 sec.