Primality Certificate for (4800^4007-1)/4799 | ||
| Andy Steward | 14,748 digits | 17 April 2010 |
|---|---|---|
| Originally by A.A.D.Steward 2010 | ||
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.186711% factorization of N-1:
| From | Factorisation |
|---|---|
| 4800 | 2 · 2 · 2 · 2 · 2 · 2 · 3 · 5 · 5 |
| Φ2 | 4801 |
| Φ2003 | 4007 · 1101089700717863 · p7352 |
| Φ4006 | 48073 · 733099 · 20228107708489 · c7346 |
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 :
| 15 8637431850 2836159980 8572813697 5597458857 6747782411 3578220716 6070437152 2253855259 8626270651 9350039800 2585015477 2848392105 0813853945 7784668310 3450537632 7579903993 6709369410 3334941995 3867050057 5325524920 2754114134 7671454745 9922986951 2417939314 7290831596 9204321001 4367654019 9583839206 0257866305 9355391454 5431690289 2315145450 0535761666 8105239907 7062373701 3810407320 1960904023 0398578993 5503411585 6510731299 0971041481 6032069891 5459133725 2375761428 2154487467 1878562097 8555772868 0122090888 3033924356 3513085941 3834683594 2277084933 2478411676 6613654781 3213556291 9257708606 6091392397 1795952557 4362497775 7083999156 7933556218 1453367790 1291517826 6513812597 8788221909 6662225093 1090819543 9727492342 4202176908 8231469793 4047655803 9286807299 6020187599 3128579651 2512266579 5853323430 6284383858 3809421330 4589349521 6459793867 5946169321 4085372715 6898454893 7472961078 3914769596 1569328405 3624430391 3656148774 1032862966 6162535335 1173771033 4897700129 2884235415 7224675453 9256094434 6072947950 2799874993 2169022307 3794237715 4518033051 5339921536 4950465630 4539786150 2534351103 8620050540 5723742755 0126073705 8380214399 2532162532 6932346855 5933881063 1165471978 9032219214 7169102838 4958206845 4573649061 7163686584 0295599596 6292148185 7767125571 0224848538 8284338949 5386282952 7507566323 2650074625 1431792743 6926046313 6871866285 4245251942 9007669991 3586113276 3076363131 7571393049 0461945596 8495745477 5947030955 6407756892 1044411224 0628954982 7391161826 2250126873 8279431674 3440885952 2679421575 8954736620 7323195145 9833644815 5005209040 1282492535 6971654139 4333598627 3858924489 4357467372 8275997793 1104266670 5104344815 7740515024 8574112193 1858015699 3693098503 0535583131 1891778374 0143267259 7147882116 2477514976 9925533791 2059952976 1661128665 3162638585 1490090183 4354594625 1430633924 0261775741 9671890014 3616202544 5073707187 7327380955 0643142719 4263832653 5824497824 7346353067 0355378213 8917335231 8019529169 4576469010 5029842947 0311616378 5603731966 1028238033 2927748942 9431653495 3487127890 0189925423 3807794184 4478273536 2134554942 7855048990 0313617112 3918177827 0627062117 8777793940 8302774598 2483023053 0040083905 3253974266 8269773640 4539817973 1153741728 4865825744 9696145100 9695676114 1604189764 3969870423 1644492227 7536656026 7365650569 8766835570 7131555780 8505882481 7267133327 9116864688 7771697183 4659819041 2201675128 6173339553 3546275440 3457286569 9743890746 1556351901 7527286993 3084289241 8258523289 9915391126 3807358156 3903504751 3148844218 6557248925 2209953440 6283935159 6674020909 0913717459 5334543368 4421470802 2973982183 1605093940 6316512341 8612001869 6687902847 6832710693 2165880984 5206752681 1203099335 3115586034 3824713194 6245676548 9967087372 7383822879 5677167068 7579728254 4374270979 5852976870 6521190756 7999658876 2598912595 6940746038 3773318384 3638138140 2303988239 0075838881 8709029026 8455605281 3845343673 6282949849 0855143748 8101502260 2845813232 5839178525 2935117417 4592747434 1750410268 5281547367 0017930583 7922777802 8492685356 7209329510 9051821076 7981131919 9675714619 4581951945 6646160330 7892511225 3717815848 8527879650 3127116798 0715259279 5465368327 3539847454 8290629729 4292866616 5816480558 8711187227 1972589155 8224899175 5561088281 7938617646 2413347549 7996850910 0775634544 5092526381 5471075170 9033619644 3366547138 9980322491 0857806910 6698060310 8065678085 0435418822 9206835490 2014590008 0573153014 8181637367 8491218325 5238387385 9508935132 4000282382 7329294384 7320190875 2535756756 8234600935 6366786465 0053877422 7626644789 8649687749 2649574256 2545633536 3134599368 1888575353 3602842534 7805416074 9128744645 5347813552 3845355014 5534852703 6401233970 8919615788 3818070757 2200508831 4956485722 9294100031 1206311145 6368623202 6747673547 0651831948 9589440333 3273315954 2346548154 8271331709 9563701362 5813612110 8566125223 6234845594 3978701155 3378212143 1746300232 7895581006 2443947326 4245594665 7010292192 2286378182 0314699731 9056463317 8412015870 1739781704 6722639279 3187784210 0884408401 5100095537 8425121939 9619294075 9362379233 1249602836 7936964296 2429348311 3948162889 5619996252 6720411643 4579304283 9941908593 5537517662 5819042032 6236907279 9468552330 6998996140 4355542650 8336155607 6039141629 9445334618 8557785548 2524306004 6809524284 2175093848 3116420562 4869643742 0358318306 1286245802 8312915246 8809221164 1864562468 7084012479 9405339040 3870652640 0657051534 2892978033 6305443479 1002712451 2906802229 8005419375 5539804490 5355965098 7091024488 8102632479 6599124056 0987095940 9176397817 5161899254 7546944646 7778469050 3124383892 6137861090 8535358768 6363110132 6091969144 6129467921 8642210900 5069924169 1585844456 5033721837 3570062221 9236570683 0018125834 1859867533 0167614655 0759652172 7653615738 6127444561 1622456572 8812292976 3592697443 7917842367 9485152035 5174224980 4787054755 9583764064 6449210269 2800679299 9663715633 2413866850 2734328035 5410211621 3634077457 9965558559 6114559526 6757395316 4437325848 2042788920 7383874269 8355079627 0490585517 9829008277 2816344407 3932783198 3114510996 9098105098 6556137916 8449588510 4855926390 4904583046 8375582578 7064681549 7475233351 6083557387 4297366132 5985779523 8251428550 4396384784 7137910405 2285325827 9804137010 1478535170 2218544808 6517579871 9192534411 3134412618 5943974997 7577622072 2550034516 9115035343 7921823255 7150798739 4274883361 1795851370 0133885072 2423533922 7016194274 7405980127 7967455402 7142153487 2748406712 4404883783 4544966474 5367155590 0366734301 0731153146 8213915751 7363738483 5590291297 6373335131 0373868916 2809174911 7775730013 6460713228 6517445999 0187216989 5550927907 8629297419 6911609686 9519877681 1117589601 5290225672 3594670550 6522006149 0069907826 0348146757 1756581853 5559221031 0473960031 8351135288 7509133142 1740533378 2668546841 9844115300 4068234413 4176513176 8275420335 2179156240 1994397898 8608176127 5403653003 3928891128 4247317140 4795602510 2254853172 0428131370 3217406266 6677654928 2533106359 5053153529 7152712227 0709016927 0094310490 2458008726 9112016356 2708218771 3771929433 9104898614 0268494865 0602066252 8493196092 4413508132 4191351620 0350934435 3270027249 9610234667 5283058763 1158727898 4761213768 3584136288 6742249030 7746348200 7404805428 9188180795 0059463145 9725669461 5135683293 1031624644 2920858234 3773723471 1110098938 9493241773 3937479398 5647829523 5883247790 5947669035 1733779206 6104939827 5866260317 1772394923 6125063523 5434277110 1528922780 6502790964 0646184012 1233797927 7524078525 0006396386 4497971363 1077880731 7684517065 9812375309 1118432641 9532841184 1881143874 8539229501 6920873491 2147566130 3215670128 6302088775 2072903571 5874458470 5851324375 0059433323 1325147110 4143128930 6123707064 3717469459 2643578553 7416625055 7727402465 6479958076 2842575503 3090743039 2209776036 0298150429 5737666220 5108407733 3427438955 3212409890 4987260849 9461934744 7925621751 8606446849 2915809077 6797751783 2896262273 6051272732 1296575697 0290295293 9214865141 5627680358 2386648763 3872334969 6682191784 6317853337 2127349242 9356495156 8501127066 5540509272 9477522854 3103572163 6612162584 0234959512 1145705482 4200429919 5908291657 2611310721 7843665661 7936511756 5176300007 4282918257 6700495655 2654309881 4704199719 2604685048 3577459450 8013849188 5096935302 6089334346 9954491645 8259180978 9137869477 1448447377 4263641302 5556128835 2067152769 6321315476 7065605742 0004573008 0192170806 1195248853 9302500156 7919479108 4018316664 5713954967 0565398466 7015618549 8348577445 1687682533 4753538461 9336105477 0288455290 9594337657 7300497784 7690165728 2877915430 9508923528 0564840567 7942005218 9503825703 3308841938 0223914758 8884002807 7646267737 8970400713 1168979017 7699487666 8592387640 3412885544 4734283327 2597753540 0041510319 2596914390 9766583565 4078455872 7524838596 7654814624 0453109854 6812667849 5706762127 6828971456 5744250577 6409948999 6294088243 9816346275 3265191119 6673313361 |
| 110108 9700717863 |
| 2022 8107708489 |
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.040835%
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 = 17 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.