Primality Certificate for (10008^2027-1)/10007 | ||
| Andy Steward | 8,105 digits | 27 June 2007 |
|---|---|---|
| Originally by A.A.D.Steward 2007 | ||
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.317313% factorization of N-1:
| From | Factorisation |
|---|---|
| 10008 | 2 · 2 · 2 · 3 · 3 · 139 |
| Φ2 | 10009 |
| Φ1013 | 2027 · 346447 · 421409 · 17609993 · c4027 |
| Φ2026 | 118601128301 · 595512964399 · p4026 |
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 :
| 318010 0255945170 6157281868 6955597692 6343487304 6887240788 2224666867 9036572752 6049206904 4052208050 8525292213 2579951465 6012880468 7873804856 4958865810 3294048926 3636847551 7627513978 9292204085 3722247855 5618339689 6656656970 8277903079 6606165757 9457183736 0084772434 0178274565 8313168532 1874332511 9144211969 3280982802 9257528260 3721873217 5773609920 1612858516 0340121486 9140539423 2641832413 9342243131 5419008309 2052869169 3893350787 7175537703 8576336352 7158192422 0357896918 3706261732 3149802750 3032875366 5396950760 0554380258 3808658591 7381352860 6105720413 6726336028 1897110670 0565881739 1191913843 6351700617 4346011345 6283939015 2834160768 5890207139 5423752819 2766134230 5119793496 7867256748 3836518764 5750514790 4542426654 7252775107 0035138450 2267409389 2825188360 7508076465 5349087733 9442543029 8212472575 1833950640 0829198801 5874002249 6533856464 0303018631 9485745870 6750403226 4338515924 8533480001 2868997657 0614596490 7616407511 8248660990 8810194575 7533278543 8012182043 1305254513 4505165448 2250568142 7920214237 0741952322 3716361872 1952251246 2738188635 3997156841 0339820370 4164241703 8038153137 6841858856 9267062847 9123755264 1629089058 4141617668 0514860315 9811160046 4285402104 9006153492 7222450353 8191213929 9521344547 5235878392 7958346577 4013320603 1764524505 5057795823 7993376811 7887588574 4452227660 8750790942 5409991587 5642003409 7080662415 2576430129 6357964282 4882588669 1320503854 4461122742 2304258103 9264355187 4467149856 0091391666 9693235623 6167790130 8541481851 5861910802 2407862836 6865622116 8584625376 1700819926 5817185485 0110247930 7755731923 9550268483 8970622183 1995206114 1935218442 0055056133 3103009428 9322670966 9410512605 7374886332 6424269592 7504181831 5363700981 5775932377 8616331785 4660155059 1833243991 2319277011 4718417764 4537694033 8026786899 5475445350 2456158102 6135533712 6485255976 9198258850 5432101158 1043163630 5462891022 4456706642 0870670029 8279246406 5721531824 5185428114 0058335890 1185901575 3667526153 8220436334 6158393563 7516376439 0563033422 8844279885 2430936900 4585799692 6013244536 1515765161 7573597634 7612119925 1971820128 5394719088 7145315343 1603045206 4215640411 2525261282 2211594917 7299203301 8163990147 1043641182 2539558335 9493457713 6484668307 0552295186 6498973485 3365742322 2426690159 4574400141 1026312255 0184712093 5872217978 1203390364 5360578826 4215042778 0580380710 1083995138 4782328459 5149298712 6616406925 3533129438 8211773407 8331501578 3226926278 1532899134 1244305904 5177052073 4915319428 5422896989 6777675672 3761661100 2398335471 0154046377 8428365076 3314160253 4070147061 0507740346 2362390732 7322880216 0133248059 9346910906 3666080293 8017686966 6097505249 4436916544 5129574942 3705564234 3988429487 9128135310 4258466113 7537544738 8050968422 1263711792 1991812972 9450400235 3209031998 2599889682 2062601747 7999478525 2647439115 1237635038 2824208242 5926439141 6453935433 6639917860 2052808287 0637215656 8616613157 3886414338 1269344891 9592109898 7470831192 1405984883 6522603178 0866201694 9641886955 1996950535 8604141061 6619994276 0572731618 5835001675 3969934864 7959153912 9015776532 6244034140 5073128973 9157025431 5862937133 6730755043 6306868091 8271979143 9280414891 1206480625 2586873896 7183907033 5097594724 7947159797 6548801733 9272650675 8578100460 2585691385 9760192405 8660849778 8186810038 4722376524 1443643618 9551194243 2603237773 8564636770 7919540015 0143390112 3990993911 3193522326 2038336107 3051499607 1610578572 6755002707 4667563325 1440617355 2825849269 2470820344 8698872797 3325928409 9919953979 8389716434 3730152600 5358945160 1938651894 7164344028 5205292741 6582565910 5976359359 4998441798 8012384205 4960133032 7034071273 9181088313 1683162498 5202933689 8238293808 3773491561 3417544076 5111355656 9466386800 7680425235 1508063355 0444956712 3094041893 8289044464 8261904810 0687711981 4692089067 4639746206 5612277965 8895005537 6027096943 2380174640 4319870123 7211682981 2338821002 2666704589 5549091236 7513128851 2256898784 2679605810 9123199395 7289605955 9842918073 6680215699 8659574611 1687176522 0244109758 0192360486 5505553645 7903328944 4924016631 4841962854 0606710326 1001036254 3969901577 0114996650 1756477591 6354362840 1824934555 9281558944 1622736079 9454944329 1832574207 5637467500 2030964492 8006175194 6739922301 3052681389 1886400061 9340141796 6591360480 3771412579 |
| 59 5512964399 |
| 11 8601128301 |
| 17609993 |
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.040043%
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 = 5 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.