Primality Certificate for (2130^2539-1)/2129

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.341771% 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) = 35.584117%

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 = 3 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₁= 300013 9556867065 0095564191 0594367616 3660627520 6784666362 0993500230 2441007303 4886606526 8462125489 6121207742 8338442649 3168303570 5267862317 4181045190 8183372445 5720886308 9016124406 7042408740 6428977646 8649477810 2033180497 5525445610 6296133263 2546435218 6016529093 7385867080 4820306223 1112475559 5823017884 6725761485 4071504764 9498146740 0458859745 7984115775 6376815625 1389877875 8963119455 4919883167 7743178916 4292841938 0164556317 1959677953 3299287207 3259446487 9709038017 7105404192 4593911081 1525432404 7645847520 5926711537 5569936698 7980835193 6325552339 2813346202 6416721882 8880253828 6467343150 1089526553 7422484310 5111802270 8569792546 0386246997 2711890530 4924643970 5211981635 6776490127 6907239860 3159633732 6150555115 1459780137 9885004104 9514605021 9080181287 7608592664 4868924576 1485389747 2926645411 2111648742 8275649266 9053327567 5836995841 2637703198 1604924420 3455836609 9249961112 8057970913 3203661463 8237805895 3113349791 5902523546 1622824586 1446004065 4895696636 7664028906 0523272666 4351364741 3507339831 1493981971 3725250054 4065635254 8392374163 7965317387 1100984634 9514636913 9481715932 6380856660 7535321630 3263076653 4173119957 8223565702 0933279347 3031351190 2161583152 9716117201 3166911175 1884650248 9303232137 9403399862 2491427278 8404306175 8391810138 4247410990 0592538400 5050947653 6509202310 6195302679 0565977512 9857991965 2151857673 1067748025 1213984797 7198654445 4396907694 3266327053 5776559605 6915546942 2679700377 3146668177 3387052422 2412286297 7632134398 9525192510 8211353230 6655692320 1487039877 6611623226 5633126860 3749138126 7971649062 2963316987 9693289466 5688482006 1371439905 4390905938 9448727471 7068701285 9019733938 7014201552 6170084702 4335412313 4980397391 7310796142 4998671625 2673418177 3668172546 5501865909 6235919183 6074954373 2251772662 3010670490 8885037097 3594162665 6589314028 3515299817 8552617350 8344369905 8496540053 5433351716 7865640258 1738310167 9041475322 5884259291 1922767281 8108195579 3595293428 1450103668 5602078121 5686335818 9747020514 5912131409 3737595602 2249642854 5315569042 6499496334 3162314742 7537905092 4774910709 4019396661 4006914711 9190982637 8909846963 5615314982 0114733660 7776052490 6626032351 7392029255 0544550481 6150593442 2661829502 6843381620 1546731487 0614197356 4555081390 2848401255 4788124060 4658150198 0856189436 0355763684 4345783192 5658283395 1781617581 8699630402 5367329525 3411516103 8824174416 1888670437 1121749316 8067769540 7919258614 3060249810 1337525643 8615110718 7597792754 9715835824 1036917654 0646491406 1224409047 8989986075 6792601996 8092407813 9692520478 1689766250 4560194547 5529924518 5947988433 8764401612 6513573909 8248462983 5548901373 9837664307 7040369159 4430212062 4003581567 6863627831 0154734592 3869853801 9743945853 1768542033 6608692353 1776753034 8764009629 4423203411 8510338280 0732375619 2576125390 7584110834 9086784261 3711240618 1124876369 8424194330 8472194370 4168907608 5201693986 3431144927 8919210311 4475705136 1549407697 1708975919 4583681069 4736267444 3749505188 8377319475 0194042540 3898391682 3072825343 0314354281 0030126071 3863032506 3843607616 0584653600 4650414937 3974534111 2872009565 3572563780 8653188057 8717851488 5270029085 3223299933 5671371899 1857492575
• c₂= 348738 1642100190 7756107893 6276406244 7697939875 4104389511 5464503209 4925537294 3260308989 9614169019 2449320985 5233843131 9119412700 2602752383 1789573369 7410649996 6046158797 3672713542 5476192527 1788275615 2390822065 3335116868 3507939246 2845515319 4716819144 4618111420 0550266411 3044716958 5284715927 5548523427 9651367991 1649507750 4903904645 2121265017 4524198751 3574281378 9284997106 0909778543 0070787049 8534316986 6072317596 2962803178 3661230087 0729976661 8898375827 8312513958 4112365266 5329340956 4257507405 5564797340 7035074253 1623777225 3521702373 9820236134 4375350563 9424215894 2382053631 2343577036 7477916045 3164486861 9187813848 5294981225 0757287871 7403821541 1226794387 2222413668 3293730364 5871911551 1923370642 4097355419 4863224456 4131695851 1717098391 6668001007 8520796621 5993559868 3125532305 8261069286 5841710809 4922453998 1270013881 6973776669 0042854078 9997994881 0836259791 8732349094 0485545615 4863266307 8961098732 0348236142 8475182498 9358372082 0590187736 2316155071 7119923726 4307450083 3738029102 5187626469 0605411751 9509752925 1863751221 3625818260 1124068665 4106883679 3580624493 4905715765 8485831525 7774099363 8016430590 8415243213 8178471237 3263378189 4944196807 7473994755 8336797866 2905096125 4051647023 7734314653 5097348865 5959323932 1899851807 8342222239 2254336822 0603046649 6893374364 9701946692 3039857279 2078614826 2118637237 3973906091 0054740980 2328369559 6066269605 3516229607 8379401882 3579479914 7547899743 8688396737 8063733311 3835871761 3388092826 9731238740 4278882763 3563279240 7574302461 0866549869 0825921985 9958193527 1017016341 6779668361 0220623514 9291465021 1899018488 7133173572 6262981063 7545860048 9816870194 3142316592 1119462230 6178627766 8371159870 2295220980 8671764707 3337581546 3814834256 8898525310 9210718537 0713899990 0770976180 6514062324 4768580964 8561741421 3039220034 0793361586 2185922559 3840808257 2295406466 7336368715 5122653381 4180402320 2833450235 9651723222 8202547683 1197529978 7267482696 3567614980 3368360168 1790777946 9814339175 6259394507 9422636081 3716272921 3097568985 9731307780 9890483843 3799917380 2803149355 3308362559 3523113300 7039215703 0803314657 9705981755 3804893409 2637992880 9224388912 9960305171 1137704174 4775066137 0310625482 0484995460 6579597576 2313023809 0190787892 7055382582 3546887376 5082951234 2123554663 4963402794 1645682280 8039122007 4718236601 7909518787 9185967813 6713689596 9151811743 7321726814 3123831828 3680147500 2081911924 6389866168 0687172803 9967083966 7962615047 7216479512 2299153491 1886838155 5492601746 8485887151 5046052174 2336918603 6273107035 8173401398 8812083903 9819369105

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.