Primality Certificate for (20250^4099-1)/20249 |
| Andy Steward | 17,648 digits | 13 February 2010 |
|---|
| Originally by A.A.D.Steward 2010 |
|---|
This certificate uses a theorem of
Brillhart, Lehmer and Selfridge
to prove an integer N prime
by making use of a partial prime factorization of
N-1.
Factorizing N-1
As N is a Generalized Repunit,
we make use of the algebraic factorization of N-1
to arrive at the following 33.607568% factorization of N-1:
| From | Factorisation |
|---|
| 20250 | 2 · 3 · 3 · 3 · 3 · 5 · 5 · 5
|
| Φ2 | 7 · 11 · 263
|
| Φ3 | 13 · 31544827
|
| Φ6 | 37 · 11082223
|
| Φ683 | 313387721 · 293992220671 · c2918
|
| Φ1366 | 1367 · c2934
|
| Φ2049 | p5874
|
| Φ4098 | 4099 · 28687 · c5866
|
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/3
:
| 9198 4813460248 9819264299 5304414837 1861704668 3712284213 2986550112 8716308214 6599023632 8697279865 3756810876 9718994481 9954522749 7436159995 3425264420 4522381712 4410662684 6686891393 9586988163 1950135705 8706054267 1695752211 8413845984 8552173675 0253355552 2234373586 7488774781 1090020708 3964465160 4219236414 7203218484 1579033364 8274783535 7845123839 1707126854 9023347208 0118788667 4546347863 6178927600 0458848833 1868171509 8736277718 5868050265 8348806486 6428906297 7550973265 1531266242 7345532674 7494147673 4377444485 4241613423 6407959111 9342924170 2199330963 1259658866 4813251674 2881074007 7428587487 9205580440 3569982484 4461741439 7127824033 7790935690 0777196302 0383054047 8442279758 3503438191 3786814675 5763220928 5861166295 0025968385 0901149190 0547982395 8795289756 9358258719 0977473152 4147837838 6814907710 8212307714 5289385403 9868470821 6143288655 9771343851 2158118533 6198918609 8697020787 2652769067 3333198225 6931815380 4118320800 1204631274 8282844544 4592658862 2002641671 9446330031 2330051361 6896016608 1404485722 8192797254 2281457947 6582454559 9347488335 4271461165 0808718947 6702453592 2025957180 5875084061 3945428312 0534088972 1512901601 0395464238 0450507994 9674851861 7355089661 2546424321 1818784278 5604676939 3066867394 6491906815 5482080553 8959638200 4429276291 0004740416 5814071829 2260137931 3654797113 6254117317 7541068694 4693338066 1511960559 3413623405 9192221142 0835051392 5326270503 8941057463 9835273936 5949468762 5821503449 1695929709 4296737242 3166651707 7033590894 7505373776 9961800476 4836195388 7654369389 5717371062 8147977340 3365649503 5695121798 9363204324 8835814890 0437452888 3953884290 7210649692 8054548309 3490092761 2689625231 0838483724 3489964287 3138152670 9041321195 1751271538 2070576514 2917863332 3743571061 5076229992 2616823161 1351572503 9503412172 4537800350 3045247115 8778241153 1081627960 5826191496 2877416718 9329390239 9288841343 1158373944 5608574529 0970540202 3862359727 7230078439 6211566490 7877586598 4414007182 8910704509 3032906567 0024445187 1286833233 5573792152 6169332326 8145592210 8877578501 2456465280 4258011371 2494336978 6321396743 3498233763 7524185414 0536144212 3826196804 6035426764 1125434703 7581386883 9205024380 8816839377 7509284670 6977669768 3686916116 1661290356 1434821829 6415000986 5143860435 5218993260 4344510215 3350690679 4736595603 4901218160 1853317709 4787947135 2400440143 6089723185 8434211727 3227697373 3183869347 3029467762 4042923735 2134788327 1186658532 4918280631 5644160353 4661853227 9545451950 1357241044 9606912867 3813612973 5341786108 1201778984 9883919150 8442663218 9821751399 9883275834 5883124844 5926667034 8798084873 1706383583 7719542442 8730488051 9422736831 4824023961 9576959610 1685195917 6608674655 4867124337 8514849311 6656668244 5860892128 3677859491 5110596786 0871866052 9028728741 6987995578 7935613438 0060141545 8571873353 2956620052 5447228853 9257395691 8488825516 5872991377 8935732962 4502756307 5612258029 2713031120 6448010767 8880792006 5201243171 3962988888 3658885456 8342307637 2148256265 6574108025 8540982949 5879518344 4103369155 6879841901 9517769026 7279957926 4459013424 7996473128 9760047127 4939324349 1445540605 6743167166 7951317272 0541618815 3944486600 7533696848 2626627329 3901758297 3086027059 3058472231 8375696639 3254103616 1639502613 3298515257 5904268527 5365981381 3772935700 2247545521 2566619861 6003933786 0896794971 7954405744 8950268183 6913540011 6080271307 4330412016 5327800103 6690489826 4790655357 9798101222 0429669803 2579410198 7817782858 7018866714 1904301088 2280708481 9482662229 1714262798 5065151608 3880672087 4360578278 2526704776 9815080116 5023114446 6492561081 7846428593 5733080048 8014630318 1706172720 4930569896 6897407580 0696735731 1477948902 2457422507 8085345296 8411174021 8742981900 4802822819 5823141773 1228303920 7263506764 6250973044 8717546957 3152140356 3042453316 1676426872 6096914207 4449680723 6408421658 6032082234 7687913816 2858380819 6395374882 3952184569 5025061634 4156560361 9901505967 8845352764 5017601628 6810801706 0991807513 4456526379 6283981315 1505794713 7774527991 0071797125 1654113517 3087557078 6489587126 9589543946 6031800556 0874347099 8848792200 0795737163 5113392883 5836529165 2503042906 8496632123 1709292987 0096541379 4289759271 5264170601 4647831550 6513307565 4832919558 9017468283 7718229255 5844070232 6096613660 1321064349 8965745381 8365009278 1126197340 4334412556 6952039054 7750143843 2316275666 4588880510 2892880649 4608603626 4074827496 5693820394 6934945528 9487319046 0463490583 0911469633 2467361421 9206367189 0071633705 7731672147 4800428118 8475892966 1267994168 9730649038 1888145838 4094274849 6014806354 9725090697 9131700788 0498226435 0468259199 4310452492 7094849445 4047721365 3421201371 3921397497 5120326906 8960657757 2862973951 8541110258 2955439047 1765343108 2720546514 5340771415 1779963684 1892811349 1687855705 4531440769 2962725436 3013085079 6111980428 6097251146 7869657350 4403687339 8838055838 2792213582 6297613234 0232836555 1620932972 9842843238 5422009376 7745238056 7164149488 8283303097 2880241510 9283248048 3484804028 6731138443 4909915528 5865215665 7088726319 2508778130 4011622202 0918645044 7683693634 3448852290 6809169021 5368486975 0110582499 5839944600 4195348695 6642962926 0778200690 5731078116 0876891148 9369860789 3383054517 7690325607 4555701544 1399971766 6921083227 6142249933 4824598127 3792611847 8617146549 9706628018 0309626636 6223488827 4381296706 8800299827 0672067881 0046917824 1535764692 5987713580 1762957177 9698987802 1385695899 9520573459 8292983034 0485929069 1268792038 0880916868 8253050797 1870426940 2012282088 3583562889 4657975713 7008305916 2856620614 1160031381 0809370033 7081478464 8184336824 2523324274 1292476356 8024347359 1016755542 5904758427 6472043077 9591604914 8821672823 7857534271 1744537628 6992378277 3296894899 1468309770 4833725132 7110805496 9129876911 1115331939 4309271983 9854956493 8906684226 7647585108 9869420038 1034802412 3550614787 9894611807 2642367735 1891350338 7027366093 7277510606 6336352684 0952156995 2597201534 0874456823 9594159374 9208924907 9388857299 1942301908 7189063458 0726366615 6980106680 9562053489 0529935993 3332089844 4714149900 9306051012 1285252497 7330733913 2632769526 0706051984 1274669950 6997796159 4390494127 3669908637 5374027862 9763679087 2971879765 7987814269 2229452001 5059106936 1998110474 0491755040 9234354751 |
| 29 3992220671 |
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) = 33.349514%
Finding a Witness to Primality
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 = 3 suffices.
Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F).
As F3>N, N can have no more than two prime factors.
Express N in base F
As F2 < N < F3
and N ≡ 1 (mod F), we can
let N = c2·F2 + c1·F + 1.
- c1= 541852302 9598301135 2883623399 8064639876 7474137756 4671333213 4250691697 2256640674 6917226141 2140690958 7281357704 2474833946 0539028047 4926651952 5566726864 7304879549 1511293066 7335735861 8509971315 1926613647 7853680433 5398134216 4440874272 7411891128 5539414855 0827884432 1774938226 8448471409 1675022535 7861762767 3234216755 3928300480 6639317476 1127538896 8082786465 0317573882 3895798561 7506674483 2608973514 1327430977 4157149859 9315686901 3419965436 9956404542 3884537289 9864411279 6393740032 9762745726 7361863998 8306098467 5459798526 8698337600 5276876435 4715332360 1463768882 5432212889 6306835496 6146205502 3121140787 7933920908 6488651833 1421415281 9331450083 1180490803 4828917619 8644541084 7889830906 2665280773 1930996706 2635950839 9698595607 1605245579 1014302517 6331103983 3187405066 6238036094 3421165149 0238994007 0995733764 4700455790 9043994001 5408056876 1458895223 3869768685 5553871706 8486925553 6602871929 1452908990 1655994630 0839805517 8609735543 1954157299 6495802226 3585798098 7299805485 6135395933 4836718894 2651870256 1957352480 1547139202 2104725004 7202877405 5911383292 2842692479 0053905332 2029098710 5659136861 6811151134 8382941408 7412201788 5949209822 6430301849 0626976583 3409575179 5576183925 8655317839 4076719200 4778290446 6381231830 7894871583 8974371764 7979348075 4084275712 6484998709 9020330298 5342140809 4838549594 6816051098 5960033849 7394855687 8633606722 7949056370 2440401882 7398099128 5361490973 1319571409 2639520839 1984414865 2607807983 5327223652 6063939459 1964178201 2206347654 3448227162 0626048208 0784034502 4722306014 4705524474 9200819919 6460660523 5333923416 6190537737 2279414929 7932145276 3148845778 2182815080 2334840151 2018185845 5529416923 4699568549 6627994671 2062557635 1628978331 1378471052 9412980705 0707903985 8270622680 1701329655 1481483957 8596007937 7998098615 7272741561 6075867034 8960658703 7285452344 9050942166 0934953334 9119002354 7517190398 5001095205 5034408808 1920353349 4722985880 3704250539 1291293627 5643256644 1927500517 1975012010 5947008361 0274350267 3644967824 2660952200 1161630808 3586631802 2632868379 4528077020 9026818761 5301212509 8108656003 6045104278 4237585639 4173173323 1363232880 2479149899 7500183870 2109004212 7735060464 3676539991 0769284527 9364256729 1747700884 4911929157 3590446103 9837202158 7925056793 8292474699 2846640926 8081515768 0032984574 8161979612 7343378726 5634065730 4773977108 9684712664 1609786249 9466076787 3130593647 9491713136 6972361663 4871750795 6150418872 7127476511 7895829897 0330636792 2595092566 7116499415 0201411044 6390754764 5256783109 3748992533 8107919633 3446223677 1335328294 4465979223 4536429823 3439417866 5457405102 7201077998 2410570730 7256790607 6227094644 8521132998 1824443352 9121265563 9331795285 1438738928 4290987105 4965265739 4242265897 5805967007 5194800810 5666848114 6397973764 6707814560 1151563911 9204923253 8050939897 8334136839 7135295531 5910941444 1110839571 1930826415 5415461747 3829298811 2271193979 2266530142 8992755243 3972097219 6716169533 6750060094 3336119224 6943699658 7266079694 1481103994 8800272169 4340096437 5354318448 1972479974 0639679655 1141887647 3471853220 4666067953 0544754196 3888355500
- c2= 7339735 4815986732 9406283454 4920118242 8229231822 2088667301 1192026454 3464919364 9263759773 5757971491 7464930622 9132619995 4419821552 3529185558 0495041579 6489491245 6061258656 4880687117 7577478135 4914917947 8742536963 4744412434 4360526893 5516919805 0908963776 0439263426 3903932644 4085988683 1407925377 7604734478 0557114001 3883730320 7222509946 6796019432 4784222059 1874561725 1602508397 5682953551 2853992778 9090697692 2609646655 8618754478 3651321312 0430886669 0458032284 8075576990 4341484924 3462533147 2789915700 8163219435 5136463458 3183290229 6689217100 7313789486 3112068801 4971354160 8872342215 8267558943 9944214922 6311864252 9092507383 5255419714 3906908664 0983262906 3186383292 2926594865 5810678268 8724934928 1845624886 6391480602 7456868948 0626244871 6126614945 3634632787 8113700367 0776252681 2344533199 6518602698 2077003153 2254329353 6575856749 0543200669 3776340422 5097070003 1342610984 5062220290 6389140391 1282647179 3295384514 4369548864 7254286282 5042584013 6337438222 6822032259 7346492495 6926433994 1739601058 4876852433 6143458359 6576687611 1745029270 3793358596 5814457818 0582743038 6580884912 9981610881 2252813648 2560940884 5255536243 8694164999 1019560647 9829178337 1289201174 8589329042 8014360392 6993526012 9808174519 7194379386 5388298537 0332260677 9500936898 8133576169 7281261225 5387480801 6771246657 1384784569 4246068098 5098865118 7886030991 3961025000 1649601996 8950416853 4071812342 3588603978 6275219663 0300904013 2396234823 0396417557 7950055008 3075126089 8271663762 2956995944 7718578586 9949308411 2223258876 1879199368 1455860953 5650754845 5014266884 4659789320 5555947319 1814320485 0680476859 3497143884 3481170785 0540034457 1911818113 7320582954 6446184814 5309609723 4082152237 9938051831 4364337304 2749530707 0590567705 5668138617 8913510366 1570250820 5297857971 4535483278 1154927182 6370378290 5765257052 8082646898 7277658596 1161443866 7104427062 4488195338 7522444964 9154706635 5199625578 9167941536 7897825875 2414312564 5085784620 9783843292 7022670125 8368034786 9029243163 6374256025 8525817722 7634681151 9513604705 2294461104 5288771282 9121271981 7299193461 3078406587 7006201502 4213978497 9317410200 4504174178 4758449651 1699787276 8100359023 9413346405 7287291049 4786713904 5151913597 0322727441 2346894208 7083620422 3091838161 1803080475 7548799280 6093447436 0196203855 3976002935 8647012100 7644878338 6972005076 4445670631 9870068721 7257193749 9430271895 0169567426 2213354712 1272080119 5307636370 3537140355 2797697906 8381903351 7257772436 0870929055 1332727795 0993282974 1814199050 4369968685 8529853119 5092935656 4105186833 5652834733 5861763865 9203321810 7978867962 0562186872 9998568214 7254188563 9627592038 6447824879 0530789023 5301065119 2167135674 6443527968 0708527556 4777179191 2475201140 0890324400 4195092203 6742731102 7907770686 6400080924 5640422589 0857264879 0004174521 7709127221 7462238900 2405647432 2443360363 7134310116 1895739576 2614141998 6684646602 9177939083 1464286099 5542998940 3047099709 3609120470 7974642661 5654158180 5015825683 4426042689 9449027937 8207859996 3057130319 7381002035 1727980483 4868582228 3667324154 2735849724 2729924416 2833093646 6342201699 7143581237 3299507318 3732372261 6576321580 9056545346 2452572727 0606367233 9628024015 0652970488 8560309663 0631740766 1561376121 1387746185 3993658655 4710925829 0189286120 9500788521 7374743515 1872614043 9442078776 1596690294 0026198004 1429410355 4112068310 3633046289 8064864503 2020374667 1159405526 2595188303 4854916697 1171260132 8860053299 0143347226 8257140613 0515668602 9866433711 0187807262 6774707496 2781608063 0534408998 8105994541 3276232167 9346669085 0431402268 4309501393 9936580705 0176515670 9441446493 9726123111 3050870674 3428728394 5343538957 5328182304 0400926268 5564044580 1402061661 1871883226 2515443365 5447254749 1679302584 1603696565 9842958596 7835843308 5094189428 5083713826 9935311872 9532974742 8403978201 0847695571 4258722743 3446771382 5616892871 0849326327 7995956038 5862302569 4400986266 0069994287 9591597208 5534366776 7759749895 9963356692 5841924663 8431231932 4584533413 5285688263 4203382958 3144074093 2617107113 1970753314 9350744406 0395213230 8547933947 2851181073 3626851592 9508535152 8813977405 5852462996 6500955297 0041220148 6907771099 8797875833 3720263709 7318636670 5329361009 3109879651 2408280634 5825500673 3291647463 8247064478 8730641909 0667957410 1396307783 0976750177 8014749071 8562424957 1936019431 4321161113 8872643864 2414769870 8383796380 6246421272 6037998912 2714947583 1963313924 5225682609 5305698533 5655859356 6577757787 2172729400 1680258146 3264438820 0937580657 4143745552 0876562784 5433425058 2419246912 5424687601 6998368289 4103842153 0466545823 1838624414 0096399903 0780091214 0761080936 5590070437 7552589456 3673420651 0687699956 2877944463 8609417283 2707557416 0387169444 3702223068 9710794160 7164288990 8875403554 4753038818 3639167242 0223947162 9967541401 3885781796 9140516454 7942919441 9663804026 9118571406 7563212930 5041142252 7638907056 5341730894 2784850571 0136493598 7015495371 1888681997 8305161214 8534288466 5072757431 7992418074 1779172171 5278840219 2118700931 8695678789 5689794705 0361454820 6407084527 1143973514 0613460492 1127039722 0628359657 8624703876 6270590545 0726425686 4893190782 7360293573 4166295062 9626974893 2159545756 3064693081 8619058856 9387061208 5570597714 6429615206 6826054756 4353035376 8413396496 1825587723 9043878253 0857473386 9797521127 0825429102 7278028007 5255545650 5104173591 6189691537 2050302529 8156262223 0712572350 2199684501 6015559660 9743531734 7708944848 2606489104 8045479984 4847626329 8883328767 7090734429 7755775964 5895862990 4014905319 5805367561 1286534917 5592816429 3871247624 3141082539 2063515766 8375688231 0090974497 9629995979 1775170883 0806020972 8058735825 0947486469 9935419501 6938512091 4975854093 5741922142 1037566430 5264787662 8573765120 5466632906 7621149520 2078498491 9921522778 3793362096 5340112260 0869565157 9453093578 3974960095 0968405821 6296877593 1310718596 9432495655 2063384613 2963036113 3353373848 1540944775 8244116674 8212635443 2746195987 1645001354 1514262052 2017001719 4924115787 5275782696 8375402492 5198833426 6502979137 1144891100 7191475761 0248283549 0709942752 0542975476 3381617099 6847181837 8950871641 9740099937 9644270718 7227581374 2007798136 1489227892 4717797084 3854105306 0350264161 6166379156 0915755770 5465502250
Brillhart, Lehmer and Selfridge
Brillhart, Lehmer and Selfridge's Theorem shows that N is prime
if and only if c12-4·c2
is not a square (given 2F3 > N).
Here, c12-4·c2
is ≡ 40 (mod 64)
and therefore cannot be a square and N is prime.