Primality Certificate for (5991^2909-1)/5990

This certificate uses a theorem of Coppersmith and Howgrave-Graham 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 25.881627% factorization of N-1:

We need the product F of all the prime factors from this partial factorization:

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) = 25.881627%

Factorizing N+1

We have the following 0.175324% factorization of N+1:

We need the product G of all the prime factors from this partial factorization.

We set S = (N+1)/G. Note that GCD(G,S)=1 and Log(G)/Log(N) = 0.175324%

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 = 299 suffices.

Finding a Lucas Series

Next, we find a discriminant Δ that is not a perfect square (mod N). We choose a pair of integers P and Q such that P²-4·Q = Δ. Let α and β be the roots of the quadratic f(x) = x²-P·x+Q. With α and β, we build Lucas series U and V. We then verify that U_N+1≡0 (mod N) and, for each prime factor q of G, GCD(U_(N+1)/q,N)=1. In this case, P=20, Q=-29691, Δ=124 suffice.

Pocklington's Theorem

Given such a witness w, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F⁴>N, N can have no more than three prime factors.

Express N in base F

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

• c₁= 894 4588028336 3280276131 4671127107 9315993174 9918070658 2497755793 2783192149 5531918878 9290047189 8924049137 1506520476 6987962069 9069924161 1400349042 1449838513 2788257280 6559869428 3271698690 1498017357 9444808774 7823664807 1677694985 9703785458 7090630915 1629853474 9973521809 5891884499 1309044174 8519418601 7746691981 0015669968 2757392060 4705818953 7785176981 1442239660 9800137956 7033523575 5299188544 9586691655 9173955747 1669132958 6654754347 7310707258 3553078907 3572832444 9357256440 3386163452 9854785725 4342995373 2178985115 6477033010 4847091798 5652468697 7608928076 7927440609 1280471095 3204835118 3278302161 0644806389 8875713572 9806907328 0292955776 5483320326 4510989788 4294744207 7122033717 8621153765 1134376862 5976417190 5517425432 1849854189 0991176882 3317650308 8841482197 2215051449 2681860668 9033787445 1722919316 8057177029 5246362085 0796952534 7227578699 8982774454 6604264575 4982043486 0606354325 7902042576 2383748385 7856514398 2968389932 9461668132 6471318008 1731144621 3062547275 8372993201 0191718550 0244003385 3574183452 8215624514 7734165002 9554431531 2976297484 0627957936 6124620107 2361815685 5979433115 6521240922 5498676579 3468002025 5770430929 0743019307 5235498159 1932584379 6907523396 9334437727 5226248868 0911256373 0052576210 3401040272 2548421580 9307166374 8288785959 9411536112 8411927438 0289605586 2735504456 6715478363 0668729291 0563765347 7729758096 8251020937 6693829160 0169837329 5906625094 8991163172 6388865337 3701676183 7545002544 6728491275 6662948537 9290696865 1312780622 8848738570 7609399637 9987843702 0381749264 0847998000 5525168716 9371953080 0072226063 5136912208 3181110674 5369299204 2587182061 5222508475 4204241409 5061748657 0709319355 9016340811 3210564896 6158321338 2425854271 9115669056 1691178534 4772919024 0007679630 7983668466 3677729777 1727519200 7707584465 9667805412 8529920671 9559089972 6949970080 9042232733 1489241841 9578397111 8613153434 0696045332 5929459322 8194084990 8054540148 7623679325 5063309084 6057963731 9797108507 1296776449 6391684060 6149214965 6859861380 8285572282 8426153927 8900185021 6660745224 5406944287 9730495068 8091813151 3462504559 0288401421 1573837420 0855519940 8022285392 4037015109 3397031572 3842527118 1202774819 3846988053 4912596724 3444860504 1749469463 9986248919 9574947703 2924166025 0326124057 6003459392 4761495172 5999266967 8593599838 5055594510 1532677877 8726424275 5987765824 8981385783 9003172440 0373712819 5185716956 4349552957 4719695150 4960582028 5126040945 0468345518 0759753570 7620760108 0517760963 8465800329 7512704210 3563060034 0722964368 4971952518 6620590838 3756801481 4991661592 2322306442 5146654067 2308481955 4941589072 4039233378 0685492093 5756092943 9095065780 0687329183 1388454580 4884787469 1592442998 6127671031 8776606825 1766689772 6964985389 5709682430 2711546174 1251278461 5455415028 9645509485 4447865629 4282921037 7169344057 8046108857 8205574334 8349818002 1163955730 0109961189 4647335308 9575610213 1998698864 5809014396 4828873138 4249497813 8279377158 4553346083 6719354327 7198062169 6413206809 5183501416 3599448699
• c₂= 618140708 0876523420 6065054922 0950392330 0539932284 2380420177 6949279839 9668432471 7176741377 7094826678 2086774750 3283009855 6262927657 9806696063 2011452805 4214573296 5986925377 1161195213 6661089709 0554508577 5206175871 5953302026 6930095912 9445803711 0016984065 6746894300 4909324123 2567121291 0579114702 9934166084 9458092678 0728271865 3348646644 2306625917 8204162981 5043782132 5878154686 7412650591 3131886802 2304070418 0523565668 4555083042 2155975239 8099099236 4652750193 1018238686 0851911365 9063666998 2172246826 4380535010 3206741328 3116531666 0575678724 9980793557 2658828513 7215328083 2131878876 6967512048 4091605589 5704505138 1992091303 9840451441 5159771211 0601659023 7998600528 0269317502 5110126674 3598443618 1309249210 4996463522 5088867502 6751894331 5015625499 1024055311 7801000956 2429243728 5262328235 9637366064 3140456166 7892670187 9730846870 2545597552 5876593552 6373340261 4288942673 6021800351 9446717598 1001179945 3368428645 2389589578 8807002248 3224793495 6631539588 0421282588 3431353795 0877149189 3502954769 1705347400 1147786574 3209871411 7015158611 5620310237 2048359194 0963201516 6726700595 8939267476 1288725458 0597453205 8905619402 4017462359 2977163094 8744667633 6945956395 1897816341 9692274936 2675967017 6742252076 5352958348 9104431653 2738439273 6744241661 8737773590 2435410757 4849441325 7579058490 3814457030 1033989204 7374278985 8855322542 5551905416 2986097508 2869888412 9214458718 2185874159 3595728240 8223633221 5777156389 0818225634 5758934741 8641742740 9794664191 3454619738 8763107984 9906990469 9392246721 2971562808 6129975304 1573849827 7830206806 5088848986 9203783537 2117610037 3852536175 3645261370 7219121790 9338995899 7326963216 8006030962 5616660841 7808489114 8939126756 1031880800 6531151553 3525625583 5510704549 2417795582 1309491412 1435374531 4712901814 2960505424 2046813586 6789275364 5735702010 7792181527 9037198674 2780806406 0811041110 9752049894 4676702998 0245567186 8899820672 8560670358 5234710203 0940619928 0269420517 5199300701 8857318936 3042276654 8993991244 1472113835 3627146532 4054299452 0950718752 4697428178 8642734684 4313845970 3164372984 0583561329 0223655710 3355348763 4756876767 9412932521 9453987914 2892961873 0615738487 2095896604 6486849361 6064503264 2473070496 5080512607 1764747759 8716988656 4889727533 4341871347 9353597297 1954246301 9566284330 3329228895 8890965859 8853417514 0783516618 7825979527 6669477130 7137444897 3128856932 4150420684 7087922521 1477465764 0235308750 9451949767 7167110190 3303598230 0766961803 6035108094 0783580761 4245363128 5627011238 3273113996 5548071357 2240905329 7898935823 8617306291 9983627820 1745505052 0159227458 3122256110 8672541394 9594819801 5843159816 6908128893 9988569524 8382894071 1718122670 5284126813 7548461710 5058083372 7901165202 2999720459 1220734604 4605556784 8340416629 8388224656 1302079275 5655718674 6355871651 6403508802 9982843337 2930073811 6545433771 4611904942 6433178709 3947044677 5718734673 3646143969 6488050425 0987729446 8551906721 1051373088 0500142504 2235038903 8093719949 7924325827 9130094259 8463666976 0964557550 7722517198 0515096118 6992166015 2511460323 7837027048 9832096480 7273794045 6922890844 3662138738 7529932422 8003931528 4571618894 0218252276 0217878325 9757630683 2073905067 2587922440 8540527191 6956287231 1404448791 8283906669 7396627207 0017319290 7369308959 8931362631 7427661126 6756197964 6970185862 9801105770 8388056797 6353293907 1817626092 4780036616 5528746809 7281008990 3747963170 3072126672 2913442014 4987104563 7985085870 2843278121 2399920764 5851458837 5018036693 1848373115 8855824544 7029106645 5215756148 4735099436 2403955257 1711334338 2006868516 4818437504 6553739254 2364299447 4583361431 6872144341 2633750704 3365228034 8222399594 4200915667 4345805455 0357462385 3294683534 8341140185 8569874902 7869188104 4056185723 2395213955 1195369491 2770798624 5473466548 3479875982 0340141771 4033551467 9870701923 2918053862 7212491170 6833601842 5701726131 4297982065 2160617840 2073982123 6016727895 1197659719 0830824838 6517503946 7720902597 0229048410 3146675566 7281594164 0059502962 6092609548 7587730972 9449910406 9354311896 1892428053 4285654424 7146924712 0156823196 0066789732 6396394433 2364267743 7878085916 5416564554 6019172796 0048960176 4809044042 8482667998 1114787576 1449274040 6147257970 0975708939 7727033323 8837268360 2934630916 5964344310 6069619690 4414231750 5676307671 3496131186 7891617731 3104827265 0916084732 7240849814 9362421032 1922352698 8821439857 1566249397 8948134050 3648288855 2128310511 0479488706 6908289914 2620351292 3738555589 3718942343 3238255139 6101402418 9892832075 7040163633 3899534004 3756264132 6673867766 1080769084 9810802010 4080917905 5445053229 0489886332 5735234172 4746120859 8519321807 9516186762 8384502616 7068524261 0331581659 5164222977 6934368407 4129793989 6463626798 8203790890 3245020605 7948244648 2623795230 7098293789 0499706380 9752234228 6253740022 9277527701 9823049835 7597971055 9814121735 4820555303 1074038973 1522160630 2027917933 3953594542 6083492338 3111177583 2545601665 5369558318 7951067286 9247779192 4507875258 8104844191 7970170163 8921591045 4513335434 2810231460 8442743536 6754801390 2518835594 3319298667 4983376717 4767549759 2483834102 4033293173 5372187965 2564380862 3123954894 7511704116 5015731383 4533697811 5630760085 9430223315 5117878864 1638168999 6329077623 4130241313 0526408789 8243564642 8248224010 8338047577 7287378316 3352535353 0581341467 6369367479 4453519160 3209603410 1862109100 6935620193 9827575569 7792798024 2696729580 5681558251 1052044806 4425592106 7589081933 2584778716 9933899665 4651992312 0400015851 8956829587 0844600242 0472356365 0901629809 2735652197 3912046942 4565381186 1439026218 5246309517 1314993320 4105281334 3802220943 5494198579

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N has exactly two prime factors if and only if c₁²-4·c₂ is a perfect square.

Here, c₁²-4·c₂ is ≡ 13 (mod 64) and therefore cannot be a square and this stage of the proof is passed.

Coppersmith and Howgrave-Graham

We are left with two possibilities for N: either it has exactly three prime factors or it is prime. The non-existence of exactly three factors is demonstrated by the Theorem of Coppersmith and Howgrave-Graham, here performed by a Pari/GP script written by John Renze and David Broadhurst. The input file containing N, F and G and the output certificate are included in this file.