Primality Certificate for (4616^2017-1)/4615

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.965825% 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.350793%

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 = 5 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 3996336372 2338481356 4916729978 0224951974 3726288621 2176635109 8692848944 7985020631 1521254498 6072995481 3601095459 8151700599 2011041677 6523647644 0810501542 5853470785 0131354699 0352653179 4925170103 2887057406 3596487333 9287728855 8789857082 0260987540 7496409470 7354036687 8774878005 6321223745 8476383269 2870801469 7876367598 2103639808 4331464166 2220905104 2723809489 4303280954 8502330465 8131591471 2018792083 4986488803 4671025030 4469295633 8064235595 3143403459 4016802389 4243081252 4494212489 2555923953 4743021191 3395463100 0191497759 3352489176 4842153768 9418308756 8341792532 9029449307 7124951221 7195750521 6058062072 6107953205 2289635282 8218479858 6326888816 8481243845 9342851242 0347251189 9993304312 8974429977 4384544137 2470123153 1328411233 8747669207 6616256545 4847959091 3561268545 8749999204 8094872854 6375869905 9265780513 6936292044 0786575870 7796847260 3819990046 3320429341 9414010587 6844375643 2848427522 8620683705 6138131075 6382307014 7418525918 5687330107 6579135262 9483060439 5565681164 4375639908 4889550620 9090709669 5445822417 9599434356 0803289288 1489971279 9259717928 8811923067 4947458046 0274862599 4213498892 2366607826 3424410977 8787907450 0270485881 3281426445 4804422154 7607086716 1367923647 8012547428 4111279389 9198085863 3613172999 1183599343 2784523687 7123629117 5112324983 9559708403 7000431865 3535925392 1328475694 5973502992 1358244676 3201229259 5681895516 5078500890 8690802726 3899287064 2636589441 9833103993 0575730289 3897116667 2195105760 1675182956 7736950383 1210419684 8697287279 5778663732 5889439978 1512018038 0478384533 2733065459 0442126592 2155999294 5249574349 3180946202 0472534159 9227242766 6314397174 8782507243 3888964499 3325225050 5541219292 4609580364 5324314957 2004317654 5872037721 4652931684 3743924553 2300469395 1721896138 7163053642 7862225122 0974738541 5350825857 4750149329 1738466318 1547600173 7247066840 4350588873 8766364522 8398065158 4576040903 8572771498 4698853133 0852913668 1012075995 4839082056 0098374699 7596871215 6427607778 3397269580 6539264983 5550784662 3761362328 3399339121 9793954891 3896674838 8725473132 3628003181 9682821975 0199001939 1945669919 3153383844 5105591453 6546361650 0365582339 8382082696 2378206867 6819432148 6633137317 9810928706 0329201463 8230217770 6842182801 8012945035 5524497824 2021266161 7096842500 2634880708 3907424778 9387170019 3725103175 1219588467 7373499390 5291356418 6359340963 6490763876 2161932531 5205910329 3225384113 8524312506 0682834857 8658359705 9958383055 7420312049 6770697024 9914541169 4221644346 6030067022 3437414499 3691510633 1600639699 4570334648 5223306897 4018874668 6598818920 2407117135 0354397321 6161641143
• c₂= 6413718894 6716580046 9182540610 9270132472 8649596863 8732600908 5296533342 8428379976 5615749234 0977075775 9007986541 4591814775 1002472164 1212090900 8154212035 1298358892 8996338371 9145167431 5846432823 7026506055 2940758131 9613477932 9673161981 4296252228 2937165442 7250199366 1556433668 1305353827 4511666158 1387648156 1897628008 2312155494 1580062526 7510110658 4548877524 6753477879 2297159132 2446615669 5668282733 1308731852 1853994700 2101025574 4113341267 6935380192 7358855214 8152818307 7081471037 9401654313 9082329099 8171525337 9507392098 9785577541 1048675185 4050789736 3765785595 7598341277 5455268107 4829976881 4813462475 6391696101 8179085196 1661615115 5630997673 6032017475 9067300946 1428522479 9861187940 1275483228 0624533297 7055818777 9874325231 3321423420 9278843749 7493105631 0427327323 4938813136 9827074219 6410520630 5840489003 9876479485 2572881347 3337853382 2025473868 9737688592 8683649591 7750594036 5407350986 3711128272 6955629912 0169868672 6073136750 4781558403 2081028129 3449043176 9604189039 7948106242 4276915137 1230509058 5203144997 2122686683 5914925468 2752834366 4538724841 1140725992 3250807758 4982437453 9411851361 1202875002 0773755357 6299456138 9818586711 9638961896 3431511302 3167725046 3548440446 8356404153 7782962623 7743488752 3385781945 2086278107 7649718297 5581347590 3036922462 8256452689 6145707605 1948429164 6460521761 0377746026 4525580655 1595326760 6568214863 1693066773 6391360868 1483553672 0822325380 3943389750 1052668579 2841487169 1482557664 6412937415 3625820702 9308300507 3142942450 8988504576 9199285983 8136476508 7169732522 9392369228 8441852568 7302150087 2440464640 6291994763 7509889160 3388963746 4106157954 4944248997 8506761392 1314574388 4022036462 4389910151 3163813524 0688966163 5958750263 5394600849 8524861085 2860523222 3608316013 9285963640 9767618367 5579897664 0506736927 4941183829 4344115103 3611093950 1026113493 6758995047 7533998326 2947274135 7437679545 3783656448 1961310326 9312406902 1659020579 9340748279 8449014257 3938779057 1999275148 2917530268 3050106659 9321575869 3476608540 0780539493 7490347996 7885081757 0317050429 0965228363 2892203644 6069044232 6489124440 4083652244 9056849093 0235274201 9282164529 7547173285 4281441671 7076648635 7069336765 8018147364 3770847917 3532901347 2423614510 6803853247 4255397335 8257628396 6076126179 1949450390 8748799314 1238060674 6472905763 2506980484 2733550668 4500467930 2447027581 3903513502 1495045090 2134307906 7929225176 7501955133 9646329643 4134596068 5029887026 3530879073 9082446432 9205173260 7051556274 8420242060 5984348563 8084569553 2378529724 8219805894 1378722170 4719652314 6385513627 4117624024 3965200791 6560336385

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