Primality Certificate for (9592^2621-1)/9591

This certificate uses a theorem of Coppersmith and Howgrave-Graham to prove an integer N prime by making use of a partial prime factorization of N-1.

Factorizing N-1

As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 26.569464% factorization of N-1:

We need the product F of all the prime factors from this partial factorization:

Note that all prime factors listed above have been proven. As primes of under 250 decimal digits can be verified in a few seconds, proof of their primality is not included here, in order to save space. Larger prime factors can take from hours to months to prove; certificates for all such factors have been PKZIPped into this file.

We set R = (N-1)/F. Note that GCD(F,R)=1 and Log(F)/Log(N) = 26.569464%

Finding a Witness to Primality

Next, we find an integer witness w such that for each prime factor p of N-1, w^(N-1) ≡ 1 mod N and GCD(w^(N-1)/p-1,N) = 1. In this case, w = 21 suffices.

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F⁴>N, N can have no more than three prime factors.

Express N in base F

As F² < N < F³ and N ≡ 1 (mod F), we can let N = c₂·F² + c₁·F + 1.

• c₁= 33 8136599723 1177177519 4519266799 2644598969 6882802273 9688878195 4136805493 2389871052 7922945670 1838476183 9802939365 2708317880 8683329235 6345408404 1362729649 2733522436 3880507757 4344534372 1507086637 0681673495 1875905733 2861212688 3437603749 1574683091 8118433372 0992723835 6966188778 4533999483 6422399623 4045523268 2916194149 6652124827 6642224004 4803451646 3365733674 2538799485 6724412736 2231328468 8859123021 7579957882 7415863596 0079559258 2237944391 6717764256 4889995717 3632756845 9322574288 9904734715 0117664408 5920649282 6870452073 0526054819 8364966545 2895922942 2443410228 2470711188 5728281366 6216464163 7766588276 7561971429 2796559465 6386269527 8258657530 2542400895 1061203232 6372585453 3412071847 7945176065 0688462591 3001660184 0472996516 2080688043 3258630301 0939391269 1127405091 0065862488 4244668871 7025644274 7720074392 5590203307 3989753472 3265010214 0482332269 7558221970 0551345583 2461023694 9074169089 4269243049 3341017162 5686960744 5143672246 5880863346 8886079648 9814218115 1814367240 8147675716 2568646835 5102096283 4231918115 5777851616 6482418712 6212731052 6182673349 6696733536 2200222626 3295011183 7499129048 6326791712 8203575696 1616844332 7025958500 4128115095 5211208666 2857405157 4917715587 7910949182 5292947805 5839648557 1722073556 9150175905 4456859678 7152215740 0483017236 0897800504 9842445493 2525541610 8686181265 4831872663 4787546040 6608566739 1527102798 3157424133 2945930454 3166342635 1512040644 0780222839 6077048219 4469066888 5683954210 7229271835 1507690756 2930029141 0573211897 3925989229 1601815669 2840213814 3470747170 8328695939 0404769617 0789194302 3108405612 5805440922 8633696035 9166179687 9396874005 7647536358 1420607259 1334587668 2092503583 3922472533 5905503271 8088480171 7037324620 9085411230 2694571892 2720280526 6556741354 9996310277 3762423972 3926535031 0590288967 6976221215 5997386628 5021873949 4914300868 9132922241 0210785710 6597815334 4439705980 7118293126 6617099080 8822325087 5600212662 9602498525 9018683820 4936580964 0499642884 4757664217 0025732465 6926041614 1460229715 2391840752 8702255457 2000128258 0130498255 7602653438 5882869553 7671328223 2633002893 4600675234 0532046261 3226764858 9696649426 8300291459 4242928904 7184215636 1492649520 8567665237 3869396786 7433565053 2206602955 4768377988 6369017685 6438822974 8903303960 7312837293 2524952519 5403782769 5797894308 3903096498 3905864088 1023158769 0612972197 9259748140 3896220868 6956184607 6399574256 5060957805 4283750346 7715648220 7486403605 9988966981 7412806232 5369199092 3837595360 7825999127 5076541640 6070075686 8588598432 0282196806 2860952631 0832706641 7622020656 8828752533 5828696224 8778922572 1241763614 2208535484 3983764115 7065273343 6944180781 8194920183 2013920649 6246717499 6804573787 5913266164 7814233470 2299172890 8179778944 8873862562 5884803762 8256239044 1767737531 3678351589 5510408564 5862277974 9528352465 1899813921 8076202055 9362018718 0784119672 9990270027 2651013785 0190011509 3087495626 9627763649 0006496543
• c₂= 674785776 7778430975 3378095913 9477228487 8107859453 8791773496 7867031171 2164153919 7355690357 2453147326 9225433350 9129612642 2092084408 4830467793 7687325414 2567151832 1327617577 3232110058 2552048876 1739399207 3543385947 8131472422 2044717503 0547068707 9613758934 0692563482 6988567628 6727906386 5459084431 2869113775 4777489922 8651238895 8754630309 0585517058 6592531828 0584202624 9420703229 7809131044 4544454066 9940992170 3333999199 0281803950 2402868523 3631070935 7070927047 7156027166 5504379293 0248993807 8545329402 6649803113 9494571944 3069805865 9011962218 0563333196 7804541742 7815705230 4257984120 6374033009 5284135307 0728645785 4768834400 8370476692 8140370044 3286096990 2669055096 0502476650 4147354958 7371281583 9740118043 8612927615 4065683698 8513088071 4379995961 3717841216 6659672895 3808990353 5093615123 1735370324 6769860230 7422853772 0999086059 7887068695 0552096165 7439278572 7734362314 8378692758 7381344757 6791289555 9993066149 3831248706 0060389291 6769113766 1333403670 8749022061 6429120660 9148557542 3864244448 6389014112 0110169333 2193168975 1642284706 8955638160 2576247234 9663602840 8162490400 0847530286 5950937160 9372305534 5246464204 6250470958 4554770551 8885623473 7700968232 5869185485 7182190103 5838747937 7044455591 4354084931 3150940529 7116794180 5125047233 1178635381 5218815174 8316045457 5273334301 6076567732 3248680225 5973734312 6031368561 3337807136 5970592402 2402576641 0862062041 6152820504 0894305052 9607578638 8196605519 0514525927 4915896301 0849312420 0913969248 9642959772 2054277768 5277970004 2314376433 3944489724 4474826382 5193569657 8288745239 9412053901 7527823065 5585651759 0375768325 6710374131 1358027350 3849610160 7097592457 8640049051 0372575935 1104475262 8090262136 4635255854 8217954653 8949741315 9271368695 5180505091 8788487783 0854789646 3240810326 2905135237 2436098042 0977895058 5539421571 2546010309 2724423656 8858358362 4612736168 1227791042 5419273776 2404065607 3053885478 7735826931 8242320367 8881690160 9307157005 2934675274 8203213136 9008032222 0204637010 5540959543 7976785772 5593671714 8230272555 1446969200 8086373804 0084108622 1142200536 1911772001 1578033076 6080992295 3742437939 0611191513 5700062705 6345892336 8515901004 1128941272 1147438241 8934462053 0442418349 5673071291 5037066216 0554090744 6026216578 2168064519 5382560900 9572187264 9980871404 5247516872 2134060178 8404176114 9271418542 4512091375 7960783544 2171932678 9117696904 3247192627 7768569194 6453107200 7980979140 0107612004 7273957870 2612518024 5588531650 8913957206 9444083037 5458046594 5698409627 6895551915 8063001785 5545437494 8848529123 4421111298 7932859606 0065334486 4622127322 3648035324 8922912413 0844158603 7713080602 6369777344 3106094558 2011205114 5316753940 0500227706 2263086301 4687072980 0452385795 1073766289 4560374662 2445768654 5406126319 5695085864 8261245747 8763177112 8288873642 4679623092 0085231690 3809612792 0503673005 5359409868 8108020597 7727309725 5032930127 6525108695 9290535236 1429460303 6840810225 1782205136 5476642829 8125102570 0715011503 9366464983 4672518275 8293877191 0579785648 7008943899 0581711411 1576249570 5225597164 9634667559 7872699685 8247527389 0210162206 1120943829 1449931181 8554562266 6887252242 7480946025 9818375548 0074012649 6663329500 8198641839 6731053891 8015665347 5573886443 8168878650 3282218155 7365351996 4313468602 3153398411 1939116426 1423715236 7264700296 8582205662 0992769436 4221328725 9172354310 3527091883 1752782594 7307229408 5410725021 4523227320 6339357333 0269322366 9941037229 3393474271 7256263051 3516056781 5483395282 6336154215 6409560320 2686848412 5298092454 9985812823 7470672193 3579139074 5388889812 3589961508 7686784723 8843269693 8715613053 5532120891 1280264916 0079249942 3920052710 7485398614 3995885167 2666735299 3297032977 9976931948 9838099272 3517628934 1350552850 1043144229 7668113592 5127479652 9754035259 7138880761 7197116238 9860429216 5252370371 1905597716 9635211854 2051450649 6688647487 5447855488 4187447435 9190977999 3850286323 1869622843 5070914585 3920636075 1839797292 2858187941 3431816073 7380999044 5505081255 3635244242 8031942889 5536089467 6485105111 8298049479 9948865221 9430016653 5181094468 4335665267 5916875850 2170355806 9402190434 5785045026 6982633820 6492150618 0161812683 3047322936 1332751162 2126646263 7463310935 4815744288 9088693064 1259312299 9597493035 5705858911 9835375949 6407358901 0545134820 4465578429 1868508027 7936677041 7301320583 2448589711 8654476495 8802108404 2567184525 9529575323 2797966038 6582858104 1093967748 8599647898 8258865372 2374731894 7263279398 7706400893 8040570169 3083309073 9402607747 8132202773 7906439330 7291597854 3661764706 4275948890 9312116353 9126800099 2975224162 7228108548 0606988524 8517847998 6991052117 0378034716 8600715005 6072028432 4136203592 2691436268 8476999690 1008466982 7526206437 3718119809 6258239276 7608848421 0181228027 7799468675 4910722550 4005751880 4600550003 2730670070 0475501066 0096681048 6569121253 4255277605 4369754405 4359843893 2210098597 3280703413 6839079300 6844377375 4882126612 0799150183 9481812110 2414969830 9125968889 7077392694 9565322279 9542788212 7370788360 9041864822 7235836506 4626508833 3299466073 1768909062 7628106548 2758655800 0723747325 5726481422 4497600651 4259202535 1253974441 1913627018 7315971360 3677746952 0342298564

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N has exactly two prime factors if and only if c₁²-4·c₂ is a perfect square.

Here, c₁²-4·c₂ is ≡ 31 (mod 63) and therefore cannot be a square and this stage of the proof is passed.

Coppersmith and Howgrave-Graham

We are left with two possibilities for N: either it has exactly three prime factors or it is prime. The non-existence of exactly three factors is demonstrated by the Theorem of Coppersmith and Howgrave-Graham, here performed by a Pari/GP script written by John Renze and David Broadhurst. The input file containing N and F and the output certificate are included in this file.