Primality Certificate for (13803^3919-1)/13802 |
| Andy Steward | 16,221 digits | 18 April 2010 |
|---|
| Originally by A.A.D.Steward 2010 |
|---|
| PrP: Bernardo Boncompagni 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.689084% factorization of N-1:
| From | Factorisation |
|---|
| 13803 | 3 · 43 · 107
|
| Φ2 | 2 · 2 · 7 · 17 · 29
|
| Φ3 | 139 · 157 · 8731
|
| Φ6 | 13 · 14654539
|
| Φ653 | 1307 · c2697
|
| Φ1306 | 412526618279224332911 · c2679
|
| Φ1959 | 3919 · 3020779 · 21842851 · c5382
|
| Φ3918 | 144967 · 391801 · 822781 · 313714872871989739153 · p5362
|
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
:
| 22 8720841329 5243702777 5033523107 4284533349 2068985336 9260633122 3360805749 1738110943 9082214633 7931481260 2868158345 5400040986 7263429838 3932639021 3681710131 7602513582 2277357791 4737963071 4424560113 5276487356 1829602037 3498533576 8723715474 6094768755 6101154018 5145684916 1731755228 4595248095 5014171188 6931475123 7838892646 5437778440 3349312932 1964719914 9462217398 5440091044 3814231830 2621932010 8035558081 7604279969 0442059639 6924164411 0625635067 1590324188 9476441593 9703000965 6267890260 6707941625 0833045711 4749545162 9951146666 1763160690 1402086633 5506638446 6271396817 6086137672 7062767228 5184051018 3188309962 0900814001 2518231792 3839368368 5143356801 0525409918 7087795276 0529075509 2958667839 0260592877 6657984093 5143470012 9935082620 5546350764 9579134121 5898667688 5345103935 7574712516 4873196752 1464615821 3270866223 9983853793 4227592487 4816833230 8277300641 0157487940 2427454459 7998168704 7606500946 7863314070 5491905438 8880104427 4502320473 3643200683 8158670794 8963042076 5641924567 3810608150 2956028773 5685726216 4895173813 1969853655 9438290215 1078107598 4244945750 0629928315 5861560814 7703504754 4317738284 5229618716 0365807068 0160749274 8438071902 0060939142 5577653623 5011209841 0511519151 2429094553 9218244180 2392873555 8791096027 4474440250 2184583649 6174033472 3076457682 3226255355 7788834366 7409103656 5960001027 5313829938 7298888675 8987771001 4152692495 6537422741 1150788929 8149296626 8040519143 2841704431 3086316967 3046516230 5818651073 2035580093 6046167088 4377383192 7477879340 3407027813 3200878723 8204830239 1610583538 3272234547 3480636909 7702349514 5362444092 0659407669 1909669282 5548084300 6012142610 0684965484 0047189775 1233325931 5901305176 8952449372 9111016983 7278187024 8806914957 3517352382 7854923722 5576822883 2622192293 9691792088 9687882913 1544848469 2924988501 4604523962 8366071940 6848470864 3722150332 0115026183 9721211604 4890826982 4613189057 6062907025 6866027057 5307208527 3202513330 4679151386 1228598250 1918389913 8176084619 9475152671 3487131016 5696004389 9883711561 9939984578 1703559905 3444055836 2205879916 4785601184 5748864828 8151102004 5593030997 8467044212 6419023184 9566944290 5976197182 6574380276 1615100960 0983476383 4382086928 4772510662 7877278179 0816958157 2126835920 0730353164 2438842172 6373142248 8319910009 0298949018 3334356137 3693522907 9586976804 0229337524 8202891076 3187074142 1487695757 1702359962 7091473028 6905744826 3051299333 7738319686 6604946840 7744138088 6818948784 1932793542 0202591654 3556896891 6845908545 5370930906 8736925358 3117780297 9970772822 6543650460 3371231121 7722384473 4063105338 4408944674 4095375068 7145567008 7939414279 1955150428 0725420906 2762345131 4464550967 1555926724 8472072888 3400094887 2861015111 3006636088 7075900224 4980540663 2038449686 8242074841 2837016995 4677437924 7752844099 6135368210 4548814095 0804214854 9102885258 9914505897 1016508559 0504328437 7624113436 6377992162 5698686251 7855522311 1867318180 8785688021 6806011325 5896489355 9633017183 8792159180 2885953249 1650034708 9625008472 1420327395 8569568866 4711982444 9419812887 1942041918 8614743678 7408959382 5626982405 8131532189 0775326583 7914026019 3661944774 8373515822 1499981042 2713059469 0882057912 1799179924 4602195590 5991256050 5133919662 9942346639 0324899655 5243097102 7831526621 2892872925 4294648972 6960838087 3980074414 3902262907 7261161221 4475661307 6093504006 8885442413 1302427286 5069758392 4863684649 8426753975 7679318191 3474846239 3928993545 0081249601 4060026375 8007912974 8827950208 7946739934 0277620343 0981762764 2794508474 4268003785 5000002228 7226141529 9833172570 1979532619 0562907528 5757593074 4007622938 3455293212 6789655261 1822774352 5600106947 3776165636 2570112773 3232884606 6856539220 2765492886 3212871973 5025107309 1839030239 9731804585 2560406908 6628019046 8467246539 3784890533 3464735898 0473437301 4350116254 0469416312 5002488164 5369700705 6868263123 8642145243 4803631640 4309768132 8732441631 0422501173 8074941921 0461397927 3404341481 2677425913 0060068362 8662760574 4916871270 6352031275 6756484045 1126613082 3254751755 9735578493 8485896344 5354157477 8529291718 9359205521 7709047452 6570670884 4624681638 0485386330 5417625847 3880699291 6871149625 9308639743 4836210051 1976239379 7435420958 9772857854 8407875118 7859115819 8980597596 1593901441 2237268805 7320961333 0807770560 3747101739 7202652348 9903213948 4671010247 2651371417 8543417099 6022468463 2173993524 7553839249 2383428221 9633453102 8672839617 1324251867 9901196078 7596578837 3732528856 1122820414 1720440303 4359232662 6130461199 7265319240 5117901222 1181091581 2066825860 9772310048 4690920357 6846839106 2488994937 9944127159 4374465170 3767697782 9979765168 1824989078 9261570705 6128314639 5597601224 5713138203 1773224933 6948852196 7011110160 1760648216 8561282813 2875703704 1661591608 8791837386 7711211803 1590105198 1216770186 8662296145 3100471683 9765104845 8908441848 0626018679 0742868923 5869735538 2163760464 4862449788 5390148199 7867872234 2946526895 4990203347 0465417583 8684572645 0571528464 2710546883 5780267054 4284909874 3991187285 6130242546 9921492146 0247825023 6187227608 2656955219 1155232137 6366269502 2640129443 1693932568 1666536844 8213361847 3594540261 4739606255 4478065324 8123551932 3941695178 9744451613 6903170090 8527344852 0887229661 3443971066 2380526665 5932170663 5271161685 2924898088 0978002456 3387692273 4316403161 8756635266 0664254513 6479474875 2534838260 8978600980 7052326720 1006820066 3856811139 0662137052 6630536923 4485071800 1318214873 8437864253 3810585601 6212826279 2189779041 8952660224 0681294906 1217382074 6762377023 3306424471 8357310505 7982306446 7853640785 3074506410 8213893859 0875422954 1195370648 4831701379 1299449773 4951011324 9660740156 6762889301 6073131549 3484798792 9380733506 5938129371 |
| 4 1252661827 9224332911 |
| 3 1371487287 1989739153 |
| 21842851 |
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.351861%
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 = 2 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= 6453145380 2820183061 2511004494 0435678768 4840115174 7060538207 5295970210 8843755368 2723532957 7003864881 3406043273 6080408705 9257192809 1852120209 1189510591 4918259237 3676168686 8454999230 1375778270 6222188748 2051855786 1120804341 8356439111 9433954776 5840570338 0998455179 8474999281 1244649158 3982934366 4130528502 5610264911 9702722147 6311236275 9904524913 1249696405 4827178561 9154701573 0140681162 0004576501 4194743440 4055869726 0521637238 2625798095 9668400604 4488022472 1947516334 2866346254 7488430297 4003649631 3229211072 6629500756 0668195775 6196080249 8077992982 3249522735 4458275081 8303598105 0863331387 1667276874 7022461599 7757562478 1293446240 7499792653 8329995614 5275162047 4059071689 7327147248 8517872878 8962653491 1785764848 9246626944 7863307173 3414110113 5408370946 7907285783 6819477681 0914150387 6893691303 9691127015 9681741818 4615518860 3148380650 8601162055 3988526245 3341886500 7062171122 3496783147 3369180069 0316706331 4556378200 2116220992 8889182616 0115270433 2355118191 0687513543 9594838010 5541661901 3513411769 0827995565 1636918509 8958854505 9154022950 9777762448 4045089916 3367370303 2779405213 5678891366 6995184327 4579972892 6856685137 1601911693 2941534008 0298260030 6998725813 0216926909 1695574156 1258797490 3945096179 0402168009 9087426701 3210550889 1104844635 8986882803 2388343622 2616154655 6169833679 4158654759 9664204094 4113161434 0133400536 5728027450 5783358267 9426761114 0892459458 9897162513 4623068327 6750040715 2553601326 4592413069 1831719384 7880380157 6805379490 5261738997 4448939629 6317261768 2480086039 1376528435 3808956938 0064252437 5286448109 2664600758 6568561636 7798395149 8412469572 5070759910 6664102401 5342264561 7777974934 8154191960 0576692439 8234202800 9628570464 9406913005 8342649132 6786215018 7074082441 3996735448 2556209758 0468565790 0383183317 7954485524 3126589659 2923721692 9155362654 0573218992 9520503940 1760981074 8341523551 6032005951 3877805916 6431389955 6771900643 2091348802 6988734472 9792709409 9010358233 0216570926 1578494088 1826171008 1366077520 4764496213 4164997428 7333674530 0746877529 6317658947 0357919941 7066270742 7603075441 0717983021 5639599207 3386298718 3687317127 0097393392 3468979422 5868901977 4273157172 0076030143 8852307030 1166714634 0536059933 1030091252 5950712652 7833098791 3058122796 8866166258 5883978244 7732530616 3577807624 2903652745 3448711845 2942908643 9927204750 8794838662 6211565739 0959939678 2395642093 5597348394 4697738943 0079329994 2779163323 6810523767 9795778962 2611309426 6492027260 8779436724 8042441695 6356047002 7010600104 5653515390 0976407936 3533248558 8237496895 6574705567 1326258399 2981394611 6755203295 9533148623 0823325144 6934717133 1568000899 9045240715 5386018014 7014309302 6476193955 2411367288 1506480247 3648831839 3941445383 5180340008 8664002987 2497160170 4316054239 5506893330 7435915563 8960208562 7537095295 6316533107 1685857497 6444021342 7357285580 4781161694 5184758481 4322291514 3682386739 2787887687 6508255285 0262614943 2527442405 0628488400 3311580042 8416382082 0979099326 4695252858 2508061851 5969320975 9886047190 4231082600 4984936007 4203113045 3907609494 4911871165 1528280122 6609348389 9239441528 4996922608 7922229386 9030311049 0846429432 6777363106 1036986314 0143825478 6454993766 4332125339 2952288963 7532888309 1009121893 4698602158 0058754941 8855745005 4854571853 2347395306 3554932793 3799477386 8258982181 9555756014 7876223897 7553811034 2522051540 6221806050 8659783413 6473080100 1655377866 4827183424 3960508183 3990771458 1771079443 0411964271 3207363332 1104199690 9893185716 8946778833 0870700924 9467274895 6012021227 9264058334 6948807766 3960486749 7305868157 3452439834 1315565053 1322624521 1810330292 9997547753 8546141743 2230435493 8148119207 9267207624 1193278826 6584761756 3018746618 9765598902 5313159341 5448500888 0800604774 0695472339 8887572175 2048755853 3037263742 5615498731 2840879762 7205407316 4460793638 9523268075 5752944361 5323715000 1522001897 4144999184 9281014498 1625880320 5281576085 7703397461 3818921852 2942416674 9677746375 3964001208 7881625845 0326841469 9640730314 3427068351 4205749314 7750588345 9817031945 4956182192 3465759139 1156538500 9361141301 6377096697 0564465844 9230819536 6460028469 8590585739 2720955246 4193741489 2862736608 6003544903 7083893341 4743422136 8418802768 3327955885 3528328806 6483219124 0208449048 7107575385 1666642617 2769241298 5856040633 9202429439 0335995847 8162647704 0118177420 0836790498 0643207207 1113635942 7724458700 0772098704 0211549816 6578709052 7888764186 7143084489 9399178885 7028158299 9252776145 3472323332 7227860413 2860347552 9076248630 0946133114 5295095330 9808879880 3876728208 2583030139 7370649734 0148186855 7726760302 6413861689 3471287111 2581768742 8681390791 8903417982 2474911751 7592242268 2240264451 4147686093 5254584635 3934324589 6168474762 5078650502 6520173921 9205715572 7876656380 8422978118 0664683186 6234093223 3972564990 6189796822 7040194643 5839144517 5710432007 5753358474 8603317082 4891943981 7314080578 3208228774 9825475300 4322298526 8452467245 0537007734 7639056045 4152216398 1904711979 5184582269 3564901664 3296820681 3919286922 0899355381 0218474995 5652477482 4782915716 9945650517 3338895781 0675369103 3789287105 5861856719 9660302128 9328215836 1355737360 3132388038 0463136785 8133464806 6345488152 2560263767 8497566247 6240103552 5007222620 4755608887 4042730383 9843076628 6264153418 7725716813 5287056192 9690586649 6988029929 3170279684 0692116791 8028773905 5937814241 8196112730 7519664619 9628683264 3965039340 6737779160 3060876200 0993779228 6598443167 7702114125 0998505890 0454087076 7669508423 1206625805 6830891351 5359554505 7277985891 9593918089 7569686155 9348658061 6710668467 4139836655 7676562841 9633919926 2490183484 0614561093 0438278005 5026471491 3880639914 2241006635 3911354625 1185988877 9093746332 2128345767 0621880951 5390236238
- c2= 6 2366746869 7912268953 8673624665 6506499774 7942531295 4985865871 2826070640 6967409499 9575391255 3809772398 1960551485 8965920566 1786920958 7957716600 0423537746 7106961065 9372386309 2501739319 4052193529 0304633807 0566148055 6755902806 2526127551 3202362530 7057329624 7513476480 6640309111 7925407948 6250040445 5119585677 5101035720 2049421792 4476172726 3830844162 1501703180 4512622319 0100680005 8203864603 3813405741 9348370072 6152230537 6720727126 6618582113 6494039181 7647930365 3933164825 3473563979 8040811397 2820899487 7793793530 7275680685 4626598492 2338760551 1165057310 5545116836 3641985629 5929843323 8333740977 3189401789 2635406052 4226714074 0034787773 5687303523 8013294781 9509065076 4343568588 8797350766 8306139283 8271431083 1691250326 4913161395 3861226189 0100709233 9569318154 9563359840 5243104915 7700541878 3388406622 9211171182 3698941519 0274600849 0704635498 0711220215 7424765745 0004830264 2257720769 1383435547 7740837088 5849414441 1388556114 6617846441 8290235316 2959616991 6711336551 6589761155 8467865184 9391775779 1122836930 6818972378 7461940392 9639597314 6942021636 6319405506 0902099805 1831154267 4679380912 6357645670 3566299786 3168067439 9406979080 7242594999 8564009998 5318198599 4560560438 5956770362 2164111782 7846672496 1097506379 8477311688 9996383016 8228267112 8948434570 3445727916 7661840278 1146781561 7073410492 5936404142 2164206602 9082391339 5055239422 4167583002 2983913158 0207441756 5730674478 9843540175 6066390729 6441003690 4117238662 3231022495 3051805323 2110894195 9329413240 1139820577 0177139916 8134588035 4405963439 2531624451 6968015946 3324807044 3540491638 2360816235 1106931813 6955196745 9600318010 2810576819 1478952226 1265691202 5530113388 9234051268 0710249357 5366528648 5497317766 9009647713 6096226966 8624045498 8427085550 4676902672 1120439682 5610403267 2236275806 6252241079 0183087758 4991299837 5488599579 2679360562 4338569172 2556148579 0719642037 2950456798 7747196929 6576564633 3443436065 1150692932 0988239809 3824417705 4233979819 0495897499 2899769378 1133545494 5824394502 9907033748 4971426657 6870927390 3271064122 5969027370 7327149780 0086546424 7470854233 4187397493 0975229002 7543262704 9199305909 6095780871 4380633794 2770703343 1714683602 0862900324 5758853684 0240335426 7652754146 7745447275 2564888570 4604107499 5302642225 3439818804 4023259006 9399328646 4309738606 6552835148 4794069107 6686339173 4883485811 9635065555 3198928478 7269591965 6030149622 9614289999 2529776840 8895415667 7207033366 2057209077 6602037504 1057201457 9991150843 7048936216 7241365456 4601499627 0690053054 1132604700 6588626389 1866711703 6959473637 7775414503 3416057876 9378517348 6155894579 4876504353 1136784105 6222031657 9938752264 6205178410 8675408008 2128171460 5885569535 7093768737 9073255836 8686430171 8061959871 5763463839 1701715888 7588308108 9601076443 3586959419 8330177661 7985378483 5726188708 0273192683 1120259414 2474361733 7779835312 5456490414 3885631692 3113090862 0106150574 1203772959 6409362218 0275395839 3377361335 7309182462 7552558910 6760637761 3488598865 2735523124 2013956996 8898791095 2700942307 8730431978 5462745794 6969803796 2413853323 3629405968 4569040663 7415886732 7946039427 6292453181 2452272760 8997821125 7660335074 9481244726 1078293605 0419753708 5324769222 2482329635 8531185834 5149202794 9749966402 4344637062 0991334854 0256235686 4679715642 0576109325 1542585621 4718740955 2210178842 4632712833 7657587852 8858077239 5221449595 0854694556 9123547123 2831512642 4890475960 5339395837 8212024434 0796510881 6453323940 8781121604 7791966266 8822228425 7656653941 7456802299 4952519293 0430781599 7528579878 6604361095 7598416968 6941984767 7970827775 4613528384 7130493318 9401704628 7759814210 4914457089 0423695855 1125383728 5642366073 0639150120 0550100200 4439804291 8942723462 8136178243 6451494387 7450097577 6408805789 2078104546 1550287806 8137635790 5831029069 9585998799 4460858134 1736300262 5108510416 1728456642 2453813194 6658087214 7432103063 0491130344 0090075406 8775516305 4067393262 8614457457 8304033302 8886976400 0566548844 6056564723 4805293827 1776784938 7831248409 3698775006 5849485712 3894181602 6993635666 2534465282 3866028960 1574965994 4650371650 5311134163 8226719793 4386394625 4895965698 9128176347 5172155243 3132561258 7293089076 6712321506 2919273718 4806215689 9687448121 8012681051 0891737652 7403173967 5766821500 2349502520 2680203155 0233619792 4007489140 7198627858 4995844599 8868859033 0910805359 6020974663 6458577270 7855916477 0197065633 0752541375 8178676955 4850072917 4657032161 9163156373 9739490548 3831408699 1638657625 6679703015 8936612650 4785163837 5292955811 5759341995 6867294275 5267402323 6144505012 5906660542 4643279080 7880480368 6360518606 4413715749 0220956416 7598126128 6423685258 1133974495 4626844166 9385721074 6218490979 6441937602 0384534196 6354884199 8373729831 6550125327 8066065706 2774486493 8442134038 4084689698 8293337191 3902635888 8753162020 5783584847 6231883965 5740834853 9456778461 9020207528 6159904110 5493630161 8012139084 4038873978 4145421016 5186247374 0678749252 4532297446 2576388222 7167408891 1786684935 1898914687 1177642264 7570497319 4589294442 4475078144 3891236862 1820472976 2045495863 9685634574 8670001691 2922655295 1794156314 4227446341 7604180192 1809984253 3813593687 4003928193 4023255592 7624361098 4777500195 0313264556 3773741999 6824940362 0858139940 2484735280 8858395225 4010719102 0757439005 5675052522 5178289744 1490162754 1529178227 1644882646 2687041544 5030440367 9113411069 7377017501 2807283981 7754231478 4861685218 5099051982 0599867583 9172332524 1085970201 7792917838 1562404052 2763544767 3928596713 3560330443 7128557039 3044570485 8049583090 0458200198 2986044868 8373447069 5107859076 3326409541 9956545018 3083275577 4636742069 5314104542 9717040194 3092439926 8007109473 8742393597 6003087655 0197126842 5906560136 9453404074 6238109002
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 ≡ 28 (mod 64)
and therefore cannot be a square and N is prime.