Primality Certificate for (4466^2887-1)/4465

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 33.434092% 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.345101%

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.

Express N in base F

As F² < N < F³ and N ≡ 1 (mod F), we can let N = c₂·F² + c₁·F + 1.

• c₁= 156 1641114462 8961929325 5713382164 0522103083 9184472521 7783835226 2434397024 0775577398 9299975678 5111050688 4874093376 7753295445 7181564479 1494229710 3492810425 2255965045 0047211303 1482538465 1069956742 5413617656 3676241617 3657457283 6338402900 9090477141 8817501397 1206831032 9741182590 7097779852 2290432273 5825278130 1730196442 3328110970 6256257275 1140452730 0934923475 9366751078 9229891708 8297554728 4519480529 5914307701 6571911555 5533064426 6552475701 8489931916 0565890480 3081192626 4165567625 9381889900 9897856833 8889936558 5884889963 0840604566 9482431973 3380149844 0225521311 5397731043 0017761673 9175253608 0553406122 6490499971 0777314088 5992280053 0675445799 4222958038 0244833900 4906476206 2324113228 0796509734 6447159931 7285842388 4306601159 7118598614 2091189654 2813246480 8662390809 9945361408 9295821740 4653402770 9332918862 4060539608 1834118501 7832904738 1839409854 5748838503 3942237124 4677854147 4815281387 4673738849 1579778483 5107988401 3651554895 5630896413 2672064653 7087567237 9808403527 9487784651 1107967782 4933409789 8943833954 2588261029 3797138514 2979290473 7129875974 1778988151 5677176484 8375486307 7830036293 4544198247 7475834096 8249461430 6021296456 1227172051 4058138262 7204369306 5317690530 6775506559 1329282468 8176488078 7479907655 0885276046 0245292129 4576970761 1343202176 0406590307 5850671750 6953481709 4880768908 0153987738 7524382976 3079079000 5651698684 9602871288 6878478718 1951534643 9051936810 6453275999 6878862282 8533792718 2309760380 8896260052 9180113261 8709178666 5177558072 5529151414 2332721142 2925987459 3297388327 2912755412 5738512194 4193731512 8372744456 4334077322 7911420608 9639867678 7280865803 7866124035 0312426891 4654585934 8636022157 7766010511 5116384207 2441900062 7458915532 7162276799 3754666076 1174882162 1119493017 9775757673 5028831628 9180350634 5553948915 0319408763 5280147151 0772540056 2651151018 0299251989 6312786651 9372469623 1620254111 3361668338 8040102402 8667115812 7888083971 6347605098 1449227811 1501316674 5520150856 2080120407 6081033042 3169133024 9585637072 4546778967 9049795570 5726915941 5935621892 6146710722 6094310739 3687523825 7865818700 7943872112 9585176602 3163795576 4832170927 2257465695 2490373173 5599722931 4667929418 2154196644 7635080286 7863566446 3799442321 9919191735 8254945850 9217970439 1255249387 9195885732 6508443523 0364438657 0901802898 3763577614 8562543617 6715207052 8050484162 8332515368 2600722910 1236932466 2903207326 4880025935 3097879710 8247603665 7272911412 7253587228 5017078090 1416051797 3321404013 1148150170 3035979796 9597866086 2534965910 4911181605 3699875316 9285762267 2211255198 9216905228 5088975333 4838460387 5078368469 3190513196 3167631976 7116350256 2987359943 3847093123 8323003108 0172605770 7741835140 0316261731 1990064406 3825254568 4758656217 9974178662 4036957583 4566192705 9422099687 4138983694 4053882918 4698263104 7379221597 3608645187 8845214025 9045572033 6364443565 5451143311 0821611171 5875894842 0511005032 2845439873 0536352103 4005213358 3881181177 8333774438 0000127307 6298387981 3763694857 1920419350 9800009152 6217017153 6276576777 0141188330 9448241423 4604861774 1132970015 1200081557 3814439172 8907351464 7957675941 3458862564 6750339472 4952697362 6540999760 8572663341 9348477070 6973119652 2901357227 3702093288 8515895337 1035735689 7482098615 4464639728 5462486643 3181822991 6260167416 6892667915 7156390765 3064152952 5607197830 6718171063 3699977276 0905716009 2061094080 5071169546 5093124111 3740911322 6384409802 6462541744 0497923360 3866020428 9194647448 2818614420 8527659170 2829473452 7147691167 7167724933 4734744813 0185434091 2324570185 0171908951 5843354677 6488812491 4670370766 2089964205 2664651128 2493746803 8627383245 7071725727 4290587493 6307002256 9472528636 5191768409 3749489178 6850205004 5156435089
• c₂= 553011925 2356192942 0146471305 9378769131 0332793150 1350865083 3781580614 3446962589 9120390503 7556859241 7352438312 7191713204 5004993552 7994834905 3782893035 2473459015 0228327474 9427128008 4585422522 6378986550 5853699633 4632736708 8457679524 1860324585 2042051722 7767867417 5801773608 3516235684 3603808540 6487603782 4191521501 2628352266 5909587728 4204413820 6060504855 9560623592 5250059656 9681172103 7740309745 4392301705 4978003066 4875217009 8870975216 7885832220 7972840301 5164838673 2696167239 0044474364 9153349621 5378327761 5997707549 1361790276 0093689414 5681808872 6280030294 1400623510 1668719522 0192904592 6748632781 1449019080 2738556164 8745348490 5500099783 0165362896 4713374423 0980921289 8878688807 8539500758 6446365268 7220179898 5860676688 8693749800 7470356763 2500868984 5442026801 2227820235 6289330315 1312399724 0310051098 8047075673 2263946673 0551467714 8077724478 6221799232 8362275330 6985561759 4886060973 5988422500 7392733869 6367127379 8609802107 5728885252 2125262925 5899580485 4027200213 9266103709 1309422934 3738927506 9674907739 0028274558 3784869354 0254673159 1647913535 6617745595 2165450819 6613750950 3217774431 6110897449 9013479177 2033980744 8097791088 0569831398 2993264842 5774650442 4497365955 9865498218 3627804332 3978166479 7079041775 6129111852 0164130747 0735120097 9919878079 7884424372 3208610659 1917208164 7372083893 9779730129 1564046215 5469465936 9790082555 8636848275 0525001316 9063957435 0253047881 8586004152 0958007730 4774449290 9432806689 0541977701 8515374889 6852748986 4932176824 1737411582 6747371729 7802957119 1732544524 3415551895 7507852576 0356714340 0715734619 5219999778 8398399376 2194363895 2932081009 9583226225 0676031318 4110614027 0705862944 9659465494 9727663586 0046571635 5366015937 6590967887 9079002997 8398867995 0858265127 3850143666 7160268958 0651078250 5606174090 3415771489 6884883759 5542200622 4457007531 9147979934 6422166236 5738766936 0003674434 6307893618 9190004795 8535840019 0073522984 8029951846 3066974528 2129228054 7152691659 4296311799 4307922882 8641001028 7142348865 9344688462 9274213702 5984894113 8123021437 2870629121 7838695636 7952150304 9179134206 7210620636 0750627164 1438600020 5727533994 6807590234 2523780105 8247375066 6785002550 1897570172 9217668317 2475293973 9071796077 7639524187 4325407885 8257476852 9731517135 4167316955 0637659280 6554880968 0352389016 6704136317 6512717062 3291370626 4974299695 8298314439 3481179176 0996345180 0233121241 0787649509 3987446470 1229383412 2368562686 1976827144 6517480650 4396811043 9556124311 3225460582 9644204638 0624508348 9132873574 8861846582 1747468600 1806572494 5676172502 2510577989 1685862852 2921312151 4167561454 1084666615 1480868447 6376181687 3297656893 7113110320 0001597781 7318190824 2658478007 9832737660 4985897209 3183271430 3523623534 8569350123 3562795738 5087805367 7255047884 5835604894 2463004724 4253552023 3294110083 9893055151 9269158006 1901041639 7932747274 9616981259 3138743878 7867793190 1458732515 8752928809 8162475666 3268471562 8695262605 7276843418 1596236824 7116698297 6351777484 1122764417 2663399953 6023796148 1925191170 3846831554 8305687336 7789204281 1008413907 5156189650 5380173498 0989211052 5470900880 4831455648 3368259955 8128079529 0459337592 0581782275 7698545493 3553222912 5534326125 0769088135 9452441326 4851212052 9709930072 5775583590 4585908524 5855190547 7646601425 4697598648 7303382446 3985293874 5577149961 0115818965 3110196250 6648431793 7135225768 8259375994 3422443817 4854444829 7681456024 6781097840 2939329786 4084584503 7706441931 1687406161 9365155901 2665452439 3979197852 4172109170 4212079261 2037951489 6619514793 0153484734 3509159228 6832593768 6346926152 2517233645 5485816329 2632506331 3931720921 9976035765 7430289089 3405693534 4907372406 3428923958 3567045567 7452718550 6144745627

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.