Table of contents

  1. Abstract
  2. Proof

1. Abstract

Primality of (2·10875+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\
666666666666666666666666666666666666666666666666666666666666666666666666667
2
3
41
71
239
271
751
4649
21401
25601
123551
1797655751
182521213001
176144543406001
102598800232111471
18525843918490695886751
991474271662986957800680951
3001275790282832720932976241751
54442267778748734853078961420361450411594669214709944589849727424959801
42051775804956304559810859008305819975199677041099230574273451704628125001
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\
66666666666666666666666666666666666666666666666666666666666666666666666666667
f[0]=2
f[1]=3
f[2]=41
f[3]=71
f[4]=239
f[5]=271
f[6]=751
f[7]=4649
f[8]=21401
f[9]=25601
f[10]=123551
f[11]=1797655751
f[12]=182521213001
f[13]=176144543406001
f[14]=102598800232111471
f[15]=18525843918490695886751
f[16]=991474271662986957800680951
f[17]=3001275790282832720932976241751
f[18]=54442267778748734853078961420361450411594669214709944589849727424959801
f[19]=42051775804956304559810859008305819975199677041099230574273451704628125001
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 probably 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=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]
n-1=F*R
F=200085052685522181395531769458571935218884806219843612523860188555147288651027\
91905268552218139553176945857193521888480621984161167333333333333333333333333333\
33333333333333333133248280647811151937801563874761398114448527113489720809473144\
77818604468230541428064781115193780156387476139811444852711349172166
R=333191639114832063506244346805297978789502130973896948425439525032353350477950\
36815933282883560775617902460981907596598846376535323821001075514377618039003943\
28738928367040893488195866846468734145724494314072298298691835089677471573174745\
54731258275983793606634614367174249808305488660675218815288009513292546343987475\
80056235085532687495878939247797929962998393232736769414582760171110555517129143\
32147411952195857813020781784778669532739906996701343402223706451960326556371541\
55908671341167626032891435630079198197164714886974976190381419267364906616551227\
438451195751
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)=n
5^(n-1)=1 (mod n)
gcd(5^((n-1)/f[1])-1,n)=n
7^(n-1)=1 (mod n)
gcd(7^((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
R=2Fs+r, 1<=r<2F
s=832625012820213659339862630766390721852144198752133547558978684895870184291318\
19561149767280495857241013969981189846735325048675032385300170737940563295904576\
44047265074328230629136436895870375283696097723903703029296908434644359996735497\
59451701651664961682981277
r=376242375842783246016217437962569087364283641960541419994838805959178842886590\
27269028783033688674025557728986669505232437298783059206895894118136229157796141\
05563609092100636781489350926826927332817337778121670225891812097933246443670498\
25639211144345443734549943293006061927244057303370925536388796123787
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)))=966147869209534841611458792713325131928703529271\
11759079098346450439187261095932180651596958797268086830820178762972520824653729\
65888234746817938636985555296797502678600245792471941870916759967785830717246300\
27418014527554030463997098775590588450743329625280180489192635226237708286807441\
06982109538077489533405042534417077107798580453192294752961170148629411862708590\
65586241871179618599484347708216950336451678917377161801458577557737739230739436\
78482722748109857456253975965681829592666418965675187554240887067778871700303095\
23339239434447187779539509473501961844463815526643899820224099421676206308112735\
73992367678079113364193557171376712187258866285125784520275266098271161458700037\
47768839928281324072595355029420137021123375726081989677917189048005124120719305\
01944483256562866833702155021349289487846494328938450436199687752637654715809466\
55286835094058096754872924024806609157039670534962621101723545373451911609004843\
74444091702470023413901280833029109233399302567893748497702199038259477253083978\
27244529483585634894558198058364161031240327709494055674109408203054592536920257\
61431971070382354530336254484296011254047764043211525122720434879738667770483150\
83624327174560077290093331356133861519532881450928156198062180929007889714848733\
57118957996440281238983595691656023938115600290281508777321514679871804422443590\
19815741257121362940605961390275092459623974982991314177172699850444068454760561\
02522013061883117376845105129681437705262823931107951231626910942752195860421422\
17426109631450158849416839590464471234289011491476725027061471419151685432350952\
55597752688039836726103415205856072681362081088108858630731622995484964831520995\
09422804429376858736216466554441133255038335154648659055627363433116294326366339\
66362861701436160893665414268135322552382397926512090351060422254328332399529138\
8831532738088097869888384
m=max(1,ceil((F^2(2F+r)-isqrt(D))/2F^2))=1
(mF+1)(2F^2+(r-m)F+1)=3108291925172947525043787044023299061992596907910120953441\
75531053048554932974418212031965544731711861591852323824147287112912810654064171\
56358152573338960133461672231183001616927053836042389276111533313190675045533636\
74312378382895220584931098659196813155400566974692755626340354096607988297396010\
39044035761694700785886061134018878922374436059693113862838251250621021953779474\
79593666303975492496369222198913505837754626885188128330625074990711612218000684\
18762226084478421265608938924590712031469444913165316184452805642436061525485820\
66259086029784132010856731173451128300247762031331541222771129508826511143285983\
60527131879115472771621919617097434635433620313007890806574498720976041083699851\
52526098152679473924497521964231499960638199024605273385132992379970208721188848\
80487896603212152911159459554548618240860925484307987792676572469372422840942434\
65706112958514463811264230825197367438871601768831438907363
(mF+1)(2F^2+(r-m)F+1) is greater than n
s is not zero
r^2-8s=1415583253798221658929854745165363950790993444400944017533698638904514944\
24889675564615601996772705500734438706862198597664853955583270795337034427870922\
42194104962845232851567130164191524588407687085992149192545076400734720966071785\
78075907621284780979408509732970114609740561524179813227642394270770325697743811\
22932522217501522726772961354565186388367315565626441588976964280234552991422163\
91092041433534224780097575448689639049713936480807364066244044035402215928218935\
22309249193626609027338306998050817074417393449489823454983820948150775375526271\
16611091497327506094413154031536774680379862216102763371153
r^2-8s=x^2+y, 0<=y<2x+1
x=376242375842783246016217437962569087364283641960541419994838805959178842886590\
27269028783033688674025557728986669505232437298783059206895894118136229157796141\
05563609092100636781489350926826927332817337778121670225891812097933246443670498\
25639211144345443734549943293006061927244057303370925536388796123786
y=752484751685566492032434875925138174728560622920980278280402893017311554647405\
72822698564360539300868167541277191577410318108367980169824930308160698466073508\
22867179244175365322842111501203217941973523178122745825938591104371325924338726\
94400243165728464031573138870524126466090038993128637753084128397357
r^2-8s is not a square
n is definitely prime
2.672 sec.