Primality Certificate for (6087^2713-1)/6086

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.655174% 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.428299%

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 = 11 suffices.

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F²>N, N can have no more than two prime factors.

Express N in base F

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

• c₁= 3 8024324407 3012830462 3537431380 9511673641 2225318765 9913090226 8650961383 5605220900 4825766446 8488527835 3921760134 4655873369 4544510704 8724762736 9931672189 2408484968 7641225503 7531732455 3726176368 9599904882 5846800330 5210468761 3770846445 1275544822 5536778599 5391238693 7497129224 5927837422 3575763195 3135822244 2113037408 3573215733 0035548105 5940351153 7101049409 8024769649 0643913791 8201452713 5372996742 3278612581 2129327919 4252077808 3840597638 2287188688 3386600532 4539626666 7431096143 4495965751 7315319567 4782291045 6324340326 1613460894 3141910229 7527271113 6880893959 3852194094 0278777168 9191404455 7894219976 2890494558 6404667963 7504555925 5800770915 8422169026 0216524481 7765409607 0047684674 9460982793 7455148695 8191982408 3709230172 3456680270 4858507384 9250299947 7520726165 2290937597 2700461863 8574238855 3218103204 1873189824 0079783895 2285098933 6964681299 8787171923 6102285087 9549673078 4218902629 5283362797 1368000913 5339560959 4961675124 9718366032 3100321370 5594058063 1299835305 6937278258 1306221905 3782198289 1082685880 8246088081 4800910987 3818988605 1749495905 3842498591 8063064032 8796348186 6192697811 4452220198 0725628236 2534523468 1742521324 6708176119 2345466916 0894434976 2712310307 0396540298 4564224622 5049591014 0776712484 5599557863 3874943124 9367394600 0263933483 0693119619 3023077844 9536846141 7120623588 4848542491 4552675893 3325351118 6977446354 6369920121 6667657025 9010077490 5691167047 4959216106 6030147215 0473393324 9220276973 0200382459 6275862603 9564674370 2179441607 7677488601 4612782761 6543041390 5884981004 1560683707 5615109079 3825671423 5810306405 5483371731 3663170048 1792569339 8421983740 8890310960 8673812248 2534339195 2608617528 9116660428 0899201526 2774331717 6031645014 5712013550 7044322873 9433336896 7977677463 9966035923 8356980323 3430916592 2902017829 5598404051 3966287669 7173331483 0123377646 8293793879 0158582193 3449061284 0333930738 0388975954 8283828436 5315881875 6015516494 4215049337 9758281803 4842958655 1101816666 1062515638 6314430929 2981260885 4348345744 8369503147 8317317232 7803039494 1087223675 6365837433 4838948193 2598724697 5519583582 7981098610 3241979289 5022244991 0269974582 7758338375 2022878020 6279962512 8424381521 8985113854 2382873411 6501268059 4305347352 6608344566 8148332506 8087512037 9707705192 9888850847 6762809604 7099212287 8125378570 5803304697 8253069139 0556667260 2177421074 4308046092 5233735206 9687536466 7953566452 0530068357 5016084099 2160895142 0031772354 3454739689 0685511421 0165492209 3540654600 2719672621 1059282140 5447255685 4788950218 7996197698 4980671810 7977434504 6573644365 6571767796 1911814747 3606465652 9214375005 2512734605 3553148766 9303123339 4623914415 6710155076 4224060469 6176607396 0731169510 2005753874 4084294401 2877083085 7477899392 0814183663 2785145419 3954380142 0979904437 9310019059 8658864452 5102482259 8274544195 4481863254 6615610040 0360570276 0937372906 9367232516 5622302575 4982696136 6385882793 8445010729 7900880054 7863980019 2669602674 6976217265 5807383762 9212173978 2824504072 6543741295 8523791854 2860230157 2976933481 0500787831 7958106458 7085882271 1996189010 8373220181 2685526730 3394152764 3340675055 0945767273 2087750961 2933692061 1232716910 4560355956 3181646544 1308146865 7899742799 6730823723 6610896456 7546277932 6368457186 0193009380 8955945418 3735059503 0811504840 6537027500 2495570451 3119321966 9819515448 6470287109 8882313507 8942782640 2679323811 2341957255 2637304093 8258218958 7937245909 8772563947 5964139797 0649173488 2213459544 4056637018 8236144956 5904338255 8497402511 1725832631 1884528620 7272933209 6368486774 4469595760 6275081366 6985836189 4157682957 4014103683 5080056368 3254809350 9080816320
• c₂= 40 4964132168 6432896396 6560293191 1801259907 8617731806 7851054388 2828427486 0602507378 0188815846 7376440426 2770422634 0652880383 5871942786 3156073548 3262521881 8426501185 8367003195 5277701806 5047961176 5318756088 1906671957 1662539184 8611592759 6938418820 0529993800 7994552307 7667984072 2637323968 0336285554 0990923473 4376222718 0322635495 0289859901 0928211111 5682230212 6870004884 6743615009 3025107258 7265469873 0468971192 9719065656 7037832767 1028616489 4099750357 7661538175 7401996462 7774937698 0806719263 4007444218 6865529002 5915709937 5828966627 0011527965 9425511163 1048019511 2179058361 8706069105 7752081545 2134804768 7782757326 3749306006 4685355200 7455838480 5452067082 8974578191 3379097810 9501643023 7033215720 6630177039 3690989920 5942240469 0379884280 0470785555 3768238087 1239126076 8978668621 8010203622 3946115529 5896567404 6709583336 2501403845 6171912761 8826769415 6650565807 9768732001 3059194622 5176988321 2920419522 1349039644 3856338172 9322644022 7318415607 4196499536 7532722731 2205326905 6049917820 0220390445 2149520634 5399274115 4823071190 1740177989 4304810486 1579789174 3116706501 0590251373 4173660816 3141764723 9212155338 0030354333 1987030755 7942601579 9791343446 1844841157 8363118059 0744527530 9367174667 0039205194 3017421344 6418115829 0044443386 1138039401 6370058217 7751888423 3707918296 7371452671 5753573912 1837437447 6489634087 0460490606 9191063139 6855383318 1418976733 3127901520 4154609814 0729250749 9657605666 2712885640 4133771455 1628915971 5116486120 8518593310 2864289230 5143483687 8476138575 5259805870 3833342437 7853025245 7199436186 8139558819 2007128710 6936079036 9154086275 6980499520 8456283837 3971435247 3930021850 7197463160 9433493692 3848090218 0837632929 4306245183 6594080536 5651616644 0841036879 6103641340 2089147631 5894217858 8273709120 1383724209 4207989530 3005886008 3615239457 0170302686 4906931901 7949370460 6743304375 4042478801 6084939863 3226665420 3070468544 4590112949 2275022367 6955386921 1802788656 7579089186 6480252930 0859517609 2025733942 2505314453 6705548011 5478786214 3153023950 4825748193 8552620741 1003787058 6903126176 8618689881 8081844385 7031942515 3825464792 9404367876 1659095975 7029216936 4129981500 0401583508 6299439027 3981197439 4196703830 2451754030 8336508861 2941015580 3355881870 8232885484 4447054625 7091349471 3756568041 9528127543 8455164334 4885403552 9553156294 0453872117 4449055861 2092674161 1191345760 6238634246 0301402897 0893825465 9375443244 4979532898 5846473340 4674892712 8499422563 7314147052 8641895439 8276926562 0537768841 6365570192 4111564464 5879199028 3945282116 7048665160 3163819153 8207075605 7505267079 8571276856 7834009417 8109780631 9217466443 8068851523 6282999406 3242672315 0779492562 9188236778 7172252112 2812298988 7309900308 1717737399 8852541294 5342507237 2108085986 1688241700 7655101931 1931102466 9614516699 3673724972 5334177611 3003246321 5140434346 9465743974 1112119010 4805974830 7916276032 5022331923 2725016358 9142473579 5803234865 2384091023 8502529503 9396639582 5114616941 6711232862 9568172478 2396277320 1171427480 5028453287 0927169686 9128703704 8586188931 7218792670 3583722866 3589225591 0795963739 7001909275 5407376135 8338837213 0728181810 8046584939 6334576164 8216361754 8969499160 3027057746 0449280122 9474364336 8343112954 6216875021 6051426305 7464102981 1622837470 2463297776 6247936982 5308059330 2363563844 1763309624 6530595706 4642530581 4669952504 8347519395 9356330181 7218575741 8264436959 4331020746 0973044902 8862325493 6498241113 6688005813 9073883261 7386820683 0943820973 7284650661 2700085539 9430480174 5951975228 5039624234 8339248163 2545839673 4165641191 2681738090 7725666470 3487428978 4094915040

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square (given 2F³ > N).

Here, c₁²-4·c₂ is ≡ 62 (mod 63) and therefore cannot be a square and N is prime.