Primality Certificate for (10708^3061-1)/10707

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 35.839807% 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.368352%

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 = 2 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₁= 6428 5850933377 4715657612 8892427598 6962799802 0876231626 5043513558 7706493295 5542088904 5016887154 6176375074 0797514693 2224607609 2517667289 0147757686 2231822476 1034334950 2494372543 7471681810 5145792929 5085669959 9028250413 6407976869 6984072332 7005042487 6535302628 0572071868 5319908365 9059305745 8609728515 1652499550 7267341227 1831355232 9004889108 0182568474 2798993209 8191066338 6648372779 4175493888 3304289264 1881464120 6140088811 0480294579 4287849096 2679442086 2383283121 0258143059 4519229339 9862721952 3610977243 4309312404 2214200949 6986384080 7798742524 9967806327 6230522919 8810683877 3533555533 9781147465 4732069200 9134253750 9372945735 3052407303 8967920847 7280596107 1312265661 3477670930 5357361592 1406312056 6364915946 0524258050 3228019514 9190005669 4559300483 5578947024 5987071074 0375985819 0481421668 3514788395 8439469512 7893945018 2246469466 1136164682 8126993983 7828868231 5773666304 1385000017 5089859037 1473754084 2911196882 2391101774 2512574299 3083242897 6960302635 4575940404 4340460707 1777090977 9858951634 0285996199 1727128867 3325774956 4100064709 6867625528 3910179676 7425930065 2579214217 6975668136 6071923322 8483454608 9944054754 0202364942 9358146430 4005346742 3163997021 9312306812 5485858465 4480831397 3271829712 4123038541 4263521119 3366288033 4228793357 2643390561 0251929674 9063832464 0284869062 4160185155 4942450250 0351705872 7636288644 8464308571 5099833551 8915459932 3768492105 3518999850 0326572811 8993907019 8506519662 2356112849 7335644232 8506971693 4146949753 6318731910 6161156832 5312496144 2698755803 6179775162 2211448759 5984874127 3380828542 2422622683 2427748581 3007102201 9782423318 7555602613 8867545667 3174592329 6416476239 8616404846 7324321461 9882825292 5534625602 9603268393 9305302369 8032234592 2268268066 7860308904 9080204611 4443678240 2808219524 4679248832 5472457255 3035289593 9268691655 4167605268 9699997259 9430896543 1102605523 3558077380 0864155186 3548893767 8377231922 0608943690 9956590939 0177936175 3676100199 2224172560 7424988209 3431686394 0356961780 1675345497 1022741779 3344682428 4894941719 7324339937 1319428803 9367689668 5736320233 2404260341 1852205963 6435077124 9993716120 2275522120 1376614082 2973112302 0161632750 8662097865 6954150706 5986820455 9701778763 1328416222 1732485089 0136939373 0667087626 8653147605 4392923704 8189496260 5464866015 3405451376 6304322584 4171847062 8702136308 4429845293 8042999003 5758079301 2529608912 9514624548 1582070406 4099462829 7690133219 1985763911 1551797788 8561369273 5990849193 1309340243 0488053959 4485760428 0274700846 8489837632 3106768273 8608275034 0692176413 8165541928 3432485955 9845066539 0915254128 7146688407 6613984830 7512651964 3207394515 2806817452 0454107528 4076099172 2776818324 9182025405 8421096913 1482960714 2117824061 6147100880 7877620038 3705532228 9296422852 1115039185 6429483651 4509200486 4670193550 1692942743 4952678395 6740937982 1656889923 7638038452 9214234096 4794489987 5661106551 6541722355 9744346216 7367613936 4073771231 9273472503 7960488483 4579046998 5979617847 1420136002 2551384986 2136844940 5198229362 5251703658 9566352238 5416251586 1594489495 6618936584 4870404766 7696031583 0247368430 5093551606 4940944383 9683171637 4654706793 9705729446 1091047038 9960889454 2346583479 3936648663 4501523972 0247932597 3729499058 3634801000 3279509541 0744986856 1279952598 5143828129 6542560159 9016888647 1215261432 0907466498 5471727753 0893987745 7685598776 6089669469 3104485920 4188419011 7606623194 8467620752 9417716597 0234450100 3174891029 6008046123 0081294585 9688295799 7256389587 0095839167 1407295886 9125341979 0859668696 7980121910 5008653372 1261044775 9426423838 5824050606 4881707564 4995252287 3618428540 9967644670 9695267213 3781741753 8331093166 2963138128 6474268442 0902918471 9921003095 8852337413 2068742214 6128981818 1500556563 1258501136 9688611427 2269423346 9426994982 4890568921 7660047665 7808367105 7010729661 3379310382 6329353484 7857163064 3565641375 0347522480 5766267783 7151224482 1400746032 0374569322 2600264580 6377205502 8233880755 9771486909 3980030402 5725159481 2443453693 1842517190 3431855218 4903718723 8120637648 6327513245 2095340491 5583510444 3782931946 6403933919 8356863797 2699023314 5159520955 5020422779 2990927292 1846408097 9355195157 4623717596 5009552694 5682182248 4359443749 4369170627 9450029092 6717761350 3700436965 2607418010 3049870055 8108679595 9867771523 7592823134 3522910071 8185573537 4687127791 2283720404 6040519189
• c₂= 46 3767749918 6738848129 0932670392 7736789123 4237277796 0248146869 6587045304 7753981920 8662577994 4227567179 4562860061 2110968198 4882206713 8617687752 1290559574 0376249957 3431233961 8289307921 8038188854 0498867512 5179418205 4424788939 1783635234 7737519975 1178632065 4048107911 0520118494 5387173688 5432106710 4899444800 8664965900 6365187287 8704854474 6455939010 0723806287 6169674897 9003549785 6542525378 5356457134 6972551507 3439148116 6703699221 6348720107 8566921159 9113140349 1585772696 8489108815 7808805495 5076704485 0267722775 7502832521 0458357245 7969925315 8684827258 3148088317 9574422772 2860592919 9845625918 3562854985 2923639994 5570286558 3958092644 8586896060 5885273119 5094132821 0900508287 2206767435 4313979517 5219327263 0949977617 4762908076 7458207822 1268343240 6132765578 2315423365 3833864498 2476180487 3271055022 9014158271 8354400707 1054055799 0650348629 3315018889 9903286404 0641568330 8721394181 6486614274 0148596204 9441394148 5736418148 9744695908 4095112242 5942236552 6139955915 9894423050 5790887028 9419845077 1826528515 2529835544 2524655308 6533761784 3256849852 7272475246 9038642622 6036705719 7110677276 5885754149 3059456543 8388483365 9387289801 8428248356 4769904344 6037600496 9248291158 4086105228 2095632434 5199442128 0130728123 5286300450 8941048553 6917607910 5483521335 2589912439 3845770815 5782834466 7657635861 0893235216 6852624012 1472727562 4584749822 2151500384 5349368158 1739512643 1230157277 5739621142 4073197451 3089535695 7697220092 3860033872 8748082690 0950522374 9087030715 0072340696 1324539679 1761135845 4549023209 0726984766 0525299728 9892751085 9964744067 9081651557 9190035201 8381603763 7366017738 2617032590 8042686880 3866477527 4845584594 9270895985 2787198392 6192623735 9237255183 7952493436 9273388520 2261517349 5875738306 0341607149 5911113879 8237827527 1744718080 2525120402 6766181343 9593964056 6665873486 8664410585 2397577264 0124937768 0024403223 6871817600 5964901889 1634338605 3494828112 7497481696 1244425293 1081083481 7157709894 9497920436 0866890498 1221535173 8262835919 3083616181 6996963218 5026731841 3303199033 5226633942 2847467706 1367550989 6243508075 8992312801 9979507500 7395082769 5693780648 1435752027 8422695693 0088572967 5694426270 7719428436 4139385054 8881929138 9197738143 5969772861 4072631247 1165354457 2285550685 9542832160 9156942798 0337542524 0083961034 9347068595 2335081716 1333915133 0361233523 5665854700 8300588191 3328216541 3481100581 8163931530 4932602643 9704331116 0037177894 6760070395 7209699018 1169047247 9356377396 5186273399 4967775532 7543572618 2815157023 8076815454 5087416720 0383217217 5525282266 1633666185 8250820336 6740985042 1170370355 3867614861 8189867764 0991435654 3067832666 6947612522 4237440123 7018113745 1010159034 6042458298 8226631027 3452346927 6888716633 0888267672 8429882459 4251224468 8196856320 2817720758 8866755994 4362981817 8015070910 8354686523 4585033194 9353112104 4133837607 1074569917 1603677120 5730370234 4395635522 8415739281 8181853612 2516146866 0854643658 9017792247 6940617523 6597555500 0505906020 9691971009 0750959006 2208657296 0906039234 2830052172 9961979538 1915130573 9229740362 5195723358 7479060844 5240109036 8764418022 6787396683 0555215962 7088346695 2599331190 0129290942 6658160340 3787276295 1759397168 5979019359 6972093559 2117671200 4075909028 7294637725 1955043837 9652462703 3153252347 6197749698 2649259438 6767578679 7135509139 9356844353 9890351563 8206173581 0811065960 6656830869 6429062762 2327235700 5294632623 9269649440 8572625625 7780834048 5603209796 3618875992 7646977545 2706039040 1429442198 4093564288 0812517012 7041075928 4994759182 3099985006 4712963963 4754543998 7194963336 3754538902 0531460309 0649385668 9374155171 3478511951 8864360211 4626299766 1671435711 9611660686 0301886305 7273743042 8036548902 6290650316 4758268004 7634331251 1985811259 6161963620 3788847767 8725511088 2213358756 7430498271 6914899404 9907943139 5474280540 7268666152 0465931635 1852242878 4503801492 5959276046 0358146423 5273590556 9315297143 4990525455 2692534324 7895733883 9181639526 7860764509 6987311320 2666529971 7821416660 3269753805 7077983997 5730045935 9367634314 1219043007 0277152971 4739775195 1630427196 7575177407 0891176224 1030611137 5750502227 1190438931 4346908313 8647491099 1336959760 1152331781 3533178235 8458916778 3375496784 6307836345 1208601332 6216292656 1486838398 2400315270 4961633190 9648519731 4787042424 3026860508 2349942894 0400353272 9173415069

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