Primality Certificate for (1549^12973-1)/1548

Andy Steward41,382 digits14 December 2010
Originally by Tom Wu 2010
A066180 #1545

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.545040% factorization of N-1:

From Factorisation
15491549
Φ22 · 5 · 5 · 31
Φ33 · 7 · 7 · 16333
Φ42 · 29 · 41 · 1009
Φ62397853
Φ1213 · 4093 · 108198289
Φ23277 · 31327 · 20681668127 · 12503548991459 · p40
Φ4647 · 3650929 · 29988367 · 296800327 · 26347309550459 · p33
Φ47283 · 38326633888972671816294278880086321 · p110
Φ69139 · 1657 · 3313 · 402133 · c126
Φ92c141
Φ941129 · 802619884823 · 12784791887303 · 44028873099881 · 906859022094911 · p91
Φ13837537 · 762399769 · 1583539099 · 246195518766935251 · p101
Φ141c294
Φ1884029593 · 17937871859009 · c274
Φ276160357 · 23520169 · 71026491428056081 · p252
Φ282c294
Φ5645791153 · c581
Φ108125100821 · 6356714563 · c3212
Φ216247 · c3227
Φ324338917 · c6453
Φ432418723110257 · c6447
Φ6486c6457
Φ1297212973 · 2568457 · p12903

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 :

638 8901475251 8157717284 9324547996 0027917139 3036596312 6224867042 4778793620 0186764410 1028683019 3404732706 7573842178 8569628561 4091756877 0914689446 8469939799 5206413642 8176662390 1890175264 3701735680 2951847823 6768258661 3735041609 1462825669 4445339155 3927794889 5591767472 3868139495 4135867991 3857825311 2147271462 1530743535 6098250152 6633239172 7227476579 2496781183 5190127445 0134970454 9273613370 4890050144 3916142488 2666012635 1115545919 1170918704 9278027401 6123267375 7288582165 2923243922 2468701657 3883695798 6196957437 0671834499 0164979866 4798137670 7897456228 5608026207 9327346443 8306057294 1506930028 3091165433 3723809956 3930040773 7619662397 4546540181 9159420543 5711089774 1460119570 2552022927 3035588131 3523394046 6172221310 0503564184 4438494868 7321993022 4233210870 2549359370 3544451198 3094774371 1025687607 1035827920 6091884955 0077940737 3994402860 0383581513 8386154887 8898576142 5202055713 7154466468 3471381482 6211783097 6203517083 2206821824 1066286853 1158356489 1760854783 5992961606 1281537181 1592855154 5608922379 8596174993 8120272276 9984029610 9862762925 0627997191 9764834554 3410031132 3365025790 1736261067 3012378585 7570824085 5891507167 8510633781 9516752048 8295575107 0803213341 2839922186 1533112944 4510169350 8777729700 4311012771 1004917386 6951884332 3230417200 5462092679 7127712016 0840967777 6858555618 0165791166 7902333012 5736435220 0147289768 3470686644 4805037141 2617674627 6364998388 4772040391 7599305117 8772804833 6071100770 5535677226 5147662310 0927711235 9107539318 5766151949 5767690882 3475012072 6940740353 6687355436 6518123993 1875576818 9844060962 6869640743 1000009070 6772019423 1151057265 4458613304 8833434577 3229626823 9007510454 7697592924 2386408886 2804858206 7611304429 7797834638 5950467548 9318623101 0937785333 5319950389 6671777077 1634494720 5815026405 8425066468 6388529636 6323067089 2847387035 6699804312 5546221557 6158183727 3736108790 0416337703 1383783543 8567400131 6898064908 1790760710 8660443108 3163094810 9971775653 9237309881 0532161845 0609338164 2830888101 5726821824 5603911773 6259876069 5273251101 2574908390 4280449462 0768232962 8579208535 6490174752 6527618723 0522761359 0068058266 8468125924 4327290985 8632163551 7194522585 2444406685 1858282496 6898184444 1286878928 6121650928 4244747383 5726719230 5224263894 0106598102 0059183656 5099202596 5643978338 3230732944 0186868528 5478081535 1461790553 7943994377 1109149800 0146204889 9254735748 8665420740 0780164324 9771448685 0639833346 8864532880 4244813477 3192607076 1183567614 2930828228 2177450379 8755774961 5377309370 3420661134 5844358443 3961508967 9838130111 2424634969 8463690761 8844368320 3291980289 7292812053 2045674920 5086752826 4563733282 7475266493 4327301005 0428421085 1832869577 4546228465 5378863931 1406848759 6814192536 1896351689 9101213214 1274528730 5845103480 1881271308 2883124993 6715092575 6909850205 6911663998 9883542316 9915180386 6919357429 3593890329 8488455301 3407789454 9044754697 3788277196 0059454445 9818984540 7353653879 7442123653 3190247867 5607693705 5693660308 9810219931 0529868262 6386930080 0669782152 5131281882 6495585494 7459835575 3949548257 0769047783 6331624892 9638811643 5605551912 2171769681 4467946596 1487993861 0271756560 0374332365 6194689202 5989151607 7796179566 9873287658 4546358148 8785712963 0426452401 1711670786 7421342761 3312450549 4343378193 5235626043 3873750614 8118367456 8921942955 5217429826 7493436203 9129500560 2036413854 9475036847 2393063985 3266139186 8067012974 8624661922 6171730465 2909426312 1941744707 2089373038 0127864817 6061789150 3105520576 4830167708 0823097123 7882439060 0724767766 0785712541 4461880317 6790997678 9497912770 9215718483 0642084564 5485905588 6806553090 6459038464 5994513164 7608971021 5183756361 2842738890 5400869573 4075048310 1460600975 4562867957 0882844416 9019209975 5160235936 7054040220 5706177544 5135220622 4933255388 6110955074 3533982661 4028842124 0478180926 8402557555 3686335006 8873887038 8076327029 7354179371 0186107590 2410763544 9293977405 3533471509 4588095755 8159312776 3187409724 5731435279 6205446556 2296943909 0260650863 7105117542 8216627691 9097979651 3554469217 0679368129 1759304990 3268427197 7688064922 5146670620 2333416654 0221385168 5951022232 5097237387 3242427484 3812256429 3838205179 0802145031 8606976922 5223903034 1066068712 0607400453 7530793052 2149315401 3082652946 4536914532 8360298939 7743705353 8997223669 1832119745 5523205000 2578948272 2134754816 2043652917 3576425493 5818179992 1752205467 7026008283 1025024171 2227762382 8053437836 4258453988 8237037486 2493282232 5782856330 3595825660 2091850148 3934255707 9669060325 1601892607 3510611084 1779927400 0349515960 4009117503 9107847693 4450717562 3810724159 5450877573 2831500203 2732825923 0407379522 1437245544 7427448377 9325396159 1687891691 4874658911 4231417957 4866942118 3512632183 0162445058 1809742164 9455794887 8133371986 8717365196 6951741629 7295170532 4342401644 7490369978 5630214178 3628889234 2641213690 1795802599 9838972754 6078861437 9094748234 1378449721 9390514039 4310255824 9947863639 6651394139 9768178074 8636518314 5868008318 4680441933 3205622658 7087243184 2583427861 9720836452 0307121582 2821890248 4859686398 0034222173 8931470404 1104752678 0539330735 2610447807 9000428404 0577452108 3112460200 4082772194 8183574602 7578405404 2898151321 4987865012 5995377861 7312987287 7866129002 8379467277 6383975664 0093844000 3781795270 2511035088 7146016162 7536180603 4447190296 6964070114 9577960142 5076409625 0509789172 1947056925 9964290884 6955490305 2606721071 6454262284 9829202230 3565052142 7592976846 7842095297 7180914058 9853865488 2238866869 7378462128 4002115389 2850629388 7059315403 6012200759 0170523958 2883800457 4631321807 9102170541 6492101541 3930704505 5154331295 1942646605 6561578861 6567644766 4964484066 1285753978 7216042910 1402108440 8427178196 8188110112 7434447525 4530764943 5582298709 7386051283 9858632795 5251149126 4708791094 8873157617 5767092393 9232657930 0962386026 8006192414 8823925516 0594843977 8868394758 4800242418 0694658990 4841065927 9956442382 0640740471 3809369236 3566045311 3527140861 5162312470 9908953643 3551575933 5442803919 3683680347 9978071427 5029662659 0340233009 4401788234 2665620836 2528845194 3929170257 5466922300 4571129496 1430128806 3424926083 0047276204 0011314729 8819053848 7778322909 1127917128 6022048464 3527097684 4182259281 7382034707 1559450469 0968088183 5515157645 0911464355 9248009767 6616230521 6950128156 9820210462 5949292883 7484073054 2696959066 2245174917 6620322827 6710086830 6611700455 2809839450 1573398915 9550849078 0072749482 2035822463 9648660146 6834605888 5028864193 2156086421 7763324491 3660454580 3768728078 9557892216 6933934320 1162680748 5684307165 1080594835 7166967774 4660786646 6580486283 1184840729 2777854665 5465319190 4985833270 3720250309 9927113236 8944356188 4646035342 1083983724 0354445568 6112480286 6481153384 4044671522 7373059400 2252567324 5632350226 3377224349 3104315160 3204657007 1815132945 9654700404 7985484028 4204668638 5362407029 7912523127 9427105570 1387206865 6140861473 6683433272 5858222166 5931701690 6188015761 7012525634 7038939904 2005769254 3109695696 1128036678 9072112258 0685121003 1183471705 9742982504 0671573578 8771418943 0887041338 7115035261 6278169318 3241749343 2577884728 9547387173 4873792007 3360154227 4079043543 4782605840 2981147638 8391263972 4157909127 8098899358 6808580705 6039193089 9207128223 2926335413 0310358817 4291659952 3446782831 9783923800 0933299878 9406292572 3550466961 5046054354 1775376643 3140643731 3414999175 2785952840 8734274462 1082408493 2586809932 5126399881 6890262183 3919327436 2865067709 3497077871 4071013789 7793654038 5966267849 8267544171 0332925224 1444256846 5509805617 5055560143 4994603930 7852600070 1764175976 2553354751 5011164816 2326374405 2050526895 1606950711 5703994449 3874525689 6997577180 7197352484 2884479346 3681534677 7519495304 3834569493 6094168262 6370450612 4029118560 7236769887 8125746859 9496367019 1899605205 9033173710 5534342197 6251912958 8926524030 2516389534 5410358311 2017780350 3944005591 3298600574 4567075810 8369542176 6161975359 3244174544 2813868822 4689201578 1017858519 3613715369 8357011909 8587816762 0925670002 4892784445 3948978953 8628541086 3104554968 2571454465 7806291147 2742245706 3083848231 1625952497 8111002030 8845602384 4082948968 8883692473 3611635379 1798737043 7838278189 2419869749 0453829723 5816891915 1122287643 2542716556 0334349863 2670904418 8172193475 3398131546 3998232376 3764866954 5729103581 3042670410 9616470765 3673166830 6176591483 2194035024 6112846660 6274070703 0790711863 6779939405 8012245241 5115358022 5475176787 7896460038 2745405377 2044925496 0260260570 5920316580 2239868728 0645906451 5916376383 7749130606 0687576865 8594191434 5649445129 0341101153 1701726015 9298201311 2920311267 3341775762 4137383057 5051369753 8662708306 1221089546 4154259730 8401736831 7496712998 2507867518 7234536273 9505945339 7535180376 1884224655 9083648245 7166425474 1535940703 3040251024 2514621273 8711101828 2255384728 6446159512 5521014280 6176671056 0353315060 2029016641 4907810040 4082124392 0665771250 5285737871 6009768309 9000457230 4558630961 6394012170 1401507829 2953901698 8416374800 9489991114 5000150128 5206506456 9266451570 6404100574 1561540708 3783934050 8186619863 7647096686 4455689581 2657581774 6555432356 2812127332 8599996025 3393975326 8559129334 0943362967 8220396506 1367036923 8668897621 8390808360 4511399785 5490825611 5118298159 9384735641 4842535521 4186162005 5367347658 9602542869 4568464581 8305161883 1755574081 7549698362 2382670575 0892016768 7200838053 6588566558 7953107143 8281374091 2051736354 8231957051 1120218342 7599713072 4108062994 4698819196 3921692015 2523770770 3927038707 1739754702 3417031716 9936554337 4710221579 7476548434 9584467541 9812064728 5891250119 9966133932 2328042512 4187194138 3123207344 5684085494 6595200007 6945762825 6826479248 5588997256 8766443706 5970475205 0736202857 2403692322 1976580282 9916526884 7382044613 0251069197 2687498279 8422112050 2349776690 7579746731 4170832752 0036001624 1864699975 8756683804 8793561462 1919516460 0954476923 5550588959 6519926722 1994729346 4023967660 5696238348 4121321813 9601555199 1953463385 7626174532 7386023322 1074319813 5420600668 9505099507 3129356907 2079548204 7363769291 5176171672 2962691862 5154499289 7567409197 0268103111 9239850005 3975461892 5639997210 2010007708 2821571071 2968620599 7509775553 0801444745 6777891797 5316154335 0606456250 4146141271 1690524375 7003014758 7137737710 8563326860 4914769457 0812841729 8950083711 3212688563 3675224894 2084346035 6974002759 8741862117 1631150922 4042515695 4600708044 5913018424 1256584732 4873651954 0834361683 6457253085 1719673746 1107945516 0106331348 1739676661 1309539277 6758220918 1877216740 4633920611 9872940037 7760784822 5900138246 7398280052 8628890946 8426783607 0588881146 7642458840 6370324070 0839264936 7618411953 7878235234 0009696542 5364289823 0217377399 9797812575 5042159651 3768033219 7340679424 1764738629 3711083216 1736462581 1457003574 6310384024 3428546894 6777909100 6432196079 8686157794 7853150443 0662310237 6100040569 4957495913 0702445679 8853821437 2023756329 4150249495 0065595185 2832524982 0953970171 2266195494 6900934316 3208322777 8702644801 0837631945 5894189875 3295864752 3528423685 5881687329 7145614804 4319840671 0622711623 4033227548 4956278201 6833852452 2701526536 6839425621 8024685544 3285084025 0095033903 4477703363 8569004947 9601846544 0714195727 8765192044 2127140448 9907458925 8020386863 7649118122 5065289773 4495098197 9123126130 7555802209 1787459663 4366533391 8818124972 7192644326 0128408934 5318264908 8670359551 3794750106 9301770547 9323786299 2955223513 2185552468 6534766487 4325582223 8818990753 5820349019 3898466259 1420293924 8703907319 1932701042 6247168071 3964397146 9423437943 1531500401 2181323785 8453217118 7543284951 8237599092 2874972379 7901686955 6026204416 5023985216 2674427482 3313377965 0334856025 3135884040 1438192484 1085299102 8160271384 2000850635 5909411016 0445985622 5645839315 7710142497 5492754460 0942100645 6456460237 3485738623 4221734839 5469360883 6870822969 4770336771 0927785720 8961865022 0618483687 3408543375 4049457401 9080819451 9703067693 4640377843 5716382296 0967239602 2760242994 7107640416 2440617945 1271507745 2447428954 0568876463 4478467915 2678891178 8492779884 7208413264 9591992076 5944112707 8808248291 8460774943 7858233466 9151034209 5061740996 4578716684 3241291330 0504717717 8588571484 3006340732 9986320087 3159249476 3633893873 1577331984 4497041360 3639534419 6454383629 2735545950 0845110332 3181101080 3416645503 9196796756 3153042938 0842783418 1474953222 1489604197 2540200722 8791772602 1280656829 7663189846 8180457707 7961044328 1529210603 1064439518 3532024317 2516972186 2313403468 7561581242 8201457370 4484146719 2785917067 8501432112 0263433476 1989238618 9053978767 2603609169 1708616117 3317808527 8581782277 9455781792 5298584977 7985951106 4684800446 4695724422 0340718528 1639506474 0888429883 1985584994 6281596042 1210030821 4468531896 5209899465 0601061317 1058394565 3731582828 0935819747 0927911309 7834353770 1320401359 6475223583 8504392124 3915360637 5336490960 4349307109 9797246695 3264391198 0810783169 5388695541 8323231347 3805901669 2042541690 5769891623 5746345694 3712853707 9343676228 8166742713 6166060372 3263092798 6913594877 3393098991 4060102999 6691689407 3868276266 4332993059 3754836056 6551704359 0916062613 5647994601 4662613031 1937406192 3022439238 2754904171 9284212146 8803151405 8322861397 0850865710 0566118659 6430378260 8417126939 9207934437 3834857655 1953472595 9894444657 8889999039 9486394795 6494788870 3734774518 7649060848 3416644235 3558288116 7510526165 1629058164 5515773067 8928959284 2294519276 3131257431 7959046452 1155959001 9502545758 4682418704 2554359697 0982449836 9340470870 7472815188 1751177597 2779297424 0237680126 5911775390 0287535265 6149214905 0333077505 4724433779 6467837561 5894600468 7255521594 6356376424 8545090297 5755888210 4509418639 5405195034 4441705348 0835391833 9816571741
19 7959442104 2051990170 3409475899 6103412218 4310370952 0228809233 0374222842 7016493187 7746383155 6055823747 7298646377 4414780520 9056662031 7890660590 6748807115 5299333675 5944568152 7619486976 9892303402 5023653149 4491864250 6821741029 4883979144 3446325499 1285693637
5097515613 0103503263 1125826705 1555667466 9009963859 5882223659 2241059734 3894462560 4162721885 6673260604 0838234657
2 0653393077 9806693192 1984812780 0190526252 4983064881 6702815129 6649481013 1593763302 8516451872 6914741633
1 1937408850 2497853569 3212222017 3511819169 0257092262 7062260277 0959729641 0357421754 9779568267
6766969375 1189377206 9111782125 3317878333
38326 6338889726 7181629427 8880086321
376 8740189264 1869824958 6476740841
24619551 8766935251
7102649 1428056081
90685 9022094911
4402 8873099881
2634 7309550459
1793 7871859009
1278 4791887303
1250 3548991459
80 2619884823
2 0681668127
1 8723110257
6356714563
1583539099
762399769
296800327
108198289
29988367
25100821
23520169
5791153
4029593
3650929

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.338635%

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.

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 ≡ 53 (mod 64) and therefore cannot be a square and N is prime.