Primality Certificate for (7147^2161-1)/7146

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.238249% 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.391712%

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 = 23 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₁= 6358064614 9728680829 3833836616 2850123049 3794121010 3951874021 5956714628 0885327621 7739292288 7255758726 5493838771 0591462466 1954905102 5724055899 3577532376 8817503833 3478427910 4599333417 5584657966 3116891912 8731630360 0976449234 6924826251 8425268174 0904368146 2053613452 9633456655 7702247530 6105605210 4657681777 5478963505 4681434846 2161420686 2822429340 2346569975 1167491511 3082010881 6383729928 6726378886 9348256742 6108975367 6122021105 7249355648 5189462964 1483096684 7336793933 9703949263 6397752286 5816511660 6323096104 4996757417 3030207304 5674878021 2651822112 3430378888 9414366349 9132970585 3924313428 3593343866 9768568680 8580279205 0778648455 7813562894 2563685005 9904500281 6857239053 1224424444 8037715802 2298201489 9912931464 4372958039 2066126827 7161471915 1223121243 1417219967 5420186659 7916658472 1784264156 7377140241 2549174383 3478928160 9806003925 3991668322 4886089884 9728247223 8115380818 3934889248 0135328196 2528218101 2044414262 0973061002 4748284067 1410419130 1712077361 8431600734 7638249103 0639159590 9303596479 6376142718 5653977780 3354992962 2260641765 3814686105 5992637899 7446877002 6022193953 6648698188 1371082496 7811650583 3733789032 3570500916 3581270142 2942325577 1594143538 3072498709 7680628462 1008293890 1477301801 8280546193 7498162178 7718743126 3737534617 1678016775 5955838669 0862741076 6188485885 6226391046 2971167682 3948513325 6332556400 3154688486 2856398557 1430487056 2341952482 2362863440 8130695803 7437046752 5541577689 8546392465 7732873390 0687912908 3962494950 4762189215 9870924050 8374388094 1964246657 0213141655 7163826337 8632024737 7648123656 8045866106 7712507790 9148086715 5213455492 7392710006 9287469179 2046501827 9554901018 4048493481 1777829926 0957508033 1069264336 2972247858 2772345683 0458517386 3150473793 0545280900 6144509271 2433630622 9570388203 4381489964 0798754918 4709874631 5474722275 2090293466 8999111166 8032544160 7084464145 1565781279 3638107194 2188190714 5438669920 2789427579 7247608228 0363602335 3785624335 2850876113 7363205682 5072834093 7340961731 7036928178 9857195054 6778359663 2760695145 9626732530 7887823827 3713373522 1836586505 4998951334 0148632668 3951104852 0454877535 6044301081 9609227392 3238684543 3531214132 5120659497 2784627423 8589647963 4882102044 3498461048 6224779628 7213620790 3742798138 4705826151 0287124448 7813683497 7880231185 9028396478 1793823258 9493118212 8677829468 9319264939 8527476967 9506425241 7626169310 8220998461 1037203174 6517261063 6448208907 9669052981 7374650688 5788934528 1908596555 3860862028 3165058684 1404767347 6625387259 7130809494 8495363060 6985322570 7149569861 3840181191 6016053175 3461655163 1310331443 5204752701 9528722086 0471436536 4339847842 2352370259 2696073858 3452919075 5449724541 3590419291 4565673483 1167884767 1921934139 0953139484 2378620988 1154100018 2331353330 5942661884 1251876280 4982201043 4222767104 8564354775 8350581585 1070976228 3245301901 1346556537 7280426086 2143104440 2688490403 9694290350 1535734727 4021679285 1261961288
• c₂= 177475 3719930505 2423048660 1654400620 8996965543 2824265112 6570888175 8105079926 9407492133 8630918924 5756519449 3004713040 1120200257 2190645372 1306186937 8836093312 2204915746 5154582540 4237591448 6543027086 7935678559 6567094201 9182095436 6938331480 0798296327 1772137899 4473622120 4850094062 3853706593 9161925052 8570450146 9516937134 0008661655 6878782826 5052981414 6783978552 8079468247 8015024061 7940751086 3219792389 1612524540 1313778533 0181543033 5925375893 1589385358 5823323420 1710033616 5592328363 5231807693 4467399415 7125959357 5631110861 9419396377 2113730987 8930088832 3601548672 4601562489 5710367131 2683308927 5706917032 0933610462 3399998742 0664728673 6942077753 1945625146 1869829971 9231218445 3688058220 4842839943 3017707066 6893338359 5682406888 0969544171 4249906385 6757753543 8679026955 6158325988 1238057650 0797958424 8283176716 8035843461 3861694861 2621496925 4265871565 3680522004 8231947638 5108396223 8379731777 8165367516 8874981881 6219627694 4251044705 3623421558 9752423059 0670333582 3805143356 5407882173 4571120597 7690230259 4487658937 8926317467 4063997995 5575620703 6959644802 1562195164 5909550652 9871134825 4701139489 2326429099 4830920190 6111161332 7227772271 0707005488 3394010313 6414543980 1962002439 9858324159 4905155189 1694626796 9780945589 8556890966 7007959126 2060018013 6447242787 6520015686 3246383030 1829551053 2658428148 7300925581 9274423535 8645036006 5164721827 8000391200 0729329552 9431605447 2451355543 3284053890 8105740993 3408210417 0403506767 2460318671 3190759585 8296503961 5082724561 3947914718 0095895363 1086221122 5053370332 4352286710 9030017465 5372209890 0442053188 0871733762 6986819801 1330831173 7454035359 0188451608 3476521476 1731879962 1296879886 7268706746 6293278922 7589340145 6167440430 9591968465 9824948580 8761367038 9200129422 7462308803 3538821779 7979180234 5879684697 4719448515 5916967096 8974666120 6643931499 4301631395 8870282516 9603258996 8264362501 6776316894 7736828107 2440443814 0650709155 1154835653 0158749479 3858048906 6533845185 2021603445 5975050220 7652135097 3455864473 0522651213 4424175131 1263246135 5711200273 0399551279 9023092053 2524919369 9675494143 9911536892 4586039516 8367771653 0868644135 7869950560 8479619838 4946508410 6427480860 1750033543 9792993874 4372607160 4964897941 3098990227 0215052312 0036984376 9792948359 6708224490 5858612185 0146800271 9263990314 0491804970 2215801509 2633238000 7691227096 6728429864 3467802484 1627719216 9483302416 6101224822 1332495471 8814910736 6974994789 6226862662 9450390969 8674028844 3238741674 7756878864 6873005271 3370185005 4305214753 2652692319 3366587672 9729664941 8550007084 6872357326 9075422351 7221196333 6686785829 0451930742 7646372265 8847877055 4925364773 3995666248 6019746608 4160039414 4755603301 3903978257 8475364412 1605351478 3309902466 6501784689 1445560828 3629759621 9165038503 3225937606 8610816209 7399028511 3690483957 4728513710 2420134051 2001778222 2775928288 3756687249 8057066281 1809241142 9600120916 2729971352

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