Primality Certificate for (9832^2143-1)/9831

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 39.518752% 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.336555%

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 = 5 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₁= 3 8698022438 0597256125 9746304738 6635602228 3213857712 4035416634 4453573187 0873765739 8505833081 2529309233 9310019325 9765898178 5764563309 8907322561 3230642432 8055717038 0393326127 8125836984 8187119016 6250970977 6708401676 3749350566 5189689879 4151202084 8465765724 2438755363 9163128455 4555036570 2438616998 5254724407 9600325323 6392522431 6997481981 4947052138 9836924443 0555449789 0234075034 1572685398 9267925420 8998719448 5683481877 0318618846 4077058301 3964335558 7711331515 4366290688 4670247701 2575774825 4894366896 3329257414 5955373602 9232605723 3366468671 1938588093 1527531757 1488490701 9951061622 1576046050 5833164565 2667730481 6288453732 9795606351 5864986481 8875702114 0680880684 2863703267 0353333414 6298817322 6365468553 5360276425 2211712558 6032018830 0407491251 4840947919 9410189305 6488201755 7187950314 0845532986 7534735665 1967321571 4748883169 0695813458 9503306328 6234348873 6864476318 3264404287 4817261521 0193075444 3237998541 3462259827 0630214647 9302725484 1007708016 6328922003 2282315720 4827569126 2585238077 8168398500 0267072381 3887133375 3698690210 0760585568 8579116701 5057053097 9001501142 8804314544 1945132850 3623104867 4002031151 5595826999 8521131388 8202862474 5798732269 8699630332 6372472283 8208160101 3461711093 9876333075 8046334976 6762964729 1896172830 6284050405 8705202530 6549446636 8131740085 3573467232 1127110159 1402556027 4511531447 3944285980 9378915624 3765786696 9396534178 6658657174 0112712035 6463437310 7994553123 8737372550 0827658655 3130075952 4832856255 1448154816 2778914349 1440601951 4740352081 1855016412 1765393213 9549288733 9579005967 2773004155 6359871666 0758777735 3736575937 1020487237 7902649306 7311912077 1115643438 9564562658 4151287425 6695949982 5624995533 0192226844 5700744268 8954763343 4569098688 3224766619 6611453881 6756448424 5009025522 5708358746 6724040923 2469975919 6329425995 2387795246 6784133805 2940253308 6687245523 0615616587 5148487137 9578373913 2489668494 0865540894 2932567394 7086931365 3337033991 3613074366 7623597094 8153424975 0073278397 6277579464 0473590236 7701122884 4159733002 0285100158 4094448271 2087056087 5040510791 2693417981 1930078850 2288320110 0547749866 9463220137 5374893045 2709910643 6902741920 2422346864 5242899772 6631166939 5733297294 6556112698 5678792658 2018245448 5318211279 0955302513 7022150102 0270229849 4107250346 3132432859 3796850807 8547113971 2051392734 0307280736 9520466100 5944284127 1397533552 5854294398 2429504904 6311210996 6690324466 9087794912 5727134840 1794292277 7669910610 8950498544 4853158496 9654176495 9598040925 4046256891 4745110322 7018304011 8515917689 3404170401 6280438756 3638064608 4392331047 0628365204 5822975262 7974597493 5613910825 3274933816 7321459608 9487340110 5487753367 0147179788 1054738720 1534011735 7998501002 4428122141 6845812744 5780556914 1472639787 5137836349 8585943653 0882267283 5870446112 0250255422 5666432620 8244407501 9707476373 4868032688 6289489300 2530710245 7705741944 3024202814 7979639650 3105586823 4383199834 8645173388 4010061385 2661146289 8525631162 4592130353 0691391930 1189848543 4966657333
• c₂= 1 5679346959 4566520326 9803934914 8027531737 9489910585 8514705571 3975998204 0479071530 9726375705 7225905174 4690888827 3066025625 3914918878 1843199821 1501362282 7162994280 5438533656 9152098026 5555922071 4832192697 4177834293 7554915247 0106086303 4282519506 7176881695 1839626268 7264973060 9485763471 2276707706 8249875557 3995816753 5970665095 7246963447 0594196478 7369341997 8955858807 5266200606 4584545728 2441141292 3597690138 4584733856 2592190508 1084008784 8671569636 3706055264 9066033905 2916429303 8727165384 2494681484 0064618906 6093807341 9787810880 4589060753 3700501774 6133001105 0169715329 1921875372 1556133827 4834145748 1541115207 2507758823 0589237096 6144659606 8398646187 7415027636 6369734685 2688529807 1721490221 8049495317 5789062962 8261765219 0594017032 2952124618 4368621666 0949449519 0799363450 1818180861 7472396422 8409110971 1620258693 6493570902 4503954089 7859752749 7398270435 4671622042 0643471527 5282142188 8397963892 0137918435 8090305144 5826854365 8795607391 3181512526 7409826976 7426748763 0784196507 7035585181 7078827572 0693372033 8600229445 9366355035 2906251517 0430457365 3373515737 1177913714 8203194574 7689232566 6560734496 8027197981 9656868816 7333216192 2487016734 4804123572 5262286807 8133344086 8997376046 2171198143 3844552967 5033485425 9975058973 4416980364 1294991909 5698943951 1850473647 2293595359 3023819793 1035171024 6298240027 1942926868 2004981127 7443283351 6746137300 3375390387 3643418072 0352243967 0380387145 4718447474 4499149969 1166237836 4291133715 0283497179 7697216818 0511838728 7432050166 5115497983 4574226039 9908243585 5691789658 2138311591 4379218560 3149663987 4263052552 4679476177 4050969510 8861714238 2656740947 1225118331 7099452380 5889960928 4383226777 6237040692 7238826164 6990979607 5421048872 4756696313 9789594368 8749582707 4147284016 7408424546 4546716256 5178179213 2591207988 6979460566 3049962440 1725027950 2219975839 7146308638 4253618715 4877203660 3606625951 2703593073 9995072662 1600884399 5484234835 0526854496 5442820845 2290794476 7750083453 8717077969 6310830496 9250503097 4763603964 1939597068 0781745058 6433979926 9438226207 8142742543 9373378143 6796842649 9482363375 9393453309 3594927282 9458534990 9391563709 8978571145 6256975188 8837629195 9770079981 4030745407 9878481401 1634340593 8095206869 5981103415 1931779619 1860362784 3944517549 8936540528 4775758553 7571739062 2640417791 4129166439 6582895667 0979956562 8163056364 5597883570 8014586159 7812651137 7149342603 0689402789 5877261431 1054530210 3054134626 3541342971 2332339894 3423615215 9818463839 0954487954 2121248320 8556409588 1360946075 0017648618 8692552881 6001527523 3673672374 7222433094 6556175866 9391275198 2237809048 1746735619 9377228982 8070178927 4013074578 0284097660 4940970351 1506412034 8911802013 8128247737 0516754981 2160227871 4763354339 3266992605 5448378817 5923124135 1618012208 7792118107 2612887446 7508031333 2266286718 1459154058 9885515421 4269670467 3573320332 9512935440 6593773042 4966256691 9884329630 5283240111 8901721648 0197065411 9681847983 1372746631 7515147874 3106189414 2660503627 0908191583

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