Primality Certificate for (5585^2699-1)/5584 | ||
| Andy Steward | 10,110 digits | 12 July 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 51.047947% factorization of N-1:
| From | Factorisation |
|---|---|
| 5585 | 5 · 1117 |
| Φ2 | 2 · 3 · 7 · 7 · 19 |
| Φ19 | 761 · 8171 · 134315515689911 · p47 |
| Φ38 | 19 · 2145329 · p60 |
| Φ71 | 228337 · 1882211 · 1525191323741 · c239 |
| Φ142 | p263 |
| Φ1349 | 51263 · 234727 · 253613 · 3042639166387 · p4694 |
| Φ2698 | 2699 · 31679917 · c4711 |
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 :
| 1911 3349093310 7970661260 5102364562 2731606190 9503859488 6228683485 0563926855 1071879095 0018975785 4637282404 5214310561 0419957709 3879010871 2907282395 2541151229 7842312692 8871306911 4693607767 0150539624 5578380974 9028771520 9936868049 1313780274 0526778673 3293951737 2070151859 7864571392 8215589869 2313864756 4191286856 9128525207 2138131810 3617316309 7873506758 0393263522 4081026694 0657308716 2338200698 9915472031 6955110077 0266360663 0716004789 9422042289 5315455055 9594972849 4684942552 0092922019 0396449015 0550626394 6013372970 4975268090 1793453084 5346741473 0235693401 6288408339 9420041414 7666128051 8831965404 9270426009 2791748629 1836162851 7704395800 3522390016 4237287650 9748644407 0913163982 6674625972 1948539336 1850938716 7278223720 8828488877 7222673106 4515371553 4538535884 9983602260 8227725452 6744804920 5449624975 6941899992 4635942434 6478977991 0125070259 7561094517 0775075551 1332650510 5837160728 2199289334 8714799953 9136195441 0682464040 6911590552 0847317216 4479648979 9039571084 2313782604 4120835881 6671190568 8546233543 0476860794 0430746308 6544889694 8622200154 7168980745 8369206313 7193624160 6363331017 8373673353 6013370414 8957453308 7792914072 4015477237 1193020514 2863154209 8036858048 2766296161 5211399614 9105219728 1547822234 4992700794 9175761190 1731763587 7350694456 5892584858 0289034050 6865993176 0296806271 2085663549 1960446348 2747172038 2122226101 8720440568 0766098891 1649418149 0216115104 8187073465 4804298129 4821237588 1844723188 3189482601 3826515387 4573945761 6172942771 5523353125 9382767296 9184610526 8910024118 1367191041 1602525612 5642538307 7492997509 1993332861 0033351200 5663817885 4140862141 0089986616 0289033136 1560771883 7810344590 1795045286 3324171733 1451532158 1708467415 7918545490 3150470046 4950634564 3381182772 3815672234 3615251712 3569111967 7406828460 1029717350 4291365370 8707309557 6580148484 3083123014 4621421674 7421645241 4648967947 2042945046 1109214994 2490911084 5067252202 5327427880 6505508189 9341984152 1872817839 0054657010 8061377964 1776217608 1587133674 1297804956 6004794216 2691879203 3285822795 9413830937 9702200748 1100957827 0602561191 6975413545 4501725152 5523026588 0969801072 2828626033 8059686244 4427885331 0412613065 5335163085 7504169292 9240084391 5523966340 2052275661 7074247833 1048300548 8714060410 2893239642 9254405786 5250412820 7907400347 0203877709 0425077770 1087040542 4301553823 1712332657 2668070463 8242841491 4946882631 0442195511 2565898091 0045886401 5156745589 9661518087 2540446663 5822531447 8982248608 1849884590 9593014987 3050173267 6231384890 9566964817 0281494716 0603908795 6798515254 3319280755 9769459702 4128256920 7084468792 9962544217 1380068912 3368482729 1760216114 3877230773 3886284306 1546765910 1418807572 0940644980 1830574662 1098982880 5801376320 2050611309 7578692149 9349232934 3740437534 9000013078 7747512889 1137155708 3213755704 0453191936 8221489610 5386066205 1313511913 1829487767 5645218065 6243463975 1208642476 5173573243 9350265511 3432863697 5672127376 8619894690 8081324619 4592275394 2918884434 5303445584 1208742519 5679580768 2171097203 3243918916 8632292260 8469624103 5712983203 8987180124 7656733645 8938712150 1989027268 5820001277 0882131678 0172024717 6841255756 9744973304 5195106980 2388702317 6878989683 5080483249 1479675357 6538060934 3453666295 4173417652 7548263963 1363180365 5004937269 7319751940 0735061401 9665466066 2185320677 6640530716 0187116641 4730097277 1732227012 6579338754 7203052597 7758246208 6834428706 5371860948 7588022972 3020065225 7112298505 0777851046 3819157903 7622966433 4360661431 1627175458 2826515691 4563380359 7580410661 8217724091 4303480715 2658570022 0186676210 6630687868 4449515806 0469140336 7402226158 8980333140 7272958826 4931849094 6851404164 4096215241 5592539744 6722196983 6187921930 1900601995 2114797079 3225795372 6197362896 6558188986 3449861724 7583894961 7241811759 9312910940 1370451566 9531014755 8527841959 7708255255 9078540417 6269212656 5574899693 7148224908 6862882583 1434604967 7428178069 7818282618 1519175697 8161497942 5398614500 2719820987 5035964383 9456142754 4435487926 0805023030 3365240363 0621416613 8855812104 4458179534 1396936008 3675283968 7064923347 6980737933 9419318458 6633182246 3561980172 9849540022 2957565871 4686385499 7385733754 1756429170 9470176118 5872516647 4506152338 6994491656 5749370812 3333693219 3521905698 4419195199 2711836560 8173665327 6458897233 4777518783 2560768261 6507332543 4969543593 8967007064 9890065033 1609063596 3475266100 6664652796 0167487571 8774061285 3597775534 3783752942 8632719696 5312430851 4927431645 2061202463 7988095464 7518795687 5586412172 4921908731 7340191495 7216662337 6694689199 0362046719 9999911825 7775788810 1701124384 9154762066 3999293409 0349123831 4207847885 3133550428 0919010491 8331857193 1225675123 0193698737 6124583041 7696697552 6582288392 5570398892 9865706168 1891552601 7851572942 7310020684 3080594586 8050947115 2960014901 8805862803 0817086509 4331819750 1714215667 6814757035 7500839091 9083864824 2211231546 2441337311 7063896273 0204111292 8810828052 0571322316 0174831390 5138949311 |
| 195 6792015956 2937972240 6669258188 2154056405 4290736525 4549018740 6906640269 7114586672 0960872257 7095788775 6964574376 3854584879 0408476069 6293127800 1036338961 9731115693 3285249794 5566599122 9204210295 8037073187 7957994219 5846040149 8528345101 0337677325 8136312593 6642710641 |
| 6856333527 9052038916 0142266613 3371611312 6194722920 3731936891 |
| 3347410 0127067037 2487331494 4074160138 4283359671 |
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.071214%
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.