Primality Certificate for (11581^2677-1)/11580

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 34.377275% 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.366104%

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₁= 246234973 4578244821 5215910395 7388694556 1706372254 8417948341 5878484598 1276575150 1074522779 4467991801 6687419246 3125340353 7193286653 0675229493 7446525945 4598087974 0826009636 9116480698 4007596311 9772323011 3940042803 1227381514 3790631230 3124934462 3966494822 4683794980 1143912460 3356557268 6289778634 4590225092 1726002936 7368043679 0576921687 1396264030 4534998780 3456959153 3181980105 8537283829 7975064349 2962433519 1522074083 7038083148 1024769456 9006420079 9785949116 5924872084 9486140050 4123153717 9493062103 6812573045 6380208728 2312904235 2400101795 9085732542 5150537320 0176104407 4003782962 9271791332 3009807470 1309354972 0664223813 9457600945 5303311325 7206971050 6098222641 2274465553 9704268914 8788618034 7264578227 8301468423 7061599483 7250556823 8381427610 6276246592 1363595429 7635707885 1780421927 2304025281 9656891919 2443197193 7527303521 7744045987 5237674337 9954687924 0151346572 3305553339 9256184301 5975747966 2469140647 5001378014 2191240620 2095016584 4576421879 1726882596 7019686612 1685637809 1920425180 6357707134 5259372308 6549385906 9842427142 3074181556 0378227709 9521053985 8264490235 8629439205 4415374827 4589191860 1429854747 2221462817 4512197443 3640268383 1140988726 1619677016 8826094743 9426687643 7149211693 8338807460 6882628874 8475629260 8214264754 5762181251 2184050834 5133037625 5821450297 6226703164 1679184495 0125914027 0495133486 5605998728 0736830878 9826369542 4324496893 8572357598 7100190108 8779405146 9760666139 3258521910 9537511158 8642902426 2608389807 9557842407 2242554331 9638273592 9524023878 8610757301 1805392426 8112889266 3902030086 9082146211 5909607705 7674831375 0861653516 5035871617 8906447477 2874985897 1208323526 4898221722 2190017709 5538630779 6782274146 4722631998 7414122795 5675195901 3552312777 5618717902 6938239917 8234154703 4083514880 6815940350 9028726758 9147981664 3791213457 9203676769 4678601589 2444999534 9337252025 7432690518 1896571989 2954194529 6527286867 3613714592 4585313746 7398813673 8702274648 1073103346 4816973984 2832246503 2604866001 2656831457 5972465623 6025684392 0419602957 0511393596 6725573286 7861720056 9869567708 9640368375 0620789367 7721353779 1592114602 0786515579 6290218702 9765262099 5110893121 7896693401 1760010013 0753811584 9440585156 7646489897 0477445722 2450118199 1256427243 6205084465 5141284993 2555505016 2302216560 2781250161 2296892509 2043884040 7477716554 1101949994 4115812720 4927624915 0121671454 8180552475 8436488092 3765683016 7854835408 4859184807 9535614769 7279208745 9162033430 5162526065 1274533236 7005406659 6162299681 6288533981 4185757212 5494474719 6923043858 6167750105 7733204603 8356116343 1123282102 0849862327 3033622546 6382087842 9216383572 5919154069 1908652235 0596968745 4945475701 0758111714 9568598125 1440034286 7084949470 6372965036 1655538306 4315822209 5204985959 7777436990 8891805064 1631529707 6028137884 5375071156 0126870333 0634435402 1585296007 4874982970 4425863864 3291823090 5659953444 2630237923 8610050930 4011576985 7519891945 1870980130 3350240197 7280151761 8175564566 9472243583 5593878250 2444141787 4938768299 5983981612 2770034754 9501083026 6679666936 1769665266 7171837487 7222762294 8701509680 7816595594 0275022434 1876168559 8817231459 1530956941 9340319605 1739050959 8605505845 4524643919 2862919251 1201597423 4280639882 2336759040 2958482129 6979713051 6826439360 0622226688 4768647023 4072494373 3618745838 2402068577 7393290715 8671087867 0376365795 7621888939 0850060181 2264409852 3174726282 2631802499 0490288184 8451763513 0084346015 9325060032 4151180736 1962835214 4261168844 9055763610 8049564405 6413807426 1458872440 8131989532 2968193654 6293190162 0931660699 0316658798 1450914259 5359490937 4821780244 3031165134 6977907180 6214872023 0751352527 0684008258 3081507105 5098439379 9006332922 0550483706 2818376400 7800560549 4586183564 5355069546 9947882048 5978856903 3483659699 5074369880 1159276597 9551016463 6256972393 6946970225 9377760752
• c₂= 54217119 8198580791 7630945361 9729770868 6927163598 3641489192 5639395471 3856110973 0964584830 4840671652 6193992717 1213602456 9463873067 7221660364 8925526624 7290789360 5923940491 6807135208 7770575567 6673255066 5827873283 4488432285 2191290380 8798068127 6221176914 9033412449 1746678510 2683743333 6885277249 7383592725 8326082120 6389765065 7487714848 0718368711 1028102847 7065519601 2644249306 6026851241 2699445773 7400833223 3752795285 3479404223 1109000899 8427043939 5882186259 3844604219 8799180383 0265686753 8094213047 8118550155 1102634399 1033652629 9156792368 3570296435 7513016935 9336188946 8630492815 4494429624 1081045626 3087450507 7471296729 4719995204 5359446796 3690888243 3313996482 3295265109 7526304771 9556179410 3227705594 2409076054 9864985802 6846399971 9877015070 5924822560 1958345030 3312817650 9400455848 0261688650 6645988182 1354079325 6190070024 1691772721 3965834684 9591740402 4864894400 9840428556 5796024220 3165092042 2157496127 0368483731 4715623371 6268007894 0136314315 5074202318 1736842799 1122052188 2115298009 7785247964 1633488566 2558483150 1693786198 2753920167 5202707484 3649281380 6312015835 6873821567 1298371320 8482443500 3135767841 2102126074 8000463461 4672464061 3156292678 1111763093 0507002443 0437630451 5282885545 5685695765 3160069737 4303226544 1950428383 0329635202 1204641803 5035578505 1668283852 0872831073 3682448897 2241819479 5141341868 7909406217 9581975261 0648769640 9742709849 0325518503 7858282948 4105177169 7454377589 9535826057 5999999464 2096060825 7066411332 5907838911 5332366808 2168436045 3845049604 3423856210 6771213527 2188901196 0459158062 5155673398 3991291299 2813669395 3600853437 0832253578 2334999183 9230504745 4859739611 2391333943 8680725656 1590155341 9041087576 6204995517 6326647579 8703052636 5651413569 9061487106 2624000152 1690488513 3882460601 9530293501 6809146373 5175402831 7638204533 2131819808 5848927436 8506930016 5118671559 4000082115 0501321204 4154126469 0014269704 8090795199 7486952835 6696278861 6560317050 7398897543 7682678401 0178183380 0133586517 5993280668 7336200018 2287262794 9302831364 5977743315 7912735144 9937164597 5145450123 1555635425 8277181371 2463284503 0204903319 3806778048 9697840177 4705700012 6400542812 1101326337 3335964641 4040552258 4873800046 8916560991 7637802920 1256638042 3109060034 0778022810 1832055596 6097932997 2168042535 6039287515 8661492587 6303991971 1088077790 8054638884 9212498291 1782418848 6947189945 8068253963 9679004889 7263577175 8744732332 4460909814 4046707602 6846763139 6573112435 4262123123 9142458857 6971421042 9956210443 4210180395 7164077758 1051144544 9952956620 6667150714 4873602139 1117810305 4885790754 6082707552 2856347005 3895562790 4043844038 3019047290 0647730049 6415399395 7853550831 6415606304 8240127155 3518726934 3603422382 4239030252 5571963294 7961067994 0135686385 2894948301 1346047205 3190525487 0756657092 5166597735 2661026415 5232851944 0081407008 1375763744 9525517825 7962009062 6234314464 1688724657 1980738694 0881224740 0563174025 9927519148 2548298384 6976409763 1099548565 6523347336 2946043338 8104606747 1482882401 7895549848 9022268324 8022696928 2117821653 5811096187 5483534616 6756277134 6931186574 6651796569 4049962056 9956479704 1599462031 1705954222 3266115480 8383263821 1436585753 9578711557 4611252579 7482078595 4305504213 8772161047 4954545770 9338786352 4703591639 2997620284 0018078835 0486918868 7735428080 4042026740 0706614061 7041290759 9064145476 3092620912 5362402596 7080512206 8537737973 1414396037 7734070817 5414483345 0164422511 3229324506 1441441807 3465708710 0717470729 9246819801 3862734264 8765339420 0919719187 2280104553 4026150102 2787310453 8789993271 4427805274 8786421788 1101951220 4672711123 7891781050 4491734407 4135286392 3333417307 7786708167 8395952704 6247488975 4438035458 7718652922 8912221514 0304831603 6804849210 7304474035 6892216608 5285752376 4911568321 1652132522 9189538437 3730660679 3285438393 9479266204

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