Primality Certificate for (2639^3119-1)/2638 | ||
| Andy Steward | 10,669 digits | 26 September 2008 |
|---|---|---|
| Originally by A.A.D.Steward 2008 | ||
This certificate uses a theorem of Pocklington and Lehmer 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 50.191120% factorization of N-1:
| From | Factorisation |
|---|---|
| 2639 | 7 · 13 · 29 |
| Φ2 | 2 · 2 · 2 · 2 · 3 · 5 · 11 |
| Φ1559 | 72283998463 · 73657403840613389 · p5303 |
| Φ3118 | 3119 · 29721519443449 · c5314 |
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/2 :
| 752 4471236727 3434668125 8385932584 0699656238 5583429369 4626284386 1154308038 1678742898 5697641100 9225729566 7964523536 6146789768 1834594729 3518970633 0461650305 1545759642 2658931312 6533941670 7632571045 5865317359 4036541639 0778964698 4895989843 9928272291 4398394437 5416452062 0033969599 2764680872 0404654000 9039100635 4775774269 2947734380 0912440475 0515575461 6211515333 2229287392 6469848806 4463421444 0015337073 0595758040 8464990175 2589418516 0455325171 5820916200 8382688799 3721609994 4821432818 8646098900 3664859242 5989676573 9713890703 0416835584 0983634719 8240998411 4204128620 7818262051 4111566047 4312675791 7221604920 3907946688 0359224016 6057428582 1360590494 2696415388 1760364488 5644991937 3818736411 2582052118 5112708605 9597412068 1117525209 6124318259 1176293709 6756937460 2867162401 2872611833 2221206404 4101106900 7200655032 7083399712 9429941251 2108770298 9793332975 9501134499 4307426003 6424446901 6387196274 7405470768 1284674316 8811503857 4165594569 6510854727 6899122061 5127744531 7620093544 0977731145 6341288092 7836024108 5648767416 8498991387 4558794962 4934654124 4405432017 4348128257 7791551723 4906335040 6734884795 1336432938 2490481930 5884483628 0361202557 5993487531 3482178247 0815757764 8590520859 9876593009 7344516584 1181638015 6813604421 5377577135 5385975835 1098450195 2649542428 5042089846 4796994934 7254071708 6646661771 9044923275 8986844622 1588727994 7198599081 7178201656 0527251504 0749655502 7908877287 2027813673 9058665029 0945493414 4486851345 8179785410 6036715717 8003392360 6138210836 7945251764 6212713872 4799629854 3028742297 3490065617 9492975707 2564167938 6569722702 8941257799 3468228109 9645925861 1319810569 6485544772 2698529630 1849383154 8087440529 9185930913 5037886458 5115437400 4489528146 8703386239 7303574219 2090216738 1758081939 7534419096 8545363173 0854593103 7544671794 3262311003 8374016314 1562908530 1783757373 9405556237 2749691563 9929397289 1880101294 5301156003 1421053849 1508285743 1309672699 3487646881 8293879490 9256301081 8721511130 5928555698 0567088236 1712431817 4109675934 4757440403 9082004530 2008883494 2592245904 9388792724 3843933957 6301582220 6786608530 4222710525 9726270286 5808357510 6203211001 3763667398 0878368091 0930077902 9745268665 0317565446 6394062026 8294357216 3478579920 5634305116 8801807985 9991979460 8219474969 7087492200 3319043450 2925352332 1493110719 2317580670 0233739087 6964419320 1057801814 4790154500 4355203877 2451413062 0121049360 6826746615 9212209818 8758395806 7398679950 0650371188 1577648939 3391458806 8659276343 4728649439 1426357345 5870627254 5177523266 5868610964 4094642092 5854418605 0832226736 5122175527 1644595230 4724259986 6357978194 1224502115 0905244215 3210548561 4110322988 5596971797 0240134938 4175740054 0836128797 6767127913 9584015261 2207406092 3347633058 7730547543 6380098972 3141351603 4810888550 0585701826 2013662778 4320634241 0291590396 4460805905 6106321021 5361368893 7253139537 3838077736 8796399467 3548483787 9848529064 1793298203 1456850896 0046680737 0183825530 3448831316 6466490860 9555121077 2226850350 5409368844 0165803613 5388376663 3842545810 4296652132 1753068432 5547767832 1205660254 8694960939 7819243733 6815645791 0116594278 8124710493 3470064178 6710553411 4678384387 9655730549 2466849208 4633685202 1685706876 2657864268 5412351379 6756469799 6775689220 0820824518 4129233773 5178478761 8434509948 9279949762 6267435387 4171973619 3120851851 3049915048 9316685968 9884999319 2180172118 1987166021 3698546464 1360005444 7922427176 6328111280 1571941306 5298261896 1328696431 6303726788 8148643963 5972098318 0879077984 1298397015 9083153479 0870511859 5451246937 5794628125 5407944294 6072149723 4414590250 0730233633 5611353598 0198493281 2409486073 1426470848 3266365305 8886344132 9769073659 9720324706 8811175485 3757677414 3111764241 7503783038 6332194504 1379222583 8281457759 0248827803 4666663300 8769873723 8006183042 9250413902 2646413634 7865934449 6324945660 8616147307 7905310136 0948406943 0034042395 2643663357 9087939713 8478993169 4815259003 0577081848 8040862058 9782411703 3206721702 3901607556 1532165830 4526482720 4671848447 5989605663 6833831275 9213400611 3112708947 0128873710 0575349802 4380086395 3855168401 0031317234 1992715908 9191214026 3546978215 0088838151 3267738530 6014968361 9332692486 9273338085 5155390155 4906664100 2076626089 8200607507 6561970593 7676591862 8869459814 1157465197 6464459435 4684318621 5369356728 5076249221 1738397047 3131739100 0925591374 7509099932 1881247283 4444784246 5169724563 3318629601 4028764787 0888393809 6974877689 9965912920 4374192325 1570748086 9565156250 9441019510 7339260916 4108706348 0107189113 4591725827 0282731624 2034610737 4130484790 8183347418 7299993718 5580753815 3267090608 7785359644 2757309908 3145944620 6051683093 7808857497 6412266307 1185232868 7804889216 4763453909 1014435297 2027334306 1445654190 1315533428 0874707199 0608016509 7860549831 0153472077 0999516869 3249999274 9247294772 2956153654 0041548633 7770019239 6274098334 4493655716 4969780942 4787757137 2029644559 3602959171 3794624705 0236570339 0175219209 1950931173 0110741830 0485143932 4442864368 8328569929 0042618305 3305704502 3100739456 3044110982 5001082119 5936312406 2593153138 2415221838 7494422656 6643996309 1417150651 8649202896 1327410512 3006924253 9673175758 9322407149 4384144478 6995303958 1149857338 1289320656 0804680452 0778939565 7786087953 3941815975 7752673539 4486499819 0876288540 2981797688 0470868103 2706195147 6492841531 9414323479 7429600841 0678792988 4720203716 5501523821 1751305913 4965978111 1366590676 0516275491 7358390741 3114542217 4401629369 3358146267 2534764288 0948978980 0551580048 0703489939 6178188753 5937459138 2116265612 5337298744 8581118688 2094280211 1559178349 8690866803 7668642653 9996345963 |
| 7365740 3840613389 |
| 2972 1519443449 |
| 7 2283998463 |
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) = 50.094223%
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.
Pocklington's Theorem states that the above information is sufficient to prove that any factor of N is ≡ 1 (mod F).
If N is composed of two (not necessarily prime) factors, let them be a·F+1 and b·F+1 (with a, b > 0). This would imply that N > a·b·F2 > F2 > N, so N must be prime.