Primality Certificate for (19979^4933-1)/19978

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.581425% 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.736038%

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 = 7 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₁= 2680357648 4243102304 7203926487 0461063059 9736416096 9369431130 2351298724 8011692338 6462899049 0275981982 6160446003 7444942194 3921127933 7654083362 2481438402 8916661522 7259194038 8778421310 9260568055 0487963468 9858344269 8407792409 3189463158 7043305206 1690644815 4597721519 3253357812 2451897789 5968114582 7407960098 4936055568 3973084999 5148663914 3502236709 2352193852 0084724850 8631417820 8214444661 2022043284 3024769345 0301810911 8486280402 0113493701 5033577358 9961037561 0270399017 3870402104 4956423916 8808561418 5056707086 8523334077 8601756966 2659502826 8359180567 3550675441 2810900537 0336820934 3315225053 3313923521 0921908902 3629540288 1271637939 3518673017 4861643360 6013253707 2174580325 7116060009 9576514889 6722707849 2352837032 4612593801 0750655973 4043000908 7666418602 3284222504 4512016377 3748688872 0854108549 1967802111 8632654220 6857484110 5585189958 6048282410 6514247318 3828137312 6037460174 0447695192 6943217881 6796289844 2592714582 1797645444 8087401443 3438903181 1527520512 6977330416 7839182550 7109130000 7187011612 9617951152 8552965447 6773286177 2449296082 8276949677 8245281648 5955445371 5381464322 6656731747 4280463029 3463299247 4609435156 4094377132 8472704664 2052528342 0069945409 4436412505 0810349063 4034412818 8343245340 8229373720 0909776968 8929385564 3911581931 8459376850 2092425347 6062080566 2225565255 0654044821 1325125832 3692496386 3302761122 3972962196 1253394261 7370498587 1269533457 2226309054 2846899169 6148557372 5872479738 1181308694 9580750748 7902886691 1468029702 1984682808 4289977326 2589923789 5226056359 7981737888 6217603278 0531262804 1629521684 9659470651 0383628997 6786168274 0246213396 6976183515 6848404527 8400303378 9601139676 2247989926 8755167707 8470868584 0360494880 5669153936 7626157779 1022896943 4486028596 5115464533 2710482850 6709864178 7805597653 7095405245 3576991288 3378267727 5393123333 6634674199 1007358715 7733998658 7181452987 3065051487 9971455949 1412298177 6152756926 2227484203 7071721279 4565480167 3854170037 8947108500 5304374231 5535283873 1674662824 0535040299 7261676339 5045181656 1747289865 6355383199 6264918809 3456543758 9877607352 6301248610 9442195230 2355223133 2452212340 3308600190 1898689680 1433727661 7772487803 2780340334 9126207226 3999279128 8393574765 6593367301 3465496637 1207366867 6198265541 6234798948 9233919332 8652838865 8013788978 1405881970 4390748095 5310371979 0179866619 0322904042 6170487688 1198257222 7656182752 5676248634 7462131679 5666794072 9001907060 2135887296 5413856063 7202455626 2738479033 0304674427 8678942211 8521691242 3031711971 8006704764 1772744306 3233433994 2959398935 8014284794 5712167112 6497986249 0548196940 1713774647 5012518876 2595036193 3023004900 4677627537 9350170181 7078212762 1801708426 3671343775 6140470413 1058586528 3048907751 6465075104 2681355680 9522904764 3481641823 5495289604 9242460773 8201920648 0449154178 4072842938 2328252670 7825403465 9723571700 1802933811 0594994300 8121086886 7536390070 2388920389 7569833973 6650270310 9364103409 5563732100 5565390231 4220925192 5432964892 4144355072 0080586004 7426360805 6246060298 9050611654 4826771227 0812593963 8780909908 3182440676 6606520261 7130710065 6622835859 0138143984 5951133588 6050783715 3290456455 6424445555 6775427919 0351049586 4363828286 7297747850 0845115618 5070963771 6648516379 6185380128 6848089039 8105117032 9266002280 9264352566 9429797922 0829198108 5625673944 6348290056 3518594658 9194137775 9881842924 0634643270 7904580011 4145020162 1565972456 4533123333 6396765472 8549039841 5416310038 5733331519 0169665964 0900466735 4133862346 3927414545 3108712187 3750144238 2382886800 3838817908 8929940983 2189480475 1031358389 9504342465 5072141112 0318159229 4049206969 1495118193 6544953286 9822609122 4468957584 2642777597 4943532296 3680445933 4161794390 0014616315 7836289706 3216555553 4219954672 0159366247 9905043282 5992975959 4512230252 8327949312 6999632846 7799305109 1316051530 7424702357 7260140615 5700496500 8926766303 8820111442 4819972975 0922561305 0281691255 2076352934 5062838786 4855950283 2598036574 7346731906 9827320052 8901862062 1569159363 7248308963 5900049079 4216696485 7448386299 1423068613 7789063835 2607661510 1162339732 4057276208 1351820253 2913823906 4509506348 0886737930 5123708798 2552699494 0872724289 7590170650 5861644749 2117739432 2593946954 5442275416 3716744828 3642515847 2959002835 0956103227 9479478556 1279512134 0582097506 5288520240 8175661485 3960702475 1942517126 9074785923 9987883313 3711610094 3097586134 8283368780 1804912394 7528031791 5636736596 6810744080 2517330017 7339369784 7470117595 6869968999 4754298710 1452370699 7522795911 0369385200 8436221543 7890405803 0415864105 4575553143 7186838595 9077581860 3802472836 9950726906 4632168406 1842651150 9547326654 5420324475 6915045126 6336581960 8459379244 7432524866 1123387295 4901318486 3472678470 7220365460 8921116372 4589680396 6897129254 2501107189 3806474545 9472213532 2297911713 9445915221 2738871513 1945003604 7750786786 6198382328 4265444231 4896637635 8795312723 7870100369 3000624497 3728906519 3758364853 9580029944 2992782449 4256438289 2123283825 0500955199 5343389883 1388588949 3307343499 2295750875 7351591613 1084966039 3872907615 5484183822 1140644981 9545024660 5209347356 4375181502 0037338812 8075944924 0100166360 9808162666 7666658546 1891640873 1423884531 0643250516 7056906285 5217273317 0365073844 8589035949 9740542662 6591059275 9172893542 1360728625 7283793771 1080224522 3714763656 0206330789 3402243169 4789888117 8059387629 5236161067 5116223191 0000958823 6758583896 0665812533 5804880991 8825922676 8830540254 0065749873 0716170124 3035906029 0622209049 0290519577 8139603654 0370489765 2407357970 5995284123 3108698364 8893184464 9423922264 3289672263 9109121681 6260608672 0321752492 0308096275 8849493256 9903805858 5395151298 6463246921 3589731984 7902622475 3674338403 9041660737 2395931457 0635376774 8848817076 2348966190 5268031293 6669707448 3179087676 3673469561 9698261154 8800860122 1804632700 2222839504 1870414156 9071961192 3726577758 1050138872 2965403738 6355605227 4449983860 7426096392 3539344622 7530357438 3946328444 7117308917 3587649126 5415070460 1129158804 5093653157 4146306772 1930879755 0830431731 8002484328 3789332560 3093148234 5404636442 7740172812 2539784176 4241003823 6942664301 0113494506 5845892531 9351375652 5408254483 6404201799 1559121168 1534457237 6144198176 3918726675 0942597614 2391873332 2983806631 8751444213 1360143573 7001312178 1471386120 0698077927 3852432928 6957106819 9914074142 1878503054 6802839167 7362641699 1597811696 3434008778 0203833905 8460096317 1827547679 5958962280 4528739846 8311631108 7867437861 2605951181 0186963761 8537900503 6916236600 0204903543 5700514251 6445317373 5852029382 7871405057 2749256788 8617820841 7874058614 2277518195 7363677984 3142481165 4471338876 6267386136 7238232213 6561779392 2717477995 3261424323 9970108049 3856014636 5229935353 0964422721 8035936186 9408511090 3302878517 2376427784 0275552450 2075680971 8513852248 5171332278 8446776473 7282244447 3488981016 0309576453 7634359438 7191457941 5752485734 7659791694 2078197633 6511567766 5662081944 4728852040 4703930412 4664632335 2290019740 8406236908 5033844111 9840173800 5249394072 4176461951 7627883038 5167733054 4180813146 9118896462 4662494493 0964044013 8447023957 5492977848 7333703232 6266453864 4317548970 7885883056 2883944336 4242074718 4944103137 2072979661 2287080595 5156706273 7652687572 3957308518 0007301305 3737613712 2879622890 3460447588 2995548666 3143798999 0261807247 0570552119 3642416515 3754118359 7643793089 2706669487 7396652852 2640505378 5633823014 9085544060 0557505323 1115498933 3636006630 4250457225 3175349905 8999786656 1350810530 2253044239 5440398276 1653114043 9280072096 0084324555 1076734619 7069371577 8867705055 3877270955 0551546539 3846603632 8458162327 5253686960 4093013968 9577704350 0155759354 9826867317 4636606389 2497336879 2969687256 4374564123 4308166057 5544043216 6871175520 3671496966 6813350583 8027612456 5200234074 9517998831 3269518162 0328193758 4986697100 1317890449 0811349877 0210024810 1672084857 6138120652 4603450169 4264545911 4346504870 8470649225 8880686498 5468747689 9690196943 9029183880 4714456206 8492383521 0586705286 2534078871 3083840322 4666374191 0555481064
• c₂= 7 8574909242 2542889657 9331139498 9117656072 8994749904 1553173115 0456312414 4941937519 6892325630 3093138099 3963076231 9776942522 1760262887 0362917605 8651214649 7569423576 6689857910 1518569558 1355063729 8657322629 9028333694 9275903729 2534055340 3014277590 0844410289 7206138585 8734581513 9654159891 8816116646 2252462748 3378104673 2994100334 2749098551 0158139664 2157744686 1412534269 6221719461 1250319818 9976536586 6046503840 5097026279 8230347845 4458603532 2674313135 0084828735 4564483265 1511749897 7517548368 4177011381 6467392301 3828482465 7220068198 2579212698 7967740288 6387640415 4726874354 2002387422 9625655004 6503348301 3044654025 7530014417 5683526734 1193763015 0048847336 3402312517 4086152772 4502429096 0495365656 3258736347 3717354777 8251113045 2277646216 9842632321 7418191523 6185055602 3264993406 1526821657 9632556134 0329957737 8513804757 1663598230 8914083514 0313047578 3443271284 9108091839 0990113322 0024390293 8527558220 8181234197 5889909255 1020964635 4195905312 2571523915 9746011115 6021021625 5215069335 9190947791 7053182687 8949467409 2407345540 7551988859 3484666160 5436990135 0656039682 0413683976 3106093482 3555060925 8922634687 6653878857 8661219025 2039331045 1605315433 6551030728 4223729189 7416401042 1964100207 8140594966 0229737457 8159545037 5639630999 7071886224 0854719312 7038937894 6005896127 0485774429 2483645936 1546380020 4017381859 3848508148 0595625502 2689354073 0658084879 3419251661 0171919926 6857707920 9625169370 0423016598 4058655311 0110497961 6410337166 6378223438 0423138789 6631608449 9268646207 3754746675 5898094062 1146543448 9297098245 6825011614 1921724516 9333155151 1511191080 1769869246 0980810453 4577950148 4329113148 1072694385 1819867087 2156352070 7907797285 6642441393 4505188938 5467037773 0942272303 7752081103 7538136116 8726842510 4053566487 0283411847 8636154276 2628360201 4880005132 3586323477 6773609569 4607309949 6831067914 0746824103 2786561494 4415349948 6518139186 3077231120 8859407288 9107315571 0679503727 2222622884 2485148278 2294848030 3122023302 6950839940 7374706603 2026348012 4311985801 5880798986 8710191475 1815301848 5364516082 3123408538 7682191930 7629337729 6593733542 7510318252 1327324971 0510497431 6898637065 3286119308 9084958144 1856652913 4422390074 5155676397 2182173887 1851299143 0050283179 3546884366 6477043916 0114795853 5088871300 2439162578 8011653278 7178881213 4340752656 0535218611 3628150093 0088701453 3980320853 5452569215 2995004326 4647967887 8259530458 1452673003 5241581750 2306295536 3885946200 7239864626 8076247234 9056518974 3831799893 9375099114 4365901033 2192682007 6193435417 5173181654 9553974154 9952969353 0363836386 3429297287 6684252182 7830864331 8778711004 8104773375 7902530149 7621367445 4769793987 7755546241 6889325446 1303068266 8037587859 6187474951 3192986504 9459163001 2755600013 7850773302 1412714256 4886694134 1905000263 4917219370 8679995592 5410172928 1830382089 7546599521 9119196614 3863840776 1704303894 6264812808 8929920437 4587621965 4287631280 0836701512 5679126095 3480541617 0658977947 0558048946 0148050783 4526335979 0677994201 2613708739 1700710692 8657914466 4871212205 6314567933 0199457975 3545525101 3411412019 4292770520 7644447056 6304528652 1950239596 2803381645 2271843738 4290178784 6943378229 9240203719 0948876720 2097527146 1648315830 2765718309 7559203146 4238252703 5174026567 8095575746 2372362133 6994533448 9040846380 9644812515 4026339774 8092127486 8994037396 2758574131 9259892432 3842451466 1822154342 5283494557 9802015153 9441710825 4370838787 2092462642 1880685217 6644150076 7049347077 1687524617 2340663470 5382511108 0651730552 1678126223 0971833737 8604459422 1354531176 4491318277 7950486193 2451858730 3869718003 3305261970 1856560942 2736290270 3005279616 1451248595 1671640242 2289551157 4691399478 3097834057 4863343448 0018550794 1545529790 6832583681 3235683971 2136855110 9655480645 3026494369 4397785105 4778917267 1662433959 5724187252 9210410167 0993613617 4767486417 3664329070 3105391241 0103890059 4024511534 5640121041 0282197130 7066188817 8246986704 4700180733 8818332992 8920031517 3393461892 8847854115 6418855134 5840492624 4368282526 3453730650 7214729059 2466708378 3576685701 3051360914 2578171177 1999014063 2741575295 2956392433 4419060217 6416747933 6832097760 6740037626 7888014807 0890171663 8601185942 8330900423 7136685282 5465812291 0890692542 8977112060 2868897470 8012812321 1642423920 3624045401 1706944216 0304988427 7850581126 3101953200 6472792293 4394188857 9351900901 8527476840 8558443503 8919460358 8914902939 2938478681 7759566366 4933874618 0353913263 3926757032 0095860641 7928000460 0561477379 2682647358 9645625860 2399297406 9860204703 2159720257 8961837464 8720663956 5871618472 1957370197 3109004888 9429213133 9402303915 9975057147 1137767938 5259785543 8339140403 4547010179 4581836100 5634585375 1103073423 3940839922 5073646931 1729572733 8464121972 2888573269 0029849361 8970890320 8436010226 6554784246 6508717784 4435642279 6591088817 5302178537 3048872996 6901055164 5226831333 2780463940 5965564046 5142736311 4113031783 3401942219 5744504462 1509940945 3296220117 6822046475 5804981602 6027002707 8441786531 4086490576 6011514352 9291346295 2171202809 9213502215 8918976056 9212832642 6541362037 3814109701 3989855831 1370786636 6274222166 9503507205 3519726490 7807619566 8888355704 4015141164 4394992242 4754804016 2442479779 2993634023 3961773489 0281892554 1690244487 6962559477 9294357621 3654750743 7661330817 4072477648 4872015057 7120508792 6784281383 7327309283 2269811653 5587904934 5057736647 7657212066 0319027865 3197756899 5771672771 3243428869 0684941896 9875244487 8660506759 1593155739 0648660941 3934351453 9801713905 4587225796 0885822460 9622118558 4736678950 2079978342 4365490747 1164415403 5718502037 2343108627 6687914432 9405358186 0441627687 6600229285 0290262651 1511049700 3794775586 7828350885 4504221068 1223634626 1500586548 9275348875 6750322694 3055355521 2098891101 1035727330 8365085024 4931263613 0791417785 6706215748 8714413448 5569299633 2317996737 8175727720 5550902886 4093360901 6939919609 4382117723 6098116722 2466857916 6661566244 9149898239 0596448439 9302868164 5375571859 5498219219 8551036030 1288987584 8321785869 0266885361 4892422103 1624133066 4188262434 9218152827 5914422803 8120338268 9774936252 2893764088 5801639692 9394595299 1900487436 3852059579 0889031014 2332982433 8993470809 6908061341 1477558481 6482912378 8779913560 7381588533 8151021010 4138577027 3980144179 1331566283 0228155490 5310284903 8549926531 1855507999 5521640718 8541203390 3366907535 5301630950 9595933779 4117443556 7900702649 2356749216

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