Primality Certificate for (12432^3301-1)/12431

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.359604% 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.355809%

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₁= 3779876 7555140939 1431873831 2602414943 7793349399 6328509344 0591550935 0665873187 2004050449 2472004668 9742311409 8034411983 1084127037 4368562682 5956386776 1265908234 7489275232 4749997251 7981222489 2704484616 2517179546 8908660380 8529858421 7956358974 6936249880 9838288217 3358412564 2502516197 4662182841 5860007603 9877467973 7813319404 8572388436 3473104960 3212115967 5949519312 2420829071 8382757109 6990977083 3963688104 9547208942 7371931428 3334512335 9030203194 6476623921 9152698115 3418889081 5460123933 9919507907 2297764846 5574370498 7882976695 1196865882 9167048036 7653180896 8786875736 7494163418 6353931108 8730923748 2591464783 7777579796 0088789430 5826347892 8953994183 0614415901 0023643124 2803796522 7620717049 9944725711 5119695225 7384573113 1172298793 7690976387 8479082122 1545015623 3873641214 2297726931 3753348942 3532852679 6472258851 2586030984 0673219409 2325715618 3326238957 6029188575 1801739948 0986703861 1102516191 2799433264 3146498061 1046948293 2522748468 3773082712 4546386942 1099516324 6790033376 8957308422 5941909091 3857807322 7335776758 3527191281 8955502504 0781877364 3711498180 2178549628 0185444360 6995290516 2085385996 9662917202 3715032101 6870715166 0013098069 6307990279 6631298763 1393009393 5118516361 6997575142 4472882936 6556676497 3187221339 0017598479 6432404290 8772641351 7203699527 3487818337 5621491818 0567975531 7116731495 8190775650 2806356111 0514600046 5717040605 3707634476 5340950835 9675772300 7613798406 9076567851 9872812675 9118820754 7437081754 6790658255 8248423185 8473947739 2289382861 9910856798 8157744374 9990497630 1864902438 0678544697 4630731692 7187638448 8098158636 0613265275 4622466852 4815965123 5983112194 5390937265 2313814514 3370622488 7048885644 9874464788 2549041260 0551788055 3994786779 7210989864 3768213659 8376161398 4949908453 0951658058 8428708060 3277167633 3764643308 6730793044 2495799784 9594938850 8973783515 7776567803 4249400779 7501432866 2817340392 9032278531 1546503089 1769271901 4887237354 7508718187 5631778221 6268008499 7918133638 5343519300 7111968067 3669592205 8200254584 3994337318 3967787663 1798441164 7052983558 5294440600 1477636465 3145470118 1308106801 6587799886 7725342397 5118273124 3882178195 6104930007 5854522981 1364284506 2128734207 8048410991 4838575112 5377159826 7225842417 2234390715 1727358373 3422923816 3087072808 9861116445 2957771510 4816526173 8352506233 5058074041 9685228760 9406884691 4540940850 6970059445 7289711714 9264778748 6099965487 0265351234 3966284662 2139985354 6543837984 7017744390 8536681591 7366213988 3723491372 3525742887 2636330200 9236825728 6659571543 2767229574 0785318980 3060978327 9441617289 5723391435 1676174427 3184502861 6290366633 5689144964 8925673823 2288580248 2406346731 0273119747 2053516626 5954081008 5279378268 2414827982 1004224896 2057243037 6855864616 9965877725 0921659988 5687288336 6922799734 1459743454 0364793489 5205018335 2743470569 3572296294 1792703032 4321009108 0896992341 6008641732 2902995425 7141122304 0609162118 0889832749 2616936820 4556493110 1486426186 6767447628 6705767820 3477078427 0058486002 4365455939 7521775969 3525600482 5043639400 0930174138 1590242643 6765774084 3012261197 7666312020 4829716276 5806239338 8243565864 7538156090 0784311677 1977836605 9182474840 8340153219 3045848591 0359611941 7054451551 2337062501 2947332343 6158118981 7533256705 5746707052 3154994166 0462022020 3579268681 3169389657 7558279754 6055694333 9875580363 5129302503 4319604331 4256040776 9536273331 7162818666 6992806818 9734917276 9614049241 3812121225 4682008638 3462181350 8988592847 1745974965 2366998587 5865363250 8365545462 2642989790 3078317883 7409495821 1821420133 5928608497 2963294592 3915153637 2741887361 7614643875 9866244416 1932653791 9790116937 1984791534 9262314830 2511519594 0765911454 3515368888 7885824633 5291362965 3727402177 6605959613 6375434896 6615560484 8209398082 8510649984 2675355730 8624096373 9074911147 0451420726 4815448268 7756790402 6659014513 3834417722 3062248626 3523706512 6631113528 6082448913 5156685471 2704785335 1811719298 6103574375 8322022917 9133608910 8659206226 3690411445 1714924651 0701915469 2582641847 7328579594 3373644636 8472334115 5241500716 8396650397 6392359363 2443873718 8690066354 7053825178 9613683456 5417190906 0055204295 1237963522 1791664825 0929275144 9575549754 6593073645 3676515214 7201448898 2480475016 8743165840 0956974854 6723300344 3609767881 1818731257 1743876705 9080485405 6401275483 6570372144 9449627121 5278857954 2530204930 2944396395 5111430230 1639592348 1282812144 6385885662 9935653980 7924471491 7228960903 0910060933 1259748494 4701786125 0566299763 1315426027 8605775679 2188161379 6427687006 1857197253 6269195969 2170022491 5748960549 2997547888 5098305604 4481208800 3931498192 2763337246 9192554858 2254861390 8161706193 9304197928 1628553435 7712344676 4716725247 0854084877 3187998698 4135007068 4936752785 6208480922 6569040183 4027262335
• c₂= 83410720 0818781691 4724820401 4253298072 8161781647 0728570662 3584859221 0707149845 2788203414 3064066730 7000518543 7863880757 3487436639 4310250381 8802927524 7182771502 5410796125 6664833143 2934732304 1388463266 9646653525 5423442652 9046791901 3311603433 1690395763 0857493526 7917971117 2785332611 9140333514 8922395950 3220823375 4178327287 6885166560 3992892919 4582447153 0396394322 1337129577 9811853501 2599798942 7592306771 8118702742 9207517238 7766345988 1287385916 8035366651 1036466231 6482672382 1588517529 0579078060 6156293292 0075910125 6928055603 2624524081 3437042427 2604277296 0428839698 8854123996 8319170947 6543160602 7968917546 3978242837 4901585466 4372100285 5569546953 7888652323 5333783826 5532402327 3645590756 4574543083 6551227923 0495785524 9318354909 1803032396 8185345875 7678066524 6548258504 4164332089 4926014507 4869290122 9746535358 9475857387 5928195188 5003312224 5096948361 2649649289 9279864283 8256680948 4293126209 1114246064 4307721205 6928999469 6412019217 7322822841 8491260258 9922047584 7913506016 2518849949 5479047930 7042956562 2940203415 7309512136 2585052203 7753125026 2243330875 9986369290 4668336784 5314837779 1932541137 0227788919 2914028048 8707501582 3734356526 5634188555 5646267048 3959282297 9795816652 3209185819 8841307042 1801407816 6550329119 4829692191 9104554366 5187904467 9261412268 6935724282 2015765252 7614527389 3664232470 3836569610 0816126807 8897529484 9752778842 8917501827 5007040792 6810592008 8959671489 7313626166 1673699718 4997550665 2453218807 5193734306 4763303000 9007160613 0526828883 2198757067 8609224399 4944889983 5205945136 5803801708 5280803220 1010077329 9484698835 5192679253 5948399146 0345006983 3439141904 0047797363 5508708988 3581107001 6625908573 9563793257 5010552594 3299213308 0296701480 6569226720 7370961928 0326213173 3403263610 5019528943 5158926211 1453256371 0948772265 7080378547 3023245992 4289107588 4008017569 7946530780 8149118651 6789843895 1938790337 0976767729 7328444749 6684455116 8131195893 3659117454 1192047000 1862833697 9932035956 7531157206 2687864900 6803629953 2318702420 4627703218 5303895201 2891720553 3877463511 4359515500 9415489373 7307115769 6992938506 2674788204 1637354363 0929938909 0423293175 1261431035 7036811810 9568955344 3848509151 4784646522 9583086984 9136565736 9324610601 5702100805 9502071500 3628953221 1389709342 4026131570 4619344843 4564247437 8496724143 8786164499 7129170923 2329834316 9842722737 5450065869 8246067924 8079579697 0560819894 0442251109 3630235070 9900934139 3554348081 5998723217 8133647387 9851696675 1324674222 1698391408 4468775653 6471346772 7556521968 1811097566 4576780949 4866519620 6645394745 2674435536 0396630142 9971250882 6734373072 6449519676 4394580784 0031182901 2280051299 0282897266 0784516123 6237472537 9325234347 7195188188 5193548136 1454703892 7927431931 6030005554 9659103300 6892718238 1775861362 3360216637 3497932214 7398980790 7285418485 4130850408 6579510884 3621953938 2186751054 5785381894 3561611817 7036165154 5281754100 5966575805 8097959405 9011268216 5085912812 6763002024 1922950284 6761246207 8468676918 6875452345 8524317345 9774236935 7389615589 7749182630 2175574165 7700234716 1595439901 3124710740 8014545715 5513992088 1827858973 4285475635 1931402716 1646100908 4531683433 6276079733 8980814325 7316592537 8840344238 7259931707 2444740666 2920873441 8474802308 2492283778 2646874475 4121363238 9396890037 5349833335 4613105257 5945647100 2247002811 6774765942 2250146079 0511833261 7413109156 0305096955 3560912373 7191750009 7954504350 9855068276 9331527022 4794566471 1468008202 9219588628 2614840378 9895108561 1507856848 4378315778 8972383020 7756033681 9506234249 0146620372 3570282554 5956534881 1637464588 0708494416 7815981863 5274253455 2816053396 5081009837 0849845935 7766132249 9875026452 0377354049 8137414287 3417659128 1052796831 5703391618 2357960210 6376821664 8265022679 8393676896 4728601329 3511081334 1827070982 1346804415 4588740897 6895835025 6484510381 4491131658 9573416634 6214396259 0524901128 8799254823 4620450216 6476884600 4781045288 0817624015 6541440084 1398456775 6062004443 8091679227 5121374866 1338688373 5418062083 5076472700 2733284948 8767784408 6988908624 5175239111 3647724124 5019970024 8202374655 6509718604 4733931826 0846999492 0781009585 2769808931 5110864965 9794956283 9053861228 2601902417 1585425455 9512515996 2242008038 0744115873 5584263886 2957556457 8256270220 0253139972 2990806604 2255956849 4998072986 5151315064 9626829011 0692914234 6589208806 1159314555 8902175976 3191034769 1494822922 9063922216 2433837157 2092844323 9703691380 7941068808 0192072157 1737690274 2955944122 8527524909 5661486302 9364984900 7991833863 3577357900 3757408093 7554749567 8136391900 8118455085 0704738093 4202449234 5176358423 2271973590 3056690051 7845395948 1874095453 0657819357 3179675104 3221758346 5453071354 4145246566 0820969867 2140802453 8356809860 4994854720 1239042135

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