Primality Certificate for (14739^3301-1)/14738

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 37.650344% 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.400980%

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 = 47 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₁= 33177 2369701698 4459272061 0819372875 7824089794 9037769323 1277987219 7601231635 4843779933 8628578328 0035749141 7222706750 6771641048 4755974805 5014037842 1822569131 5521285492 9414825197 3369229488 3940597578 2905254681 9072038369 1525481145 7297323369 4161598976 6652746048 3413356173 8246955980 8391541083 6260491014 8289250690 2633077535 5211071699 3287953594 2808133318 0887046737 2332883312 8281374617 6486846529 2503498868 2748708764 3807026885 5020117695 7252306139 7006287605 0667026651 0189728945 9776714354 6321417406 8051143590 4525885681 8540680974 7871381617 4280711889 7698441601 4092976080 3200590139 6521327227 6131566566 1980686138 9492189390 0827342716 7187119291 3089236811 2660309039 7381626630 8158663968 0631701134 8487917120 6588104683 3583878994 2691485235 2303773719 3829780891 6200961259 8907982386 3457355936 2235747893 1616259727 5357592108 8687693562 3382918225 7883230455 7932506891 1642881416 6153460197 3424594865 0435438454 1964614206 0210135859 8413173460 5478901240 0453753969 8460263604 3985610795 5851944245 6807719622 8849912495 9919382116 8398577424 4644699952 6180179767 0552453494 1988069666 1971837630 1149218442 8792889432 2990355782 9487757409 2826074085 8215411756 3487205516 2236466446 2965554171 0706731747 2545218906 6944168202 7209532351 3419675026 0724692644 5001365635 1272664076 6953686376 8850304260 1480657121 6256767425 7137245603 4374290663 5898479188 9842915860 0532194746 4746455154 2360305246 3507319264 2047301030 5418043600 1178684935 7025371565 6991358705 6116304576 1508098776 1003514127 4631097977 7751658553 9163431609 5520076347 0889738030 0028462463 5136565455 0391814681 8697626206 7058828567 8397992229 4214701653 0549396652 0110504295 5644193278 6523535039 8765068623 6200780692 4339613056 2027175248 8628674356 3961684487 5961312134 4711797125 2645053533 9811086322 7750296911 5918910595 8698542403 3217018417 5674762873 8519404907 2924041005 4759333411 1565414036 5701680894 6988058050 8739818688 4797566259 7390175173 0336877264 9658150183 4931354207 5180400360 3495064389 0802566788 2779077994 1489410022 1843354591 3866119610 4753505393 0244645117 5591169661 2711218770 1362534739 3276429445 9101918141 5509203054 6517829322 1863417433 7394346148 3952248806 5500527803 5981499926 9120316744 8501503345 7041225097 4816501589 5181336008 8766788203 0112532165 0826095403 1290892301 6494572078 1383915000 1455788414 7227327463 1952755615 2404231447 9932913600 3973182872 9825322743 5997502171 6075489323 2406025478 2205910828 8140120377 7062265809 2531445034 3079436911 1200475146 2957860628 2699143401 5688696152 9779247868 4985618152 9642572029 2017791730 2576016656 0309175256 1111106600 4003796681 1990734997 3963671456 8120629721 3006495602 8515853977 4770487176 1322314222 9356469447 7954846805 6223910218 8069933852 5262242481 6560951511 2923755589 2467055912 4324259333 4438173567 3588176589 4527490707 8475428524 0222974719 3701008756 6147036145 5696553719 1851297995 5380707815 2614593986 9829271338 4308611550 9770418450 3982795350 4635983352 3612446034 2328305025 3140205032 1609621047 6351925528 6919784848 9190584386 5375310435 9382112523 5938225537 8953039738 2825359203 6429343213 1703990334 1051819476 3005702721 3309220034 1373793776 6876457438 5218377034 3212592808 6232303110 2602082323 4876859719 2658304121 5007038476 4386701663 4701440409 0748999475 2192558197 0896160697 0473838758 7981193013 6758916158 9891755178 4693600523 3351511863 5408301552 7785842259 2631198998 3216404537 4858732180 5061282811 3997185581 6537766929 1139478250 2640140891 8133588622 0740179272 4394548938 3311462354 8095701062 5777713670 1240355572 5522245234 7070139181 2532204255 7176657417 2614859530 3561766542 8902388205 3199426019 9898151123 0539279022 4324355250 9231670744 3920329850 2879439180 0557490563 7628537333 8739043050 5116205927 1663051769 5144600608 3157257662 7709102378 5724105425 4909803614 8225048400 5940352091 2971088466 0044909404 0625425095 2113251005 5784042456 6887965973 2638968926 7841998764 7994322060 8248084221 2836166839 0261540477 1725144135 1275862516 1279781501 3659018674 7505229700 1112404685 0938616306 0126223250 8372285806 1374047335 7428740745 9781349288 2392264214 5587030968 1528127129 2711943664 5788069632 9908012755 4248680933 7096102038 3544541494 6317988469 5081037643 5768163360 9222312588 5576492001 7747574782 3497360649 5746148874 1787190912 1101470094 0641998360 2554799343 5698230128 6080676682 9144703133 5597612415 8339243802 8727574608 6731781579 0449968743 8605064052 0040534436 7014878145 2349496792 7379845952 7277996991 4205387531 0761792242 5601303852 3597228796 6496346055 0925518972 7591020825 9179291384 1540003685 5766427413 2521288926 3796813453 9338520677 3648691711 5299464444 0815213907 8384040662 5291646987 4244963681 6655098760 1823661457 9784019450 1275358515 1167066361 5229434247 6066660473 1639824525 6675608074 3117069126 9533934575 7775561782 7179104663 5978025976 8804959969 9559158575 7657263721 4618513706 8165436673 8990915070 9005443329 7897128369 3897975527 6236606338 5019117974 2893771048
• c₂= 5058401 1552299450 9492674511 9252129910 4186583454 0411390616 7514607324 1310593131 3896505812 7281745014 5228011598 8446201004 4807867296 6778094087 9101485376 5449740278 2393012957 6286157947 2141756408 5332897359 3359726346 4575525277 8974030922 0574626126 4537008646 7388247197 0492502650 7360079513 5762318389 6228109311 0159230518 7225609021 2483698106 5178812030 7788746431 5771033485 7331567744 3603668923 4790015992 7262381705 0624976899 4731916015 8335227260 7082661275 5001958300 1201299231 2249660750 5069571144 4989363995 0151576935 4336814946 0861757793 5630653953 2342951251 5644934159 9906381796 3876631019 2392845761 5057266435 4105313516 9901986352 3021208819 3839595768 9342644896 9546900170 3821670403 4871652321 9117223762 7158245004 9391545341 9697562113 3065705650 2114906937 0670857025 7341721392 7945181480 1888958713 9975501298 6529420448 7264028205 0946635750 4320397191 8028067544 9227893715 4896315723 0658257801 4199099213 2141608178 4749315079 4396669175 4657458046 4278245330 8628868569 9923444310 5814478556 1775755849 8647052911 1833597094 4428244592 2691631072 3800503001 4673109620 7716334776 7266317143 0475052641 4407847859 9800060309 7109033471 4967219027 9086302668 1252976474 6025580386 0732214163 0448983791 7632903845 1108523655 6328821036 2827884219 7805838433 5723384136 4097727436 9443701157 9632465418 9624118408 4021742735 0115485194 7300315352 8127051550 7349335555 0835880951 7727720059 9364548451 7345389059 5979824145 1449646733 4360373279 1161519472 2874009291 2675324787 2007779144 6594990926 9648507663 7952915443 1302685589 7915909236 5435386574 5967932499 9101309598 6445187495 9865877878 1540641853 3471148385 6195762012 9230900574 2088030920 4486823498 1529844847 7943971738 0666818755 8200461413 3723398505 0422271008 2455703670 2421897930 2504676731 6491231419 5075645463 7197770194 8970941795 1606056768 3919631252 9951400839 2268625795 1618511746 8973761106 0767738350 2725688260 3184364934 8963848546 9165475825 5492860968 4349201222 2393557996 9236608978 2914377054 2624015664 4971728700 5383197085 9257033037 0935681356 6858573437 4612219800 6387809483 7873653151 8527382020 0225074462 6766632776 7612075886 6027399437 5408281225 6735737246 1056852220 8313136259 6516881925 6681574688 2514091786 6647024538 1715677613 6751888295 8631944047 2534919712 1681899427 1988690164 7128691111 1730533298 1527986991 1173188006 3298380944 6858281420 8909063952 5774519239 9297502877 0073401939 5360517175 8522183281 9322026068 9549477195 8840427715 3860987133 1736240773 8779454363 0821445496 6192417240 1751622858 7567545290 4160611090 9006833147 4589356733 6205169315 6201861520 9395634433 1783150055 2147070808 0358177527 1693369292 4491999466 3387207841 2568112964 7363127972 4768994917 6137813300 1551090907 3896780662 6241023490 3397901293 2463406849 8019602130 6680716299 4162877196 5680284406 3863237402 9845684562 7714821184 2149759258 6472402073 6437642718 2977169379 5369760858 6924061065 9177701725 7722465683 1172521633 1660082429 6282799372 3798307931 2434055625 5843418223 8323269318 5893117925 2977142167 9198093568 0928273744 2016664516 8691857866 5335563304 3697184596 0754083782 7972939347 6194916541 4347298232 1172780526 7838635564 1510038864 1458428584 0953454482 8144565865 6450725899 3032209651 3006844743 7892209396 8871879621 3827932764 0784744034 5869607387 0524176532 7154810045 6189402792 8477349443 3286874091 2612789077 0680532265 8228501785 7590800031 5701518897 1977261501 6946771452 7816935051 5827969442 8705708576 7731699745 9623698944 8873107478 9715650381 0728964220 3925693593 4519471339 0012095022 0323677273 5033788045 8981594721 8482406977 6046806757 0524156679 1469830358 4552247600 1451865448 1689627883 6710119004 6826847920 0175649567 0018849793 9104586346 9039732439 6886947997 8745195986 9343274141 9577040385 9394195526 5960017988 5984541069 2625668358 2641789612 0511017186 4399177668 5263707254 6216153696 2178461757 4338538937 1751292329 9026175659 3924999251 2102536019 9990792848 7919162786 7203016810 2576496516 5760456049 8866151103 6605468654 6624794128 8947214968 8559229983 2271781913 1831764484 2857607181 1690967278 1567993193 3795439315 7441874299 2350760396 7170510653 0649923692 4277591798 8944685449 3403196401 6875271706 6664193216 1276304655 6578005405 1269257983 8651487242 6078376588 4109757103 1147130250 1860480310 1175559271 7645378067 3961826141 7286593902 7292050011 6497079512 1294554194 1075948771 1172013659 6761779088 6231519998 2528377946 2442821413 6593257419 8041149337 7305572238 0007160282 3027164596 5403624390 6119225892 4106039741 6866257565 1137860550 6007730038 5231787414 5282408000 4016697583 4243889103 5903060541 6616532933 2585783242 6826493383 0023898253 7475194731 0305542926 6696307792 1743021975 6539604422 8431722702 8289731780 8709859476 6940694856 5198556708 9557863187 4854112846 4561924295 4717913199 9826421527 2425384429 0813978953 8071756468 0541031543 8810286757 7988933727 2868275063 1307857425 6394703060 5124769213 7250683381 0773878141 0154622029 3449226576

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