Primality Certificate for (8921^3049-1)/8920

This certificate uses a theorem of Brillhart, Lehmer and Selfridge 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 34.982482% factorization of N-1:

From this partial factorization, we use sufficient of the largest prime factors of N-1 so that their product F is at least N ^1/3 :

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) = 33.367809%

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 = 19 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 two 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₁= 53145763 9464998308 9721410452 1288618021 9248933734 5225136566 3552798594 7005113101 0314266320 1659015738 1725232956 0282017479 5960198072 0687300354 1206139892 9319965934 4749283575 7547264643 7274806501 6677162730 5829645576 5057420316 1405456410 6221012644 7479439405 1655419094 6529852822 3477300427 8940040895 1588327678 7198059988 3134982491 0764414564 2900653307 8515713844 2449870323 0165075393 4030017755 9950644621 1075846647 7271066951 3526393037 7176735365 6402412395 0785333144 1109182381 5717235859 5917368077 7995571223 0997076534 4539643975 4483156612 7884915107 4346611286 1609051491 1896063003 4467607553 1910421632 9961771907 0477108930 3222750324 7773913087 7171039900 8249591350 3344575896 0263512453 2174929275 2627997735 5576796727 8865132933 2738714112 0935729923 5181609280 0441855910 9530312688 8822146178 3942459243 3535174581 1525606640 5629678345 4436323657 7771634899 2525327172 5824956783 7351746537 9111987254 9372282756 7250595052 5567855512 0048567401 2544543097 0001546017 2071384633 8993648670 3751385115 7436406446 4175508868 4148953375 6337203390 5724157927 2238145826 8720394218 2998530266 3351846034 1464320897 2211205485 9011941518 7945466659 9349620806 5904687865 6735094811 3480441336 1860080044 3800431101 9909640347 7232228915 1550976337 5237000267 2763463657 7509285037 4142404008 7406300740 9797517922 3437440561 8628109951 3491241503 8959139134 3861392232 7984545727 3938329523 5177376088 9862073232 8232421260 3389383962 6337455208 3763336675 2091864589 7690772342 9245437428 9382798393 4326436722 9812722009 7683674253 9573912867 5543048606 8239471854 8024306328 8690026734 3897847033 3775170789 4188823177 8765235100 3716228153 2637052157 9468118350 2855523199 2278727950 1571219230 3839930512 4374035899 6163676428 8932691884 4898598565 6402664152 4093812252 7001956263 7352241463 3720431126 2832609916 4171110323 7953952864 7760276181 9713757037 7156343287 1505734446 3935411818 7939331694 8371124200 4612076802 8029086304 5989405926 7309395738 7283502153 3009577964 5178528188 0226447733 0081865433 1488738367 9521301651 7360536706 4546233652 4532335662 2298861684 3617128646 2945211208 3395284122 7449014373 5800246357 4186584162 7663283799 5485369110 9904665790 4073159248 3152669840 4324489932 0375402089 2056996371 4043233307 3602697791 1696977655 9348634657 9952460113 6324302310 3969896688 9379740457 3572262804 5879037653 5443858433 2926130899 8309384721 4604913426 6237242606 0322452424 3940206537 8480078006 6853130416 6092335050 0699706469 6964467784 7596882467 5371416283 3685713707 9689290009 3490312498 2252613562 8588393401 2524127448 4072744332 9508258179 4009778902 3338755781 8977358687 3227199061 3239105815 9576614595 6657625867 8886072990 5829017880 4993567459 5080991384 5548735086 1013117649 8817861797 9064821611 0089838809 3862737925 6935979137 5083513737 8106236497 8801443010 8850892443 0218385402 6607434542 0042584062 8274219848 5139248749 1016341963 5179153413 3326198283 1645408632 0743238547 3674781490 5631071240 8327109393 1310868407 8309862575 1412467017 1826035684 3389898508 0941182328 2754828687 6955050161 9973304552 7835390699 6979548026 8853805020 3013900983 5859915061 9363114672 8665017173 4425846103 5552804955 4348094347 6937900725 5495363494 4069399891 3471975604 4909663454 3632700212 2627397104 0221560665 9315079839 2831216023 4641668924 8553154376 5097149150 2523490233 4632844109 1367345642 4896473493 0252271924 0617366498 9113611818 7927405309 7315953296 4313227144 6419122264 0944040040 9694239574 2732365338 5118271422 5811031253 1002229835 0412929890 2110858244 9629475619 3711687553 3036008614 2632084967 2025563466 9078706898 2198128688 0395400510 2189891093 9223500997 1143895632 8994201872 4941566702 5351971994 5816429202 7816725063 8860093546 0067798258 1325190014 4606126732 8888462241 0467066259 1909914544 0541869768 7275703056 1012458411 9705545606 4161615997 0622708524 8650603089 9600554130 5676076839 6225196191 5087426592 8645090358 6576369338 6162456383 0089044671 4086081723 0780030479 9787871685 3387561567 2742830864 0498579153 2764900399 9297929869 3101523358 2727787147 9294095267 1222198302 2970452293 4267186927 8087212846 9040039833 9888681637 0024340327 7391616357 4121350584 8602189510 4978338709 5359043266 7400616646 9140235132 4140342714 1927922328 4046366685 3369651750 5647917447 8833285900 0714667502 6366539328 5047650235 5394811722 5252237803 4165909614 1104500866 0003169549
• c₂= 207938 0657993426 7432969723 9261228105 0731238322 4635048012 2420458279 1833864715 2951299507 3415970032 4375220640 1967137266 4225720990 8221734772 3658996041 8910919773 0114975553 9995457054 4377777390 9557135243 7773449973 3591953937 4715157938 1155404319 3103335105 1217844365 3462211075 4004507302 3699232986 3767242419 5025703216 4980271954 0773562790 4184098849 2205862552 1049801431 2769303059 0575618263 7838050002 0290890747 1128198873 8572062900 3966260102 0851059964 2030027766 6242695335 6727755527 5886639769 3465171233 0076245776 7028014176 3007650806 8634577768 4908391058 8509039314 5895145439 0113526088 9099473315 6596081534 2262887726 9046644943 9538902783 3181311245 0408191870 1837851740 8715959758 2834662320 5768473525 0688099875 1128256408 5925854475 6227001923 9068173500 4134490163 0525668279 8194378495 7231783965 3135220166 2743435798 0674761128 0960982363 8008943197 5027907396 7423563636 0628810679 2352689157 5075017858 1486533919 2652967458 9315341179 6994636030 3911916885 5317279061 0640136491 7112953012 0745496102 1597826808 0113521548 4557034982 7467565723 7223399150 2525045376 6867148126 1335657877 4369765301 0067765888 3638486749 2333181859 8766409281 5019567322 8955061880 9323851470 0312868736 6362356562 7586427226 9623932572 5129110677 9536042586 9798801534 1364707015 6573077233 0422361445 8703442078 5964349372 8674347331 1286495011 4799522083 7389627135 7031327557 6979828034 1009636407 5409504131 0930288698 4446800169 0776283332 5871914234 3639848036 5441600623 1624160288 5339706400 5524585675 1373382340 3158015430 4502715952 8077478389 6496844231 4121484845 7727458130 3086253195 7237608643 0678973026 1586956724 5168294688 9212332896 1474693187 6616609658 9860516122 0841456658 0706817121 8608801101 6856132145 1960249172 0296923665 9634712582 9611698114 5957534342 8805561507 4998365109 2917527515 7697586615 8736542784 7696896088 7935322918 6292227583 3877070850 0448449271 3901278457 7465330371 8864599430 4088122481 7602379161 5177709732 3161294926 5774785170 5252860271 0967152986 7260067090 5970230000 9835271422 6749584603 7860514910 3080843818 1612080762 0435764981 1676801787 5192452466 9495331078 5068095783 9152522776 2741985928 4324854980 4868956373 7766475121 9732110859 9337179513 0204920128 7565174762 1241631288 9322382738 5182089066 1991372340 6682304608 9225875815 6559252428 0832684796 1020889796 4965789662 6595565911 8134158059 1879126539 3932375940 2053428688 0851340854 5594583770 8268374454 6202368135 8616829592 4013519018 5472905429 7907180240 5783980994 6934934324 3608018126 7645051970 7724147204 9107079278 5673940448 4915737673 0880729851 8027009299 4154776576 1841405202 9002146269 0576993700 1361114428 0063990729 7027336625 1210963041 1564548144 9273855531 8643270737 2911975190 0530380954 1528524949 4937675163 4745493804 5435000431 8874398593 7001730378 2382774806 7277729357 3128155811 0349280857 9394706078 8502417166 8985895890 0948120296 3129545616 8113077865 4767869491 7101856320 9051780491 5462374225 7143794746 9779412977 5503030725 7747971127 1191672152 8533095356 7958153123 2048569331 3628232672 2997046092 9646821430 0701824765 3905727661 9416886503 1329489434 3990833516 7828994973 9750926940 8493541126 2211641741 7492185530 7465230418 5731201099 4010165520 7280768048 8857324939 9346163682 6369813025 0597823152 0733419558 8203434351 7864990948 9433412673 2117055828 7372223718 0892118957 7071446729 7026517560 5474018975 3852424430 4897254698 6052355786 0434030840 8069774667 4816876330 4044584241 3801995152 5816975863 9920024629 2406959801 1641049743 2408034585 7751456958 9168278755 7292603819 5997137982 2263700460 7181731997 4018483543 5975000746 9185424401 0755935578 9849912932 6786815005 7619802084 4823786644 1820919982 6736273346 1900945895 0831501033 0660263565 8289963812 3361400129 3108352145 3753076852 0105483124 6055899085 3895291644 8708276655 9842117275 0306546219 7567227089 4330882401 7137066140 0671467125 7141215872 2587453602 5547541442 8005152715 6106442669 0816563911 8013365912 3491800754 2832885374 7654810214 1872632524 9797077533 9622551445 5194750833 3924386753 7220769671 9722260975 1346129189 7974860809 5279902644 1001401536 4586398703 9029070485 0272199593 8733924501 5423425662 3153966961 0990431047 5559256487 0879288173 4030347135 0377967534 8335973013 7898959246 6468051947 5765683685 2097100068 3158633028 3197879112 7596460814 9429810239 8233299198 9961851367

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square (given 2F³ > N).

Here, c₁²-4·c₂ is ≡ 13 (mod 64) and therefore cannot be a square and N is prime.