Primality Certificate for (6556^2053-1)/6555

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 41.518585% 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.542920%

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 = 2 suffices.

Express N in base F

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

• c₁= 4101884 7979351384 8692292883 0681447332 7358006629 2740166699 1578242681 2392715879 2575574722 3282245680 1351354449 5655125025 1117041205 0962165075 9232870700 2562794970 7896778487 6125450488 0731036878 5977354045 6581898170 2539358642 3041865808 3036109242 9110442266 3450709990 7631874021 9957182208 8121990739 9589553412 4215105922 8599431448 4073797684 9291223096 8714722868 0900083478 9996475595 3610759160 4852145008 7183670855 7816811311 0095929649 8040001250 8367721069 8817374155 8625349607 1131099721 2980124272 0174914519 1552126614 9741656985 4622389669 4696682020 8029230771 4328567868 8029951278 2035769323 6356625743 4821510436 6310536216 6437226359 2247009417 9490009068 4117290728 4682079499 6683451942 8611936779 0907178267 9457658472 6218447073 4922630731 7297873973 1774762984 8771905832 3135413917 9861489452 6646338789 4107116755 3472502780 0042575841 8730213003 6568463258 3193320530 4619827686 7615053430 5211386855 6783662035 3895586967 9825750019 6431534700 3350537241 9077599980 2484181506 3491376936 7039995642 7113988668 9225285525 4061433344 5315783267 2330222598 5870192164 1351250287 2199347798 7386187423 6968163792 5452928181 9342552730 9857501593 4812491480 1779472724 2280712006 3740271384 3267103265 5694857096 8417879075 8562387491 4832160807 6104643203 0526816696 8528615806 3751968323 7953893804 8885388255 8384923114 8397260769 6124091109 8803701623 4839670711 8116211097 2353440838 3875792236 6687947876 6729298439 3552740665 3328931257 2455042767 0320919787 8478215235 0436706305 3050060843 7312158938 8473961556 6061588859 9478039290 4429708242 0773206834 2341520372 8451002746 5961847778 8390621798 3684479420 7047420289 1198755005 1836767060 8540953146 8285927328 1043420633 3686164581 4884161983 7007090555 5411904133 9973177443 9292498816 1517964254 4204668753 1422012521 7483446446 7365825122 5528521919 7410014219 7688570509 1264808660 9615868365 5326709749 1205727055 5197196792 1359568346 6409379594 5309730812 8881675302 2820992039 7932047072 1503567708 2142252814 5520085842 3830568002 3100371649 4064183598 7419541243 8239383947 3759182449 6599516575 2312964554 9117015661 6630608963 1858134026 6150014148 2432808356 3455174354 6391399698 2084164532 0408432725 3745379790 9496907178 0600230788 7393807988 9274509349 5988857424 2250275532 9205486323 6506940253 6417105260 1221935535 7902622079 6717111508 2796315770 8343322603 1046548892 1084850602 2542301511 7476043866 8251966091 4556443860 9941680468 7266710671 4762671385 0699475714 6281232714 8832354909 2810952728 1584207579 4800553593 0108984683 7708353348 5093980737 3126567684 2547625448 1353018585 3701505420 9012717949 3398251123 6282483436 3394758035 5671354818 7218203676 8240284252 8045569202 8936581106 3421986458 7449034881 0473868308 3063488362 6785524824 6264359102 3736399403 8577139800 6125756499 5282438690 8141472802 9134847386 5533718533 9525532367 1079096769
• c₂= 56547927 3493272255 5367543359 6003731093 3873014478 5303743306 0018966329 5079437294 3815824119 9671802723 3333465092 2098026594 4877861219 4538279163 9385953674 9487793678 3439789453 4327891649 9412629037 8538858363 2967370336 6653041906 1685889605 9322734080 3115394437 0996952514 3167937192 1860282387 6282164706 2901548086 8663061898 6739528653 1829699539 0143599486 9813294279 8004446971 6978861488 4871421240 0684458663 6836023310 5172840228 3711962500 3643311323 1729426528 0488354389 8487554520 0805847720 2429458519 3508401688 0763248171 6614624008 3286389166 8866872323 8323581450 4506038671 3305894222 8499253319 8923603236 4842974596 4185356903 8848564760 2839970299 0020488435 7914044555 8327438233 1715730618 3077875072 7604723300 7045847277 6056131669 4063776208 4435530008 3877581792 1927308138 4001450366 1232065279 9708954450 4790797201 7822398630 7951254764 1095623178 4422302505 9937440656 4603708142 9597218719 8768293842 6963612897 2118025929 3184650092 2608535432 6623336403 2054503341 0484557655 4181772081 3231794461 2124986499 4385505142 1132682796 3936036457 2788603993 7032178552 9210629866 4516236615 2083019297 8479086641 9912667461 3756112535 4611853621 0628497221 5287944888 7326170036 8793780723 8530275361 2391320391 9984879864 4079139430 0346855363 7237587232 8353364792 9561081950 6000816751 1973307579 2511836157 1228026491 7395990818 8567644650 8155888441 2222264160 3151475929 8699788312 6006316476 8716020273 7065154841 2905087853 5555970940 0128135589 3369082287 9897285078 0469225085 4769876509 3130027570 6284708507 4619853283 4876217108 6206695876 2911524011 0060817177 7900029419 3458633313 8221637571 9370004668 6925880606 7464553128 7858487716 1308496753 6823580151 1558624692 9590167150 0971123078 6546571007 6712054461 6918946349 6476843158 6358247098 4183505232 6178824909 3136078975 8706462613 7994245345 5238415444 4549909126 3356495828 1982724145 6606962802 4730819921 6218873687 1852763030 0452909863 6890231736 5636981152 2700892411 4353856931 3507832336 6525431569 1716219585 5520578493 7337646454 3989102950 2962390111 9355631311 3256369776 4637013135 2829644940 4712823564 8168451240 9143760139 7571949310 0482169994 8210873862 0309922498 6557514108 2856625794 6213737379 4061565727 5275275963 6197272345 0239369994 1189030628 5860258773 1700237679 6086439375 2475085108 0580224255 5892721796 1636187039 9444642836 2094331310 1159461894 5300187558 7376388544 6703813914 7061538414 5541908561 0304284899 5363403941 8620940226 7288067435 5605822609 2101168261 7446957007 4918434059 7760977668 8664361015 1629584206 4281032537 9779437903 4318971537 4050153698 5481904628 1902018905 9523358456 0423818135 1571575545 0517960429 9915781106 0994980792 6360120314 5603824611 3716826482 0381589950 1315785463 3200251016 9824253103 5158699432 9961053337 0564283117 1896795141 0266036315

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

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