Primality Certificate for (398^5003-1)/397 | ||
| Andy Steward | 13,005 digits | 12 June 2010 |
|---|---|---|
| Originally by A.A.D.Steward 2010 | ||
| A066180 #670 | ||
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 52.158459% factorization of N-1:
| From | Factorisation |
|---|---|
| 398 | 2 · 199 |
| Φ2 | 3 · 7 · 19 |
| Φ41 | 5003 · 35999 · 2090035840713415644258977 · p72 |
| Φ61 | 733 · 54526192367 · 3242630590744214767 · 22661284695004767382913 · p102 |
| Φ82 | 83 · 212872585973 · 4600785898649464752775709722421 · p61 |
| Φ122 | 141277 · 553161760747 · p140 |
| Φ2501 | 7386302479055761 · 500804952853780772207 · p6204 |
| Φ5002 | 266731651 · 4847718313 · c6222 |
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 :
| 1413 1384316684 8894027804 9858503280 4942041792 1097190889 0822282936 1863600687 4675872620 2659872014 1976856941 5923616540 1258702621 6352168903 8462083585 4545210207 9952802564 9028376008 6591355996 3034799151 5425240714 3900703784 6203857215 9263684676 5738685547 7632219293 1874865267 1298171324 9739807439 8701465673 1989053440 1166099143 0002693643 0236556249 3557568439 7247374553 0390858249 8175516251 6383183604 2977324887 0307117947 8288309603 3093282605 8038593492 6831022706 6084583625 8038902448 1703933229 1874355266 9748304814 9472934253 5538349169 7236862896 7996446812 4851610490 9807728005 9317866659 0664277255 7296851141 5563432420 4675144621 1996272501 7006744402 3827945325 9034212455 9951889412 7926648044 0347017838 2116351590 7579359846 9845503906 0475861735 6470557812 9976710666 7000277102 1748028653 5162213485 9548889058 8684822785 3532139810 5942654483 1426437498 6228674713 3996833360 3465024231 6681102984 3971010101 4954912104 2064913671 7074256281 7847111275 4376000039 5360886563 8656133758 3349686756 9180721167 5646714894 4594519039 8064174786 6810333568 1125994448 1956409565 5293623782 8564945089 0157457512 5497396598 4865086685 6423066188 3144924937 7840395362 9323358222 5265576225 9422624637 3704026606 2105483226 9233756938 8072099520 3850231131 7855540936 5560239949 0493156638 4044777568 3393199560 4000025958 8476801928 0896391056 7950384711 3437173807 3084772158 0551819245 8020384172 2755907915 5547617183 4132330914 5179595449 8157596505 5252787608 3937334073 0065083389 0659110422 6140497737 6381365223 6192381456 9285402665 0335763845 6511322323 7200272577 7971513662 2204358767 2008365111 1533372570 5660279925 6633631335 1948842720 3359191491 2237703006 7760873394 3100177734 1625486005 0151719269 9660544487 0870311877 9120645204 0766288060 2833728029 1919819968 0208766183 6563385804 8410108735 3666266669 6687883861 3889904996 8446883176 6743581833 6557997043 0314576078 7818071237 2729747045 8626583739 9535273481 4211359063 6871282371 6100526934 8697654311 7394313399 2791769229 9818978707 9002545939 6619697482 9686384322 3602641670 3928652594 3698130210 1464669645 3212898084 9949467702 1645855984 9983675530 6131878517 5767084132 6071011431 5730018232 0006832557 1285288651 0628799015 9777064013 1260194975 9310494505 1808814275 2443196443 5574674916 0689957289 2343167759 4218243113 7547948470 2697458800 0136761555 3991308627 4429882102 4712623176 5614620660 1069315989 9906261238 3622001207 6444361141 1822182185 2685591062 6143599639 0525225904 8585033326 1319200124 7572034798 4074585656 7219768233 9196623380 3455597494 1335401141 2070886277 8209600753 4920876044 4170336289 4226127230 2295538130 7897889421 5681206744 8080364514 5189217723 2005261054 4240506179 4534134088 8021126343 9515707939 3683467729 0331567836 3580393492 9975517378 0573214545 2226978357 2700159440 3195103805 0269358511 5026497773 2808908130 6599333913 8674618211 8607436543 5464625938 2730711369 4696329525 2564154091 8249317868 0927425316 1850668567 4630425012 9976445104 5133617270 3635293587 0433139241 2026968474 9504716827 1973460624 8614786010 9096386831 7735098006 8251387010 2793134142 9779856381 8500546966 9212017973 8807040271 3116534250 6531756178 7507270068 5695158665 7291846711 8506443636 9567222414 3966613520 1628936457 4503467268 2107181460 1819806894 5012712516 6730318205 7869697705 7892382398 1621290704 7018534899 6118148523 8799695955 3651871281 1783659068 3726562992 5975240109 6569344988 0450194851 5689237678 3529943450 4701776642 9331054991 1863172436 8940118311 5539395528 4802518991 3571394504 6419714727 6973390085 0996262063 6442896364 3917320256 2453571070 8698198117 9045897893 9508315282 5827418922 7297120934 9752656615 3863734092 4276197488 2015335347 2892220596 5514484368 7379449436 0682775534 7267653783 9351804916 6114430443 6070233252 8137343697 1072927644 6999165316 1864004555 2197783671 1043458427 2324717081 2365050501 6091870690 4539487901 2699143420 8075548317 2329451640 6209748063 4899575569 4213859161 7096342449 7009252555 9022883708 3247020164 4330234455 9448850846 8690333810 5334830401 8085322868 1287662555 1341397264 4057260588 1414489935 3915549675 1494574683 7875750194 6937779013 8261274454 0733337653 2658312959 6911412442 5742531786 2087393608 4203326485 3557698119 2366713270 3278680090 7255467283 5704137077 8357809187 5746934122 3611680349 1293444832 8242852477 6695697603 7160011426 4361899180 2876781203 0100851379 0168752884 2278245566 6388450228 2242228414 5708547247 1203231843 7437631289 0946732541 9340519480 4337260910 0246970559 6641771444 3671122746 2502488444 3211731744 7207585211 4644740421 5430246318 9928565943 1302243452 7172040633 4753763246 9860495927 8932276613 5510837475 5202811003 9540063804 1507851829 2017364696 6584210572 7555067568 7992150126 8015457524 6136852231 6406397217 8008285907 8716757454 2202938918 0759099349 9554143036 0755118730 8264402748 5831284622 2981661937 5406659431 3114464073 9975592554 7705313133 9746029611 4395078034 2265289070 9394709750 0812778841 7020969954 9159624447 1046764976 0683297898 3900339968 4461432107 8202121248 7714693899 6022210448 4340143550 6898892149 8767949638 9786193333 7507106087 9126507711 8489198416 7015979752 7729948943 2063651908 4103258872 8665544181 1361296320 8803621626 1196993161 7909349201 6867205300 4737031947 0579054531 0213636556 9967565743 4059077047 7209383856 5372085948 5025229340 6676144780 1896247871 3648289055 8180696350 0771878715 5544681922 7586410701 5136653401 6555249197 3260371162 4800494445 3321461883 3287324010 0106919461 6478652352 4025454950 8355538861 8146515838 2185957082 9357044211 1244205724 4889282792 8061982572 0265268898 3301039245 1734555297 7765979867 4765683135 0945079817 2107256901 5552095465 8104112995 9218741046 2782678356 8309000208 1859194079 1028345005 7747313173 6366040126 6663244260 6999459770 5032621120 8481602971 4604120509 6473818913 7028791130 7704263766 3364028755 8476379333 5401749533 9422443955 1404905458 9602945440 5755527399 6668242583 5166948210 5325915580 4663639181 2266188709 7283010140 3864494254 0157546839 3684099413 1377845833 6418652264 2383301437 6248510665 6796339081 2294115424 5071858040 0919402286 1268210719 9423724074 1392572669 4790104909 6302068031 8403302120 0712764319 3816754437 7386382295 6899841608 2211152346 0551048446 8816158202 3703906770 1390258426 9605082743 5326092733 5605422056 5922280258 0802814196 7811142205 3499393356 9242091065 4767603787 8408391311 9423514391 8053085409 3275354960 1504392358 0524123881 6103593000 3162312726 9826910551 2275402083 0791194232 9205084524 1991939465 3499817104 2280212569 3894452456 2831589450 8490541039 8011301747 0830057866 4216502249 4657214508 9830995725 3612127037 2763135652 1376548010 1876088519 9319337368 3761404098 4285989798 5778486896 3002220520 7160322002 6872473643 1791681319 5061119213 |
| 1255945766 4006689336 4002895673 7465846958 7164851155 5096466424 0220618759 0367422626 4599889661 8456036494 0148595217 7524439712 8254568801 0417487729 |
| 33 5881234942 6685089019 0433490751 3326955557 0862595529 3445553876 8757677380 7040614674 6385474460 7705154071 |
| 26 3475826113 7869899984 0630148868 6632263428 6056519568 8931935332 2137133679 |
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.099103%
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.
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.