目次

  1. Abstract
  2. Proof

1. Abstract

2·101755-1 was a known prime number. The following proof was generated by Primality proving program based on Pocklington's theorem on September 4, 2003.

2. Proof

input

19999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
9999999999999999999999999999999999999999999999999999999999999999999999999999
2
3
31
37
41
53
79
271
757
1951
3511
28081
35803
238681
333667
1577071
2906161
16357951
265371653
310362841
35081393881
162503518711
258360989311
240396841140769
355087294364791
360924572424391
440334654777631
537947698126879
3352825314499987
4185502830133110721
151192179464100066631
908554529084060531791
78683340229586000558911
900900900900990990990991
2304017384484085131816292573
1786946360382838276990549597027
5538396997364024056286510640780600481
483418418597220677238517353915231961831
44933275139025237741442164195375614371497219389368548160257661491391
44018367507556071172725810811606857705691099317190005947371549514438736424439607\
12412219115912275096151178083947984145769389193080971175686825860671696108273269\
7146231
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=199999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999
f[0]=2
f[1]=3
f[2]=31
f[3]=37
f[4]=41
f[5]=53
f[6]=79
f[7]=271
f[8]=757
f[9]=1951
f[10]=3511
f[11]=28081
f[12]=35803
f[13]=238681
f[14]=333667
f[15]=1577071
f[16]=2906161
f[17]=16357951
f[18]=265371653
f[19]=310362841
f[20]=35081393881
f[21]=162503518711
f[22]=258360989311
f[23]=240396841140769
f[24]=355087294364791
f[25]=360924572424391
f[26]=440334654777631
f[27]=537947698126879
f[28]=3352825314499987
f[29]=4185502830133110721
f[30]=151192179464100066631
f[31]=908554529084060531791
f[32]=78683340229586000558911
f[33]=900900900900990990990991
f[34]=2304017384484085131816292573
f[35]=1786946360382838276990549597027
f[36]=5538396997364024056286510640780600481
f[37]=483418418597220677238517353915231961831
f[38]=44933275139025237741442164195375614371497219389368548160257661491391
f[39]=44018367507556071172725810811606857705691099317190005947371549514438736424\
43960712412219115912275096151178083947984145769389193080971175686825860671696108\
2732697146231
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 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[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=f[0]*f[1]^5*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]
n-1=F*R
F=212912910202827345609283589848921024788750541346633675256444827859680604311539\
07974623702826456942216946032929049598851937869566392006821492229362094592849618\
53427027281200682149222936209459284959724297925252927226056387037720249037074348\
01356094444811770094433940341616957105596465699855498792752833291655432507665964\
00706419999999999999999999999999978708708979717265439071641015107897521124945865\
33663247435551721403193956884609202537629717354305778305396707095040114806213043\
36079931785077706379054071503814657297271879931785077706379054071504027570207474\
70727739436129622797509629256519864390555518822990556605965838304289440353430014\
45012072471667083445674923340359929358
R=939351210828286022265311283101279598089092342991312117876967868999976301582812\
31518564810805279493633207927847963396127048483439511544740165142295185271214585\
20502977201577641175761190220280477671143526165254170093064663110141904997611387\
55989512856387217285169138421569812610888199637956590587539025825474806014662389\
90775787707817675921112730460398448202322528330942738098161058928010839163061557\
27302819705184815292045172637566701000458442566073930815672861320991009015080810\
12713577291085576607197105451542243741058098041317813616529856636507509976731192\
61411169545284731426155110123992358052625702284904460371924697210221904486413962\
02779632238003449714417261889383342025632833908217993027126578431885546633554167\
13572211920260588647999987901356467150998749321657268455784774184041721188509281\
40818819855528366972096960802778708192354459703595803283178721301221057298660436\
23296732889823871484419340552698382579546180488647790823031787897986549131469566\
63196816689852103374554476504093557028507141243643551954540935997101647529869113\
392938705674464264379914921960640749259081
F is not 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)=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
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
R=2Fs+r, 1<=r<2F
s=220595174321141763792017981073942706160086160036010410199098054936001572516669\
83272997410027554422549652139993693314434583183454802835022651598429625746639687\
74042353928846661273070588021743755509934825923783871609102197881995254698312311\
13554596809835077293973744703741518019143756033964887458895498124044608763146389\
97604811722789990285122792026856344084641878492720507850603534309705602367960126\
9489643
r=391756418610299777998305713935011494865147182189596301440468642374521271172238\
13070139150894570893747998869971572495669888657236622847007787647160331711312850\
17002989851694698583469973621051016713053797473473809836281635725246713187709745\
48063635948903522536302246138297339814700747570628959092296086837981273019418760\
37832019511483544807108599205095469286714860834514946482860299773001921672119157\
05882105490716359396388231472529641223418946059993274584720309092101675420931995\
74655616629265835023023185658436195354735549853254969558384831767731350322551949\
58645221123824792408270939606800986336079250545743323698028560886897444292186970\
79132013332005929201658778616363980693
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)))=137363352383911696588890911311621019693167675493\
73422462459857342489841576098946023515637372139925134612818785384891775989914650\
88018289458883766359352862402403809729747932693863902887650836037527308844058916\
47463029050892867114767097590501194562587487006938869935540476504117563248193035\
82942922151142723476148787822575649094771553758352931622222997511007797659727422\
95839719159132982885599292950655526555656046601502354279180469422038870900088670\
47111870693879832241425079104021707776853193201325938617704564973570537352734831\
59116415589180344622346374522507810707305269337140198058480743519237418617752588\
17009755495477870238789688042957649886733406411385347666967135832170464082401751\
97677857886030119834296435094514410447063285546829636796580866046219144995636568\
54676282970931349363731368330698230623986316459260452434432047349649914011966664\
89329086385160373438687893681335479440005342869105266842247066198891087271659057\
30323884679148536734628678460584582404532358436283081337111469448237064022295017\
17090186040785606156605367173788558793273019687997756131660803047136878933098658\
49612324671963424139779952603453681252019636536063445139795002110024861358489399\
43515885683701911008213592593333015802575625218587043147251168883832708367302554\
29906119558006199817028590752161288021467961919778775383677547610814132409237985\
91928839270216988732768259385836375063303044985629050582491285290234563537395833\
99654596904693296083678318215373487889371495891548750788563118515789062283658022\
03491084955465176227557082569197930354114918848757682196857970721205962158257904\
65961151421615454340975903346078669682707071981800663315273449660710338411280135\
03170549067026971100655966583921377141875652217176087597347877575350467002821525\
43218240521619944831265042792137047640681933093840872880757610569044339857228167\
11944276578762170353814981336227138073597534946404335348157154212544013741549408\
79612082442042462357925559335884634116835057450436593648259808470969496981479053\
39862159766161184097845703455361415384359062678976213292525748483171716345182671\
99622628545245947928928596638654470399388372009505420552137879863710781221968316\
39610380952564458201948055009555843728783304067472744345519744942790946663323217\
76423387883633528006199977304233547975700032378243410687033150382560669774916839\
97094116318595676022070203473223222881205019253729654516536710648392012954958742\
98758318098652248058682400706334991470853326573657273043721071111771089079960845\
74830139780347519799945173997467970103874965519926266066828636992596579930678967\
90013159191488591686546140776277422609056892090171416665755371031652978253219650\
74302165060593981469838171517468495345778119241989053182716291726739553247971311\
78629679002288115286733684002052719822236560268907253413324959423041617458327502\
12540838163463622095099080530676840809449517356416205016586899708966210419291008\
77141321577877183859922411109144428263035798155319272858817349181432936009037654\
63827764093932346657744127595096342803179939361370537454917836212445770455684709\
41016664558232149617505672626287095954417695814008737143673154272769844698820142\
72806051289876852066063607274800120192678038452309742218232268875123775693435891\
59374881917142352612084160940324214873632075485167469285321626388162097594200655\
30268053835216454711344111995758649185710479357970354124936745259954799249873465\
08520494662069705794067093125858767231395147699806355825105435445417739503459733\
58010813261059333945650419694647943479475226757669760302364710139079890982397470\
68488214713030185336102619624032988447710447922129838370535997715572577424207449\
24123169728503865556722591760140660809559428679480768562094308416369828013307613\
42393531357010103755877211617391135433650126779499090089109942453180700072419013\
44351852973872991835083444363929051186291568336916516129761768194676932165020637\
88801082954613836366694996754544767293740510350054687749381176672718318998322965\
88733298620918575527121428819143632747130737992440666559050201783586720068555313\
39878710163807259895620744248910635255775598684238055859994044836139595633318488\
843264
m=max(1,ceil((F^2(2F+r)-isqrt(D))/2F^2))=1
(mF+1)(2F^2+(r-m)F+1)=3706256229457317169702887282143309493758013987276072088577\
60765992675300195817701056554914961554375428129462160930447638092843615057539323\
35120894391632354955713062005333510325450739418077202033931532117964755263590313\
34928138366596744899771934457900130200834845007267315184677136779754878212321563\
15227116551584309777867637613375809712330348834541080419037103286601888860091592\
39785465107074475406485022625384193310570885543260877822751033866773998029861751\
33467194196790652834864670994566742455425568589078948447786072992346785367618858\
78019554172599687883902388451436725207894166785346952927961052978794104512976960\
52581068944696069418448123308804236947402534752714445070902722506352541731204978\
34226854312483572109094026392921556672403998415944799124450745430119413490423051\
95823394137480965237271480671271511103697395739249667448663553222083859185980677\
20586984027872789538153503862026059701673320571600975433426461499117968880856188\
36041972431581582128146462471636538050927721847739286074564468872647165369534955\
10073575825565020560483160114093751076862652245879217487095074847316567280493013\
44355015613488710644253459615417119870448069524325884080219961662916417918852562\
39235530436912175763296631350487191346688288701934702148462216980425269172961365\
71512414363782913375445859968287039803718926572848239269227016872323875260036467\
63805645921683745367864371318843503017081369152945346034828429790626070442256154\
26965260819631752917930775031797757254032024251889046717580665465142158102371390\
38705618469588016830632529005651129391827514445568873306734491579088926810203471\
92828117324844994398269878592905433943515717483480928188886393741012175951039938\
82420483929995332018748071400887610336190919176850142424014791325779067201425767\
48308830717283839187338950603033570753803349209538798795616059508354560476541993\
61306044784565998440150633302317082637191254833525162356957134817808182646108931\
64513709673250439311654215641012869247858429413765801627913508329387918598570426\
1385261614605501575587156187773651603865513268335
(mF+1)(2F^2+(r-m)F+1) is greater than n
s is not zero
r^2-8s=1534730915223684342420887321450068152157318203673442325250501487956253469\
81640361953262201725959441911629455849096624030439643935703846034124674169715509\
06370392394001120527768425897589379887610314417753607836487793417549830784260517\
08039008104737486178848695895578911254345631483271282640489003947386406463234951\
93085171740639863237101902158536968094972020835790477917331506862381678582897576\
79491814980366208111184888051104867556421742688397726636511035616651584241885143\
53783507836619407439729230093817814237884366248444014750478341616191515205338569\
71342504965585976367950457900895477293978337733161540322762768521670894610924466\
16910610866341074062952683913301242059638351758110572995452074860367251905605890\
24914372617403090999753461434434607826436572078452163268186308475743276387501110\
41077341310707684859620053241283679363959419429918071869238127503929221325426653\
73271751160952992079437221180234040472394350356126255878076646177281231859967019\
91590257371376822084857330235293305308123761865747298823234703568336788041412590\
06618028185974649168611548867472548903080114764814279244335212395120956040689205\
17298066581723842913488727359695842522918726758767909929454676277231829818693179\
78861318446890006887571813339347607906060634259256459084648983568577268357968904\
9844486563225850374098666540961340289001948600986996011496988313566910720843105
r^2-8s=x^2+y, 0<=y<2x+1
x=391756418610299777998305713935011494865147182189596301440468642374521271172238\
13070139150894570893747998869971572495669888657236622847007787647160331711312850\
17002989851694698583469973621051016713053797473473809836281635725246713187709745\
48063635948903522536302246138297339814700747570628959092296086837981273019418760\
37832019511483544807108599205095469286714860834514946482860299773001921672119157\
05882105490716359396388231472529641223418946059993274584720309092101675420931995\
74655616629265835023023185658436195354735549853254969558384831767731350322551949\
58645221123824792408270939606800986336079250545743323698028560886897444292186970\
79132013332005929201658778616363980692
y=783512837220599555996611427870022989730294364379192602880937284749042542344476\
26140278301789141787495997739943144991339777314473245694015575294320663422625700\
34005979703389397166939947242102033426107594946947619672563271450493426375419490\
96127271897807045072604492276594503153262038227846884570207314521797617969909491\
94831223095122694734091397076604320175501699625491853244008604591352295677691550\
27537409169304844422716731770040048563694814790968092699023223179795402981124964\
39582505082701110425670506331981547032023231644674760121006670321047385640276727\
26293730607799661247840827502403888822780269099258549162435636698527175081579765\
17635978381267081955128120422572044241
r^2-8s is not a square
n is definitely prime
33.828 sec.