Primality Certificate for (11466^2437-1)/11465

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.776309% 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.347505%

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 = 3 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₁= 37029774 4608731356 1038762503 4871502576 3731909882 2961935933 7755625202 9688381578 5418835033 8377002178 2766508303 3445376136 7550945736 4921536462 7008225526 4425404419 2142559606 5761806782 9420511343 2328467066 1452142255 4740073170 0337545572 9312573837 2665100364 7627359275 3321051122 9278985423 2783422935 1752436121 8147868993 7412807848 8184376788 9067107687 4063751191 2477734848 6073737467 6564221954 3073918178 1045622742 8922155929 8046760128 9034965909 5661371998 1433522720 9485697057 4275114969 5513150165 5094555230 3381504103 4293871120 7164620999 9314938784 3303601193 8750468184 0021189005 5321115418 5705669080 1186341956 3592199279 1302497340 4149569676 7754764650 8186994420 9318045316 2835433188 8321938576 1017368112 2782185791 8417058677 0572039418 8399174529 8287270327 0311402176 9625310507 0326710132 2300239891 5528381142 7055679096 3238818364 2660806093 2347332238 4966169639 4599459537 2348542739 5818507788 8740763734 1200536434 3059070307 2219682374 1709620772 5526189368 8895857559 5367329513 4466015479 4235832068 0244243548 3295408118 8923714892 5628181340 6062171047 1828783658 7053320413 1836229180 9046860122 7768827205 3553030382 1611341354 2316200379 5577626914 2482212280 2121245400 0203972144 0505207048 8965170055 5809970200 3657605421 8325560075 6990975753 2764824793 4103822645 5785293705 5208238101 4291151873 8543588363 7983971541 0708178478 7025283649 8073658886 6583184480 8399711080 5684236716 8506741441 1707429892 2509076644 4210281691 4718135885 4758027896 7301769817 0119348183 2644024037 1908052198 0373949748 4300387022 8294800372 3884525608 7145285358 3329124436 8354479278 8191249996 0284864701 7131450292 1113480535 7899503712 9391122409 8130786210 6110382737 1765535616 4139485846 6129610487 8447056262 8706244810 9476232527 1739421051 4776281171 6303275187 6098131006 2558333307 0797357661 1238977376 5181438024 6698856350 1039740612 7949728599 9261585299 1326115409 8783449246 3256643402 8838010053 7912598040 3439636518 7949166799 6900415673 0993721950 0000887853 1760207207 0546278614 1518744691 7788020905 9140840808 6056233928 1749789525 4519881135 6189287620 3543145246 6438873740 8926479632 3140693707 1886698519 6777789209 5364483041 9566867647 7890551816 5046941295 1688302707 5551493516 5874673022 9503315784 2613384637 8335486191 1913329194 2433073318 1665848553 6104150164 2247854061 6123711480 6840662775 9818009837 6389113398 6512114785 0807404666 1586962069 9500577720 1361735512 6915164648 1062874293 4836178473 8548523497 3055287067 0547898238 7765584439 8457752323 5944048717 3761348832 6917844865 1194251527 4820595845 3213372688 8413173533 9161143703 5371595862 1299626538 1088078033 0472187520 9387210454 9074467750 6777156656 2979430436 5331092792 4086404419 1416877088 9721296911 1526101036 2343446585 4175702291 4232956631 6292353693 3911231264 7615409082 0116009615 1991767950 0746629532 7436248808 4371766451 5577971762 8238183536 0048206048 8968817173 1835090306 5036421033 1382025440 8296838436 3179637489 8059518197 9589355332 9187525537 3475082015 1464854925 3895451532 5734016827 3834334353 0970603330 3622464435 3588939041 7661192371 2434797416 4806920318 6256573330 7490375834 2438976245 0982509215 4058520033 6789174876 0901996667 5537864458 5793899803 2320994011 3508741162 7855781130 9468883158 5448583009 2439801063 1305097883 0405325249 8838082652 0843848780 0369164819 4871714357 2482179630 7030151040 7099836947 8338902207 0056274294 7279903881 0185757899 5191933400 8003462348 8177953133 8662954834 2225834184 7230727079 5790540562 7206353429 9304349475 7380622024 6522717822 9576272833 8708434396 2852044265 7113700552
• c₂= 2752 3511657484 1345975879 9316397520 4533425354 6080065765 8119456207 9249521032 3004316364 5374694216 2135231514 9365144545 5745880166 4505305036 4167921103 4117634712 2609227680 4030377266 9111412055 0448313708 7540583238 8030449131 7788493212 8885357600 8654623231 4974773163 9333512421 4166709093 5442073030 2808287862 6949854893 2984539309 2660672692 4414565283 5276911496 3531023896 5741667414 6484991670 2392836656 0399295447 1400830541 0372078884 0370794718 8676184054 2630546683 3910763673 4839068071 3927122932 1754368964 5228759155 4593480721 0216823031 0671173565 6352477718 5644746545 4428231255 4721427563 6686530867 6887421026 6410147453 3976620415 6151824388 8667614542 0652814563 5774968686 9191141062 9529058042 3403855662 5936369290 8450801765 0467962528 4190962789 7658969745 9389790410 4163792368 2240324555 2403024903 4517155183 0640438746 0644624062 3781321546 7495261721 4678797039 0713864991 1957027444 1560626653 0651024048 3870580000 6101237957 9304360094 3462242354 0600723771 1455657317 8209981226 3231001423 3574494058 3757921258 2121036168 0176517247 6008140516 0057853731 2509754536 3686902152 1987468661 3585732111 4520114172 3555867123 7731579527 3568160762 9639814708 4362034965 6063120604 5090211851 4297902741 5583150684 7682758656 4988373865 6558134615 4596852319 9825506579 6677046851 8994767416 0334255563 4076690771 8908255809 5294881552 7415230733 6277629722 8998592989 6185142842 2174185009 3736667364 5154994168 5105061970 4198595519 0343416683 9098377543 6686549623 8254057570 3338449602 7314032553 8618500537 6771856274 6287858159 9871493667 8331875791 8634956662 9839181413 1300863867 0764312554 7035459422 3634765463 0559002908 5490301632 5531123598 9894875911 8272705587 1349149875 9917664271 7760223351 5767164775 8045779857 1513277136 4866661353 1500448916 7231274766 2497243896 2168258036 5949956204 6959097949 8470608505 6410556247 3293588629 3345518049 7764710982 8343793938 2619164066 8207352476 0222768254 6502488167 5170527950 5645958254 6449697354 5502501987 4822371955 7988481295 9699184740 6606415043 7444381070 0768814690 8591009111 1796446451 9590772791 7351215774 4527548970 5619490308 4621459502 2971323357 8861224739 7135210427 9578418849 1199270657 8938901325 0378188720 5846025684 7781805809 2846343264 5074796764 4928412615 7512328871 0249841084 8486608646 1024983101 5167112421 8997044995 0211043168 0868301840 4005369436 5093778302 5880413767 5720860011 5392262816 2229577541 1191568544 2755924353 9736388950 6947203844 0968469389 7308787085 5573661178 5249157631 6883038210 1960890622 6427675049 9875370818 6243940544 9977466793 8188090110 2706035179 2882659850 8189933639 6312403911 7382444598 1326872908 8765401752 5915134956 8037663319 1532955096 8043921428 1379099518 7337523761 6278432036 0383292482 8418578085 5642125749 3273190196 6487616668 0993895505 5718394437 7237776889 4408098144 1113279472 9344476426 9807147683 2667237742 3124957280 6949313736 0682120577 7396573713 2070117427 6275675295 9116279182 5674304512 7886220382 8233880489 7889333257 7393444605 2772295952 3439050087 7743131472 6776671964 5946215413 3314270901 6234084773 1606785659 8760028757 9577799360 0456051865 9226114683 3084310463 5624689676 0273486277 5464161111 9489049886 2916914753 1645162838 5150956710 9792971545 6107102729 1366232759 7049088486 0514821680 7914183543 3182381035 9947193732 2370524760 7561389772 7855788788 5192366474 7767987122 1963646897 9263262223 5585266983 5924019967 0883173348 3190444758 8019298648 1214713190 4815869730 7922561439 9648948953 9297351146 2694838116 4705093594 1264913498 3618079699 3088581201 3687500735 0341259887 9747656590

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