Primality Certificate for (8662^3037-1)/8661

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.675447% 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.390324%

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₁= 32 2404149555 2850629010 1649019801 8312554320 5957966296 2576425582 5427555297 6634847056 2587081698 5967988522 4309673193 0264990360 1245901208 3880400996 2571747576 0241024399 9034279656 1823962108 1898460537 4855820432 1867572837 2327594837 9337877805 9530458101 1258765482 4326469831 1465505494 2774998741 9956517115 2922054572 9091998380 6888348275 7220084929 4143520473 1093530841 2498263654 6585365750 9851350936 4789355513 4698045042 3604656812 6414570623 4026229570 1381598314 4399323714 1410587791 5322789888 8828126162 6280531970 8035104105 8653967037 3127749328 1573938261 4296013238 9477017924 8285632512 8622414857 3570355936 9723534932 1119925568 2937784733 2872651011 8229653793 3977586132 4581945692 1658980618 6813236072 0441789813 5743855104 4620493579 1094196181 6989099407 5122117013 5155510558 1073183129 6580385529 6501192021 8260905944 7618563199 5087946268 7802916669 1150686459 2189858580 5972330685 0428923625 0863995969 1951751618 8184776803 2945793267 5159001578 3124847158 2364340544 7270523836 5620834643 6406494911 1844815233 2526929180 9850854665 1516715582 7143500490 9999575168 8870296615 8939855017 2045157201 3542295579 4368169816 1317790403 9658752487 6618364071 7918165396 0563928875 5759720966 3857191835 2284959974 6613963689 6729261931 7269781131 8786144264 0224050469 1771773934 8383296468 9084939791 6052157148 0100841826 3579795778 0776878589 6198112041 2641850978 3455962827 8406657904 1379828428 7845269575 2606098472 1112460043 0087078930 2039780722 3487164367 7603459941 3717938640 4689435901 3487789492 7517096607 8939317707 6598578947 8956538778 3701705786 6059928125 5900521633 2508197534 9422663791 4998544091 1151444729 1918822396 1945803840 4814844778 0444312360 3333326967 0698514133 3563904366 3811893911 2894797545 4717192975 6178789395 8722705318 6681506739 1534909209 4302440434 3973047095 3683443577 8512692400 7181985296 9354390991 5693126701 1008726572 5175818801 5259288561 7710944964 0788435356 9654071196 7231114685 1565923981 7808184914 1455954964 1078219645 6814797089 4008848629 3997899394 6030686293 5517530430 2055150492 1455629346 4308522587 3386659226 6743901129 3782423172 4930642753 8733097045 7465386966 0033963887 6950824033 8811296420 4788019063 5021226451 5871890805 2687597403 3608304865 4244846332 8003061650 6585527088 7156804044 5834326157 9727931919 7449973208 2895309012 9507355755 1317773931 9606306901 6621897395 9589143051 3835074952 0654424965 6122614007 6554351736 5964100936 0574722507 0810282397 2540373222 4499036232 0693347238 3256627174 7097022070 2146581043 5757028662 9378678242 6360926592 5676904990 6288742083 9809130817 0140960281 5529144218 5380720632 5977198634 0350552508 5504616597 6828065383 2809789499 6850081836 1707721428 6548803852 1881436044 5331383503 9650700341 3406045331 5252452388 4228402996 9146098283 0926491742 6998415587 0998179942 5274986613 9958026999 5305046207 3297058184 5104225165 4693911676 2236493175 6840586704 9353484236 0319311344 3976185059 4546355949 4063492792 2192826724 4017496418 1885400345 8347350509 2602731277 4991270289 7489764552 7681554243 6208035781 8260022864 4532530219 9423779736 8171778697 1293355651 8723804158 1539154144 1284049675 7934305288 3057379537 6594254346 7411147321 8739180672 1976603249 0490103470 4653916481 1932038552 0665187634 3917592078 1516374354 4464993259 0532922962 7593629323 6733804102 2009016642 2190119998 0855998146 8129747498 7072757491 7693975576 1837795887 4254789372 2197815154 6501538206 8086806853 8894026547 0013020232 3578989617 0274483178 7141540754 7600962438 4879871218 8581586461 5518085987 3135666511 3143420782 8875465019 6432779247 6387045369 6749049075 8954422748 8751607152 1474560903 1800591267 9678642047 9654708932 2265800144 0612847357 5312176913 4798297482 4500190057 0485181444 8178721333 0084207890 7556315517 2892611633 3605058184 3889427089 6303076612 9192456212 8475380893 5180561663 4214240021 9479080058 1016482995 9636434353 5786376450 1657425090 1902906916 2801144612 7725644596 7893645762 8570256835 1478039756 5415665932 1978547904 3968159343 3350688507 1676028986 1000319370 8177896576 1084048705 6004573910 0869493705 1578883009 4974970114 2194546534 4876926838 5358626054 5596100113 2665925617 8134821496 4170484440 3683602486 0879336475 3767751040 3098908356 5115972770 7962690123 6776603022 5410091093 5129219756 2205569624 7223001739 5294540509 7967043486 9831804443 6050381241
• c₂= 17 5219127241 2795297933 1805977907 9791590070 2632431934 2397051113 0103451125 0018733457 0946956996 6380966849 4720469801 7763336842 1314638130 0259955878 6107790989 6939567609 7963393640 8378990063 3548702063 1420794243 3832557567 0454175681 7795155847 4851775684 3251606837 3244633701 9571070052 9480326191 6645965924 3465089382 9541817110 0634858300 1839367274 7141557100 4680743191 9343285140 1608445435 5388637359 8549714599 1069777644 2470551882 3566546392 5741721719 6568554144 9886783454 5055813959 9578110583 7007238424 0003065224 0575698071 5939771639 8953341746 3995823534 8487668666 7912146494 3318627026 0534282538 8938847971 6588903873 4147617421 2013486913 9134037909 0339702205 1318314216 0156680258 4605180962 7712486294 3063595554 7107056634 5000053290 7515177869 9000455614 7481770400 4114415286 3755148462 3473485241 7669363685 4508666940 0270655937 6698004805 6557761289 4895486497 4958240103 1954919946 5186608829 1717050779 9139359731 0849502645 1322214482 2590725889 1886983501 4896990421 1907257418 2570242029 2839966326 5448269632 9345983407 5135783034 6774165789 8041383554 8861492637 1925172828 7403298858 9186422342 4121847788 1133319158 3820589523 5415544621 0962620703 7050894724 6015658603 4178416038 1406696817 0206313609 5280666098 0715366103 7435628286 6057672502 6869386805 8688705967 8539340532 9327266179 7039669616 6566252402 4016366807 0659056898 6646190540 2359691711 8643719919 7718454076 7997028731 1688167329 2418581789 7940924357 8335759957 8730544111 3631086867 7444913887 1587067639 5454440628 8974806531 9460176858 2205410431 2042593230 9657687421 1038616610 6766861453 1357653064 8095896186 3476684122 7034122132 4108460361 8966364858 7961231088 6698330839 9035144534 7957820549 8526077363 8438540619 8228844938 7569058839 8061349839 5577570251 6042072417 1084707773 5505629176 3577925111 3840634079 8361930871 2323881265 8117221842 1442223415 4422312457 8505714752 9192783189 9572269045 6376627056 3100285069 5939732897 0808463950 4208960464 5066125584 1449465093 5961644137 2987473937 5225375522 5071146557 4291789962 7396423441 4152588776 5339970007 6485601812 8741326850 1977727650 3139957437 5291172600 0027529965 4497153559 8534477502 6196801179 5533548545 2476947718 6713459544 7166662903 3381215101 7453281225 2028457187 6664805485 5530590850 9736743500 8033429688 8448243369 4060563031 7342304467 2162441112 7702816139 7121209707 3938214774 2204718073 1832334176 7458254656 7486926724 7229896707 9199344370 8688562100 6027369049 4813661838 2548603403 1198653413 4603970589 7176946853 9397245481 8824131869 3049610582 6971049489 9787416726 6256387274 8278845086 8865617047 4417986858 3032024359 1698396617 2632239917 9310088593 2911383139 7550713334 2927875387 1454864919 4986749158 2724679217 8453055888 6045262403 6692685968 4446215565 4685113764 2490175777 8590746364 6293721320 4424301525 2182030436 6613966800 7250249249 5793095655 4497699662 1113374060 3697525757 3467847330 8784302526 2298492852 5926424498 7549877578 2917424812 1250009887 5441350117 9197347503 6687157867 5139178174 1883560684 7619201512 3629436718 4692240809 0662127122 8187554139 7818905878 1906093091 0544018798 1130734066 4236488035 3533724674 8460342312 9532154718 4953901623 5855324312 1878091211 6197857752 8364076894 5514090200 2964745498 1395830178 1414584076 5060285822 7577209746 3830591078 9016410068 7044790479 5679938446 8324855363 5467255518 1172238256 8406974445 3654464157 8400560867 5899677125 2926420204 4049293904 2334201208 5230351993 6511886247 2758772308 5428231100 6424003129 2191535795 6608154002 6082385151 9402377143 7657940171 5617622854 0728020899 6051488602 5154171615 7812911967 4759213260 3189391303 8421601942 4998428464 7783765640 6622699626 9394380664 5862877687 4105645193 6250181000 4060469324 9145910621 6649726819 4129725583 2933592056 0186841153 6016745467 9969124162 1221714780 5785234353 1519689233 0262283470 8023967457 3802590938 6899056439 6067720136 1054260767 5128034973 9401783387 2053393355 5749774493 6425858526 8587518930 5083610610 1017388199 8665892706 8442838838 7989600632 9923000679 3084462459 4523057923 5803978344 8679216798 6993271932 7333958832 1476981194 3062192228 0408803102 7268367711 5111882552 5256272313 7030959706 2347969164 3441914026 9880855798 4365879107 2983440454 9796712716 0166344763 9146320225 5399385772 2471455651 4722045527 1674757799 1988083044 8463392671

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