Primality Certificate for (5701^2161-1)/5700

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.226407% 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.351218%

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 = 19 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₁= 86429 3797395854 1370493063 0938305365 3063116900 7865417438 3287411680 3753043303 5869677222 8459337734 5482841792 2184269166 8863872647 9317097339 8045299852 7333403262 6445565174 9922580139 6706424103 6111031447 5914426026 5738921860 6161681449 5834684432 9475623267 2277853047 0576312647 1691576877 8204510981 6613884333 8457779976 7698907031 4925577022 5442813281 4672095548 7051331558 8089717170 5325667321 9598110933 3799993247 5621675814 9259966870 1466652200 3485961746 0969125216 0614585350 8330099785 8328562588 8749195176 5145808263 8332978722 4222513382 1891347667 4745101341 5256962446 2438871616 2562779634 0090602157 1731060567 7770316126 8337139978 8167285163 9637510951 6423554655 5802023770 0843796380 3063525907 2536468085 0262744107 7523169472 3310351168 7675658839 1014675861 2187914020 7336066448 4233488407 6808118175 0188072078 2018215600 8416791830 6594929477 1069295152 7512821778 9679211872 1097750173 1928117710 2378725931 0592825276 3651108686 0069305115 1945496050 0271481815 2068345341 1997159469 7989925522 4723270416 5514060750 9508361146 9271152090 0149004542 4058814933 5640149521 8791254052 4296393996 3044429461 2842882453 8815654838 2777555462 7443816588 9056649628 4816153012 7090499689 6495073034 3641712964 7347876516 2393821632 3299235404 5128580076 2075427419 2334297612 6487767117 3528300904 9315943553 0600542172 6578016308 0833275035 6805672500 5824570912 6091165907 6255512308 5926034944 3086142653 0149258985 4046412232 1253109963 7378791649 2539935939 8747750642 8318248246 2297652549 5873967195 1152670919 4429541797 7216523604 0348071726 5048862978 5517639873 4472841241 4915869788 9617751536 9333252423 4092683148 4220464881 0236850329 0981716977 2305622870 6418452993 4639208366 0567722936 5274719980 0023021125 5714186741 4714371980 8697793114 4090878448 7006442396 0801702315 8135682993 0033369786 7514869957 0480816691 2324964917 9818151459 2217461979 1739957142 6816760540 5350134623 0791736103 3390065916 6994159493 5077785439 9486083233 5490484450 9991321021 4985117636 5710617440 7820140968 4367987714 1329983630 2594190921 3898001222 4376187195 4832544955 1858926855 4300220224 2972540585 6191351789 0538714811 6256196636 4003234896 9294422469 2861314428 3782213719 5204328294 1562761858 6389408152 1683150982 5576760188 8261202035 5452740140 8816063215 9682121033 9153408452 4899775998 1167601397 3149395954 0794253563 7663926637 0762105956 8384165335 6352076101 3870425572 9136130547 2403984650 4507573485 4905432893 7874176674 3622687609 1005008930 5488225473 4513230444 9034120844 1631681024 2949188799 4044181899 5980706405 8912084975 4222610934 0041981775 3419280431 4681449535 7770096042 1686211342 3936614967 7442434483 2494917897 5455227215 2413948056 7677510545 9286106866 4892921873 2574642538 8669869879 2166867559 8883369448 6055176340 6162096392 8489215465 7329064140 6558940629 9018987920 3441326725 0359142787 9474171251 5250595344 9719999683 8769696007 4195346173 5853235307 1661040986 5209637941
• c₂= 24 1495405233 3657676885 2697781689 6826661454 2302320003 9082791217 7821800929 4891608991 5104954136 6322215191 8110675598 9776477293 3795762816 0477447666 8419302036 7872389099 7655774129 3181307108 1035129570 5430045241 8576745755 6976656442 2651561414 3699755734 1738733069 0838107836 3527734894 2072064180 4698828940 0786701841 6833543189 1670266212 4282902718 2136879412 0008204921 3002489303 5677710746 6516373762 0061422465 7838087183 3255697524 9031525895 4540925969 0556322664 8816393616 3803649211 7933932638 9275693016 0752346732 4832044614 9759322857 8987823961 2160072927 6858859584 9987335851 0497554294 4796171378 0686653365 3170929857 1315693920 9925154513 3427072903 9948313373 2614620092 4732293152 0127123192 1695807485 2694155869 8755407688 1663578450 0880265270 1256926523 7673631786 5375470310 9436958336 2308663143 4588056404 2243069655 1328015650 2110931588 9598943809 3269923057 9309992365 5207809869 8987857774 6382595926 4874057982 3802350029 2919342873 7000602782 9645174044 3480936836 4310145013 0241877391 6005017015 7585830222 6981928321 7468390692 0109761287 6854515453 3930079231 0874845376 5417365103 0015005144 3138160957 4954078266 7629988733 3953634738 1360108338 5773033065 0039741511 4911438543 9383024632 8026350955 4000291602 2201085884 4576666216 5998608201 5885537037 6951377433 5122812032 9611091939 5472357975 4038420581 6133342780 3321783318 0326332293 4308565331 6422745972 4445752474 2234330530 0240626446 5919672390 7903193908 8453906831 5124278620 8685797569 5464591337 2361561125 5241757406 3913034182 8515634467 0974058466 7377802305 8310487844 5557900688 5980054567 1008288519 9052084102 9749824164 9176410362 0908077102 1560826406 0176424525 7810659898 3582555747 0881041860 7764196629 4570255022 2258482579 5360824436 5079456814 8434180305 5865273577 4597163299 5180457016 1377859727 9109712410 7241335019 0298852467 6516004554 6749672083 4110304129 6560284258 5769625691 1153826607 8318720582 9188969499 3932294438 4274408504 4204902299 8731746150 9227441671 8829610488 2192099634 7017221489 8960664561 9727512044 9943661366 9777921495 7947677232 0600062356 4607135887 6699845207 4663024425 3848515496 7371494545 4669004094 5073273452 1938952414 1766570999 5750979843 0104463743 4831659016 3102170182 4364880274 0492084761 4569385879 3524857386 1408911525 1372707010 2596722744 4831895264 4507034989 7128840091 3088121096 4863250039 2920850000 3869312954 7346461134 5431573693 9705883438 5117125119 5742947155 8383463173 1854784156 3536122982 2600320476 4930012388 3903561893 8086003435 3871642537 4523374027 4954067385 6741233942 3814580742 4153492662 0664564511 9852629533 0580083030 3800940713 0325777082 1318065742 3604051799 3843928470 3542384858 6717183800 7966052482 6158381330 4492214847 0623339479 0603867258 8082278966 4561213443 0368499805 8235371905 5484452920 7972025807 8862149274 2859651743 4357215050 7371992594 6466479946 8788648323 3057199593 0866790041 3557464872 7680990988 6485040438 8080001067

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.