Primality Certificate for (8025^2267-1)/8024 | ||
| Andy Steward | 8,848 digits | 02 January 2006 |
|---|---|---|
| Originally by A.A.D.Steward 2006 | ||
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.
As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 46.490087% factorization of N-1:
| From | Factorisation |
|---|---|
| 8025 | 3 · 5 · 5 · 107 |
| Φ2 | 2 · 4013 |
| Φ11 | 7295773 · 22038465901 · 6890517799742539988587 |
| Φ22 | 23 · 67 · 683 · 13619 · 111431 · 11622601 · 59664825848060203 |
| Φ103 | 2473 · 985387199 · c386 |
| Φ206 | 1175437 · 499837414289177 · c378 |
| Φ1133 | 2267 · 179687003 · c3971 |
| Φ2266 | 457892002261 · p3971 |
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 :
| 7 4684925953 5099046500 1191071215 8060545408 7703072405 0627702405 1722659562 6482121443 3854264361 0175846054 4535861301 8962146948 9881546894 2475510264 9374590957 7312186764 7520779650 9705100313 7306933390 3000088543 1876184245 4581885682 0926070034 8887804980 2312252397 4263752478 2473171274 7854990213 1247504995 9303327437 5831772413 1451634403 0164443244 9302689839 5124491936 4813846772 1729645157 5240541291 9745683843 2677957519 0264046913 4122495151 8861334641 2610300729 7418057450 9175673372 2621174137 1255185236 0255834105 2155287051 4020742291 6999707234 8795617696 9711717095 7280571158 5822659144 9840982824 1128084186 9955442048 1006082491 4835312084 0633209465 8892964411 6251386887 6647007130 3242970162 2501607061 0106471258 3762965354 0001234937 7104957655 0950649259 0796344905 8862515897 3168183883 6494265756 2076028370 1219070306 0519260090 8858797911 9690907770 5713812665 4832984175 5062296557 6425878414 7028969278 0033676444 1935562685 5973052522 0004376225 0710394530 2124963302 0764537715 5430673456 2580648741 0856808433 2480335034 5967235185 2412061080 4681297607 7127379078 1278836272 7577423460 4538243159 8759493286 0466690770 3430848325 8251336044 6367226874 2252809814 2959151759 7785621430 3209353677 9264469284 4046070439 7232166499 5865254747 8606669080 0179324289 5359148988 5453619036 5851697943 2963501401 3581495760 1434645135 7574899034 5438433926 6056658199 7776697338 3489011687 8224762779 8400655563 6704003365 8830546074 6727860650 9433860015 4825668857 4125521178 7776071285 3774292393 5115587474 0317841962 9217766648 7018932497 7414893858 4167716372 9969084816 3710028797 8603081721 8300456162 2220866171 7212805818 0364411661 5522738550 8158364610 8549318049 5940515304 2704908012 3189036573 3259778718 1302139187 5176358457 5711761082 3163564924 8715611104 1767755146 0626483930 8785657862 9252868020 8615304898 8255077173 8425039947 8513960102 3828374024 2740045601 7756192537 0475607175 0962815266 8740152041 8886149314 9958719954 5889044405 4741465723 1979190298 0715993525 3931429840 2383579561 9022861025 8583191076 0744157935 0448777520 9195403933 7925375729 3521178713 3846276535 6941068485 7842668886 3661096405 8751004140 9212417628 7451165477 2913988990 5073722523 7568187779 8463406052 9957559173 7659925762 3363940211 7697058408 0169945840 8431424150 7913154266 0323905435 5375774812 3729611454 2626870019 1599863192 8244430667 9678350504 0982591794 3258495767 9717496041 0800341907 8853456604 9619390515 2185456697 4363257145 6504161935 2908499850 1610566086 1417666242 1906388771 0358368434 2204590771 7966676315 7811571866 5295704325 4343459234 0575939041 4838426147 7306716618 9874756717 7560455631 3125652274 1756607567 8553042634 1833978897 3700338354 7203571530 9904992255 7273297121 5305870099 3336641014 8184208284 7467035668 3281419861 3710085599 9846864291 4088382926 3617785581 6731254062 6104091327 4553117823 8447338191 8173679662 9274082306 3713287583 7030998401 7925048886 4879504723 9809732032 8729933783 2984479571 3958001476 1243451200 8383719082 9301234957 4768464281 0442389820 1150979168 0072831425 0729318236 3467848913 4038151530 2516660050 8781563980 9826816089 4376513260 8201224420 5832044554 3044900834 2601984648 9774456206 0731157727 6509584854 1392971478 1747294162 9202988866 0074174287 6781192390 7074634370 5505296249 4151472260 2012870072 1670024264 9577314349 1757044093 4845688314 0711053173 4521404941 7581681212 1342869972 1411838959 6336152817 5838225292 4090326308 8908586884 8991684955 1065187332 4267696030 4676324267 6958971374 7751767713 3067088206 6576895029 3668989343 4716848295 8271574751 3144933870 4268926994 7233785787 3677938161 8963049949 2493290372 8199068154 1678898461 7536432387 9418307416 8764801311 9360196488 8058363242 5226018266 8143261379 9766103814 7239936068 9128367687 8628852102 1691529419 5862170349 0785900031 4482236506 9552719435 0363223846 7864473924 2672187934 4685568409 7011616420 0299902025 5137945207 9220201265 6240027500 0830737664 0485876901 4864733147 0631179569 2291865215 4876560189 4758916473 9457084726 8831926319 9059763276 7256105298 0664781475 9018617023 8112440506 0051703416 4021604985 8688997785 3874157949 5703780351 7593418435 4470115851 7181488799 7766452145 6512492194 4059871964 5050504344 8869258437 6968869171 7343360122 9750991041 9136738115 7201167449 6660310719 7068145082 4506493354 5206097741 |
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) = 44.881442%
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 = 2 suffices.
As F2 < N < F3 and N ≡ 1 (mod F), we can let N = c2·F2 + c1·F + 1.
Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c12-4·c2 is not a square.
Here, c12-4·c2 is ≡ 24 (mod 64) and therefore cannot be a square and N is prime.