Primality Certificate for (5273^2857-1)/5272

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 43.120086% 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) = 34.276703%

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.

Express N in base F

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

• c₁= 3578 6259851528 0146448512 0316647317 8568511497 0214360254 9070021507 4462666198 5709587206 5641379075 7852531525 7651025076 0962068508 4290956808 9109990693 5974670962 1967885237 4749968783 9614548879 7385840615 4965615024 6590173982 3454251454 8628463042 5350843483 5093412758 5428760644 6556556579 8293855185 4712769311 0101106284 1368527265 0996862319 1518927979 0586259839 6649421482 7334683619 0077570455 7060531257 8249578176 4321348838 7610936865 3539189033 8176276753 0114687203 7054312561 0787491782 7035147967 8255201126 7906867719 0253222873 9204835276 5330716605 1704775792 2199441068 1953682445 4771626374 2966100205 0073896091 5204526007 5654848798 3374873813 6101466560 9775842410 0501512430 5035251971 1856218487 1264211285 4147727699 0628912338 1749979656 1907891620 7486383904 4999616328 1011029287 1363700451 6572318445 8314405341 9277457111 0888183092 3313986435 9064317764 7566039312 1210495417 8663498253 8142009769 4400778024 7959786558 8806412524 4269281251 9807790347 4112206813 4946261001 3977018943 5059254741 0291166875 6014820405 0984328946 1389625477 4563127902 4399978016 4793128941 1523638324 5902581869 2373231794 8025969328 4354432147 5966375062 4573715658 4191657184 0289340223 5715963437 0842544078 6025039139 6567211197 5697257193 6448862777 5568406122 9573902892 8833745653 9600363107 4469849112 5391438175 6350532315 2526020346 0772075270 4956190336 6234021512 5782333675 8474898078 2212225509 2396591882 1063282276 5963495988 0884566478 4128389027 2299144994 3632691341 3023374970 8251129622 9436595315 7858030138 0915911951 1603430645 3197631368 2623805148 2635468632 3366937213 5364002401 2550296315 2270658750 4720548604 6417994679 4112002735 7509674781 9188241351 6484549753 6501043212 9300066294 9108897684 1412994383 9601569341 8758170168 0913670194 9131914321 2488320923 3037311960 2002191748 9317941580 6076363073 5013898007 1743698915 9240019014 1869694102 5078772611 3619184325 7412816079 8139954625 7253821036 3862259651 5377395974 6060725269 8288402094 3208964081 7169331085 6237126540 1554083562 3400357354 3864548129 0408636005 1852397776 8024244700 8917687392 1540439143 8864074597 8701539245 8634235325 1816823980 3997427718 9126236032 2559174702 3048806374 6782782214 3905155409 8165143975 3452287168 0501900878 8882962200 6014703833 0114577110 7070260146 1008522765 1175798138 0603175300 5258339386 4261818955 7554718102 9204844440 8217064484 7197096111 4385089185 1860740228 4862792680 2859844407 7188734475 3938860235 5635720701 6808684318 4069053847 9137571793 3317270316 1892545591 0981884216 1626279960 7578133480 0166547410 1227523154 5502187128 4898921444 9049459480 7895166882 9109937763 3189929051 9618023906 6571510021 6256239021 8362402635 5783252972 7979346665 3999584687 5175003609 9938901694 2305019254 4493222258 2789446864 8550574367 3427561690 4778655743 6262401464 4985212348 9009050872 8075331532 3344717079 1431346197 5654629337 5759552621 5123016519 9284427104 8119383861 3029968356 7186047510 9559514364 6213433772 6772079535 5753451248 1591822035 4666752782 5523037994 1131233330 7459817783 0853301345 6278013460 2889589432 8346617565 9407581635 3053938712 0617831351 5166322716 7554188031 3358027384 7888156819 2265586317 5455626802 9595954428 5723125621 7215063496 4813881041 6974230947 4941494862 9300495483 1828160337 6094423300 5525679413 5509837679 7894312043 7111686437 6462129992 1049911890 2914215992 3343988367 3371894219 8569802511 3129537767 2702962229 1131620233 5860082368 0714010537 6353057417 8848002438 1609289813 3599149436 0237872854 0104768418 5049134645 0809409985 0781358857 9340578373 1814131890 8015789187 7077037307 6380314666 5233336907 7608131975 6361438241 3560534729 1644411582 7940149178 8413327219 4710364612 8439608109 4259356483 2426907013 3254249176 7555902004 2430789563 3490936060 0280838533 0493984191 0034654270 2986402821 3647982136 6509444073 6538331733 1019687422 0238501300 7637499939 0915668233 1197641159 2972314693 4065603899 5708899907 4717009176 3866186526 7563735449 8431266326
• c₂= 683 8756346368 5394634788 2723316147 7529923783 4371455969 6022816889 3553757587 5302467953 2367815725 8549939713 9803630014 0457077284 7387329047 6352920731 9847433854 5830217335 5456976422 5548051356 6753479793 1880766878 2340527200 6837403447 3884719335 8320961125 6948483709 8667167617 9797604454 7711728645 6055374920 9031523230 8414661760 5378665155 1582622358 8973273519 5727876547 2792760090 4069705662 9681670256 7351260138 0727431141 9617099183 2882767502 0786324116 9753579209 1888442271 3535054310 0293775172 8236985916 4332864149 8337360729 6609142477 7001176749 3193930453 2333017539 2526125181 6914231713 6342249159 9771393610 5518223456 5545407856 7137719280 1171584239 7863736292 3223334957 3902871968 6368813472 9284874788 5279605561 0569945865 6149752495 1666137144 8021349244 7933334310 2590909842 4397741819 0817856540 5772525436 4941769364 6470747056 3595696363 2078453128 8020937911 1008255227 2273573554 5745557811 1615493862 2052381070 5552746325 2030945188 8889682683 2729483667 9474249707 7254651998 9437903823 1085086700 3645001904 1996036801 6428801664 2092987085 4889382274 4118285189 8066323656 3093223825 6514402942 4993316511 8783725792 3115285769 2049419650 0421431027 5372283310 3574218946 8231560374 3912645137 5729291183 1856024748 5016206133 5881966858 4406397635 8151604242 6104327182 5936319183 0585813375 8845114121 7428004462 8174731148 8574128872 7716434846 9165764725 4410049469 5603858790 6794233178 4598041269 8708757092 5628099257 7742881963 2954465134 2520383031 0641385417 6079605418 7841862738 2656227842 8022055845 7307004236 0612071947 1627998359 8612403957 0364974783 2406400795 8174856957 7523439082 8506870023 9188963642 2876569703 7003833616 4010886287 7665174383 1832007263 3495255875 1068797765 0597786861 0726926497 1763324552 7498154656 3318588500 7599080265 1905681401 3055822743 6037729063 9152712663 7524980603 2321501284 3296194627 8311120164 5158008805 8735117395 2801184906 4841165214 5020975951 6344118069 1527838862 8914180959 5606641529 9248243692 8719154683 9578940969 7027812797 4278370987 4378465906 8931613317 8245060508 0391833270 9800288881 3788261249 5283628144 9358406065 6431786635 4937768405 8712545856 5101264206 2283372409 3389026894 7551372901 4139363663 6616126410 3632709521 8608333947 0250527064 0997929180 4604616678 3385560833 3533342820 2339889449 0668026347 1457296225 3365572943 0689309408 3274355298 2690575534 8995654110 7899414771 1069903787 7176032904 2363112715 0909971259 6462700473 2229470792 4911663332 5381899571 8299436967 3471860565 4740919962 4971765881 2030989469 0371406770 1457087471 9966155241 1356037228 5976667804 4648124302 5694233749 3627523149 4240914497 5898094038 8464722397 6462644239 0709090445 0161726743 7655238839 6031039149 6588066359 0222031823 7099833688 5041713429 9075160313 9876559170 2416932803 2082524559 0355957798 4055865979 0249359163 0008398689 7377786115 8241458394 0333599323 6399688754 8456097639 2767594265 6600485237 0696833769 7467319133 0743068392 5224328800 4653627497 3814893074 7883394555 1769906858 7797385609 1121278982 5920972119 9165733675 8967310794 6849360734 1704355881 9751399571 4306861800 9034029322 8018408290 1045372047 7703565428 1369794885 8828109852 1912234792 1454771027 1062908609 0752129498 1619831377 7304251219 2035556674 0085740834 1682119031 2033560923 7942680725 6152259615 1007783562 0317502344 3883573586 6361549172 8182609822 0414564540 1134271421 7547677337 6994527993 3838515761 7938627556 7633350690 2400433154 6456621196 4664810773 3117140288 9054532002 5076428614 0162199718 6042989542 3013152936 6539528826 7140369824 5823982620 4737445615 0828919566 8551470039 1166332796 2247019607 3950233392 3104621798

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