Primality Certificate for (8854^2521-1)/8853

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 33.352599% 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.339979%

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₁= 140379 8382702009 6046758855 4927030928 2892672037 6042309698 3934931760 6932488718 2237206335 3911236764 9655976282 1154289943 1234411774 8353680605 0093710653 8721977987 6129534997 9328778042 2520606078 7397573030 0101911823 0452489831 8526632351 4408094761 4252185140 1853844543 0989909506 6560233384 8569555740 8348309738 0887284164 4320114430 2889547986 7206468702 6035871869 2763997345 9688499968 9808112614 4869638043 0702272213 7362035853 6792953045 1096367938 3786349687 5140141239 1895178102 6799528789 0562241796 5111527770 0813624138 3575656858 1496214143 6040021933 1703939120 6556622990 9706604456 7683220819 4627236491 6413441488 4258419074 2625002218 3542907177 1586819502 6674052061 4007062157 8501549473 5970077867 4679687847 3103411864 4298680311 4442662415 7480191606 5890507192 1270863795 0695499849 3297860899 9986297879 0682996598 8564579863 4702875787 5956945905 2977813711 2257643821 8086298482 6040254922 9412193657 4197206416 0048938338 7674794620 8229584655 9369586786 3477416371 1773354944 4036761294 7622329570 4783421634 4159647829 5468306703 6272539576 0318742028 3085599919 4764478579 1334705690 7307357158 2229102183 3865110154 4724370934 9301207604 3649155840 4431937214 4275741017 3536476355 2619084175 0604944895 2464367019 7865409204 4631657554 5057674185 2956445656 7547495014 1172574014 9007359998 4532832096 9476367561 5372977505 9937789693 5866982954 6077944399 3325319422 9896858872 8333957708 5246534350 9553096483 3315176204 5835853405 8475616664 5873796688 8595510460 0546237932 7405550233 1090790687 4166181494 5631106264 5203299613 4561975380 1319783759 9591808699 7083940706 1076353109 2393082101 2956149708 8594172229 3380714617 9365966321 5188883524 9815898298 8385592996 8348583383 6176908123 4668559506 1677272411 0335536452 4086520984 5707347371 7585676583 9999945570 5631837546 3398747181 1172565803 0565508642 4692715810 1844467345 1463734362 5409082808 0874887280 6098589988 7220355605 1967268769 0555013379 1213624764 7734063230 4056959984 7351191451 9342427956 3224921183 2578473372 1630403348 9887856963 5157753982 6268401601 1063983413 2208936363 8670381448 1281350717 2190547905 9478583941 8353453920 7255545203 3846167355 5650004569 3512111410 3949650131 5725913721 1433970662 9669023835 0635157381 3121830023 3106962522 2075769644 9391518839 8371072257 7941782083 2085436109 7638832454 8066825295 7169055596 3236472859 5795965695 4373466669 4733883146 7539266857 5462446046 5422541222 6401411274 7710467954 7409426741 3438924243 4747452198 8935420807 9145065589 9628195619 9532765027 6818124650 6728341169 5761272993 2688034769 2740887459 0243860864 5293647453 8052549317 8538363140 3968616991 5639710272 9450882618 1477327067 6120972468 6476767046 2040563338 7777791047 8498229036 7596796017 6204127202 4757875941 4523092044 6621541764 2216429088 0350881080 6936287919 5217881734 9422633824 4305923545 9259828964 0455447851 4206666876 6257859025 3745353258 7230516562 7902660405 8105740052 9047985720 0736350970 7421311836 6232194368 4362285405 8566735883 4167229616 2127390900 1182218826 2617172496 4281275032 1808517065 5108359996 2708860674 2856622900 7619798136 0659104409 7907534475 0542282071 7469336167 4649886084 0886902081 2873224087 1271703167 2314995390 5658677673 1174645513 5686174090 9338344515 7767536595 8024913996 7167719751 8938493807 3578419713 5537870965 8329312174 3146204755 6167914376 7436004120 6092458970 9974415120 9287854575 0325510582 9364267794 0126332327 6129014047 1578700473 5533399054 9217848172 3867201619 0586167468 5530082826 6821011694 1119026128 5419725515 0412746136 4954250146 6788012770 0472620841 2329802751 8773795910 2215065590 8141472251
• c₂= 18840 6198032449 7965276061 2740476498 3719750692 1272130871 5626232113 0394537784 2040967687 2034245796 8150225781 3409873374 1657717265 3534301285 8091451830 3217156586 1323773841 6667755847 7416999597 5067484495 1338770110 8707788222 5981444791 9319841251 9493999653 6200508489 6913170339 5602316935 4702008841 4392115691 1397847112 6632167578 1808799330 7833505767 8379585546 3337584994 4552842599 0244301836 1401975804 6269785782 5255345455 3701669522 0185519776 8625420786 5182334240 9766338799 8887369990 5278659033 9929937080 1627180855 9026001809 0923038031 7733886236 8562938975 5864325531 3135087808 1818145064 6640245342 7456403706 1010675530 7759157964 1968812839 1199714623 9018645038 4593654751 7422587929 6874902427 8647123502 7840980512 9544015435 7729032533 1037593247 4704533517 1792636114 4227440527 9661229395 9032256972 7246483862 7300506418 3901687405 3278259110 0276455062 6436421519 4444948843 8397347480 7863880517 9193474132 8163570194 0078532116 3537036575 5713827730 7534895971 7785039457 3362243167 3504579639 9233438201 6032391875 5278658590 7880882561 4134415229 1543889240 3303775058 0670140779 9249342003 3635825042 7289920991 0229155905 3180621346 7752735777 9297529458 4711828207 7087142203 8406785693 8722219452 4858050908 1998425158 5213054203 3068406961 6383162354 8830205194 0526736181 1292524075 4103961017 8730375962 7853072265 6896246571 1727567556 3134493305 7902996675 2184407427 6487179774 9747569097 2974631738 1599326581 7580248100 7113176393 7616867186 0748592691 1268044576 3218705930 3160507688 1151862555 5083995267 4946363457 9595034005 3494461264 8963161360 2777665590 5832052051 8262010383 4353234612 5761626520 8285316261 3208503577 2702132390 1340468912 0475554945 7196260136 3079602138 8845547624 4280869228 5997429676 3750850404 6421025112 6266795649 6739498065 7254523676 3041151538 7421794809 5229201622 7285471054 7907595736 3322277040 6780904378 4992622117 2001488895 6736906788 4748657014 3140065893 5439080205 6321259763 0966552281 8569204016 5949814527 7438238247 2846946070 8503427784 6548153296 1847301522 6382517212 3805669050 8891319438 4544723952 1540109742 9203993619 4707218898 7492855899 8682464834 0591645812 7454891686 3974372463 5505005369 2862607320 7669443143 9229487889 1939845255 3112210245 4789370701 3466723908 3884440925 9837638343 5525396683 3633633442 3327044596 8617112588 2739795116 7223503595 8518640636 6612550646 0726249795 7467810886 6828368250 1751880193 3791418490 5953105528 9905175203 0023787324 6630809297 0540127330 3771434110 1817492105 2709790810 7907527394 7408861221 9573033871 3004176521 8796390740 2818084035 0578954033 8184799362 9718616899 3895873078 7086701067 5519781887 0956784219 0195822637 9749270075 8789363119 7034126645 9901063721 9075192612 2337131692 0782297574 8897913285 9913949045 5086932567 2121319421 0656389791 8885051581 2288769245 9246261262 9797733227 8408168781 7282624541 8216814959 3913322506 1444404864 7033208615 8427317889 5296334573 0259985330 1683738893 4899863426 2467221243 7515834464 3071858664 2170398168 3239191339 9531201690 4748360479 9120223565 5976870040 2479042549 1375170851 2602500625 5167064247 6372763575 1085445486 2202403845 6751766237 3905772030 4522893206 6594325730 4027850408 7557579817 0354350528 5451363965 8648124695 4526498379 2232942090 2756240246 0002350707 8896166685 7763296055 0833108824 5592223714 6126540443 1307008629 4874430842 7739814086 4836055495 7541156653 5366772426 0814764345 4914422672 7381547690 2983469216 3025806066 9608076981 4737783016 5244160231 8944411594 5639870203 9509604661 1482081740 1345105049 1448081297 8120548234 3628138901 4821115490 1449235095 8363301231

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 ≡ 29 (mod 64) and therefore cannot be a square and N is prime.