Primality Certificate for (661^4363-1)/660 |
| Andy Steward | 12,302 digits | 06 May 2008 |
|---|
| Originally by Tom Wu 2005 |
|---|
| A066180 #596 |
|---|
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.856619% factorization of N-1:
| From | Factorisation |
|---|
| 661 | 661
|
| Φ2 | 2 · 331
|
| Φ3 | 3 · 145861
|
| Φ6 | 7 · 62323
|
| Φ727 | 1225723 · 16283347 · 7707526049 · c2025
|
| Φ1454 | 2909 · 13634935891 · 76002550171 · c2023
|
| Φ2181 | 266083 · c4090
|
| Φ4362 | 4363 · p4092
|
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
:
| 19 6512639322 9350550745 9473684302 5299288250 8174665864 9062381932 8513380325 2030105103 9215712477 1870619343 4308406736 7149801430 8922291807 9167450421 4192183202 3610065224 0492501245 9766785229 6833149630 9087840437 9394404303 9308766434 1828666422 3745334623 6231784403 8315232975 6815786824 4547243097 1362919183 9783207060 3880634659 9592621262 3503999615 7117914442 7042410167 9042709112 7359364046 4318779204 6298020674 7728700720 2739995399 7830618670 5716710398 2364314595 3128343284 2841263882 8512623077 6921455426 1443568941 5796721990 9553310759 1531244558 4749020887 4610155380 4989818409 0844541137 8708076280 3688849961 0760218130 7222689775 7255639229 1290561859 1090575073 5049412199 0083980482 9810237043 2828663175 6526686764 7150630046 4631963238 7185149691 9369816913 7735396154 6095016437 3366247624 8978913944 6073617544 0447540501 3796751804 0890891990 2443311769 4930760965 2572141943 6218596203 0496591743 4179140064 3245301747 4766189580 3369483697 6320258878 5534149228 8562244859 7301637893 6835635850 8636331519 8025679796 4082806651 7136787433 8361885627 6419649821 6626932803 2028183997 7713699711 4115568613 1779446465 1698094239 0937089896 8480577858 0268902339 4955014898 7473586664 5045847519 2008763904 4309216870 5960020576 9402550770 1949279235 6737956567 9609384815 5026409156 9658327889 2192987154 5689856764 9467439411 2017900642 8496582413 6062523014 0877501141 6203778509 9184657219 0679813663 9753600996 5714116121 8678596288 9482513937 4832301880 6081521465 6772126650 5623804422 2702692404 5703182345 2335968835 0421018133 2467382895 9626784372 1062745075 8512319066 3311138596 1659057555 5777125125 3083457097 6184108077 0320851676 3450239079 1682685052 3279807519 1204043043 9183803891 1245591840 2079349720 7585214703 7949622365 3627137563 4217300260 1970241261 1556580759 9431966095 8183202616 3032122993 1111122895 2496460963 7838357462 5951227945 3549113558 3762307311 4839459868 0377455760 5303132121 6434772780 6893723567 8255260300 3368201503 3409330800 8974895579 8672128136 2508298680 8243819456 5402450836 9776561328 2165141419 4803652749 1111298056 7752487973 3569296596 4930128856 7299762928 7887987825 3927925085 4613708015 4460100202 1120177521 2564368432 8520293780 4955678657 2548412341 4669227187 8690918257 1714353619 2311332123 5971541316 6818457515 4596626093 3735046613 7635288926 3664751392 4948995092 8054873819 9937353443 1080940584 2905532396 9295616665 4769165660 9035130523 4548602936 5688304064 3389366627 9768361679 3957386318 3079331026 3132991349 7553325304 1727834093 6531881109 0464801947 6982464813 8331182835 5098246848 6897034631 1181128686 5447986413 4947792495 6194124601 2785555340 3571485129 5046626722 2142839224 1521254054 7764132927 2683441785 8340890799 8198329054 1703601192 1851310432 3520805734 2153487205 7424272542 2258966897 2788593611 6467424484 7472132803 6555034284 3269377270 8733013693 8315507843 6339322192 6058074595 9088234512 1548065577 1847028255 1184254680 3844060734 1911898726 8933865055 2997143664 3486010934 9350279311 0191840045 8379124223 5601752736 3073169516 8677591642 4613863169 4591238884 2047695947 7159220576 2947334428 4086622770 3266749972 2096578536 9177752379 7644118599 2853380950 5557977362 2270175085 7526658520 8869584748 4116983396 0728895513 5947741867 7939278399 8436865906 4568960362 7660951719 6140628973 6759929378 7948807432 0399297060 0716346616 9121558264 6681921752 1904393033 6724817046 1198953785 0809265426 9440465844 9674862512 3127235488 5142619831 6027399091 8018161418 2396561035 1391621850 7032018882 1305723613 1877928074 0396460988 8668073945 3028947823 1233883200 6359197617 1757489137 8656424229 0014398859 7528408860 4477658264 1478125077 6717727958 9496927404 5464823104 1871035112 5077428516 8892083622 7739130926 9410469247 7672662897 3780771160 9384136924 0280265517 7553162434 3464579132 6328080186 3538702396 9983607090 9668646104 6768510870 6583006171 0997186571 2832989124 5787191941 3709891798 5406162433 7460356963 8990827113 8165337835 6998790585 7339109667 9692207535 9604842379 7740301383 8174906066 2264315891 1883407074 1585444285 3443869888 7243424849 1631280342 2991039400 3211952681 4616651468 3611714553 4595872536 2737988815 3363485154 6229697531 7654427940 6161271471 3483990122 5390279854 7872883361 8342165564 4106051426 6900032053 4463543454 6654257990 8967631433 2135434845 6737865804 8654726103 6513913337 0492404684 7931131275 4194582683 2194224511 0489781803 1757859572 4915258530 5269678220 4979819884 2025544347 |
| 7 6002550171 |
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.346348%
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= 3 6207179950 0048460467 4311426522 3205965036 5414432387 9483575187 7825400530 9358693383 6683694244 9428372548 2907770850 1678900995 2098769396 5369568728 6401678385 6326444699 9548739111 9918121729 4021524943 6099272523 9528119592 0149449323 8160099184 6122268034 5675248999 1201470886 1764674102 6192992825 8662653404 9195895729 3828490189 1851523504 6137881853 6055761190 7745808067 7112845669 3150833979 8438603034 7572072899 7634432283 1254993621 9159305747 0790127259 5273739925 4067666726 9476732888 3526141335 1978417515 0348525331 8005003740 7392037777 3859137913 3807502769 5572915836 0544956663 7105954568 7090896602 8160757437 6726587757 4087832349 9373355393 4171075330 9956731553 0407304433 5010792948 2694547047 9794151414 4349142709 1773533297 6983736720 2446826271 3396015640 4658371528 6382281735 5436278815 1983311017 2026970342 6684296290 0597897154 3930079146 7284529038 1679813412 4440480235 7989183981 6859923020 6633318019 2496030832 2972744363 8158941904 4355021610 6205190632 2422937271 2921906204 2064480130 2689686116 6719596433 6312761620 7160276165 3573267011 8036903466 2331395119 4309524240 4282130870 7650547189 8551506175 6986110176 3680137868 0968041857 6818434910 8572269740 9214511808 5001848423 4503769544 0441332720 5944054813 6220463082 6839144265 7129362118 6823519954 2368122297 6539867167 8263231045 8896675533 5361664497 6503436333 7170286130 8900496086 7176881644 8026970760 1450904536 9349129494 7714391303 8056589334 2913501858 8476215500 0261235390 0420332982 0876262062 2393539513 3466371095 0185121001 6193403390 3834660993 0787539150 9611411909 5185596635 3124035236 7524614739 7290515404 2772647663 5888295918 8166528776 3818603290 4214839599 2155907103 5189069513 8016280483 2568491198 8504711054 3951316188 7878893775 2314752035 8642020481 9177666199 6164743769 4544417366 3340511695 2693403126 9213172250 3480484828 1754133454 7876945219 4887710934 5839852041 7771292446 9812817680 5601934484 0170620399 3664243801 2444344303 3422173659 9297301858 7726227649 3933262108 0929551015 4054410203 3774744350 6578568025 5606187933 1094157915 7366463480 1415290150 5575652198 5579009884 8003387987 7408845919 9798220114 7337040010 0017146594 5897702290 9786808954 3750757821 5388242604 2273300798 9802787491 5605223794 4613130873 5583432557 9712774469 7730953889 7456174079 7086289469 1503058685 8203482694 9404855689 1730455627 9128761996 0162261237 1279444485 7038896932 1891810556 6539526964 7978077069 9150140619 2555729163 3101551519 7789775420 1925278430 5638830431 6209088486 1909650400 8727397103 7812362724 4760833056 5778662572 4230959302 9380887168 8587528565 4775554240 2233189022 0873566425 4939808980 7812186769 5418813498 4797050092 6212915104 7025254651 4859839797 2513265702 0837019518 5055382947 6903882309 6562816255 6191631820 2360253873 9032865221 2780541920 9175478583 6353397606 0820720082 8398341232 4965045656 7964609180 5925359604 2944905843 8665974998 1042798424 4866111189 8673359399 0410803368 5277672146 6623626077 7103347335 4651361289 7962187415 1245234263 6232172997 2568240454 6090680476 6501054094 3532642024 2562928497 2322498097 4968120753 8325037615 9226947939 1714745961 8300845914 1787843710 9494046901 4580138056 1231964798 8603718262 0317554575 4377372185 5240106210 4181952882 7080467469 6969634395 5472173680 5999266503 2496470900 6191976551 2472350033 8539812120 9871243868 6146964130 1696949898 0503166326 1129901924 9485374487 7954753217 9395340494 7557525050 5952960538 5271695553 4263508557 8516482928 5198575828 8115938184 3855162304 7850638647 8580447509 8378790897 0833995649 5198685320 5827044582 8691185042 0833385816 4801778020 1347837048 4979107776 5328331729 3638976177 5442758906 4892571866 0635874721 3631685417 0176873457 0052021573 7131884083 5592998600 7176203604 7361153397 8012845034 1311934171 9428905833 8846722225 6928124979 8124115020 6399729215 3286204540 2534549618 3632689430 7540448789 3275356816 5138533168 1576846320 0228903997 7659002086 2672280997 5659533888 4470697033 6613144529 1009557425 4692708022 4965497975 4195421740 5047654835 1144841786 3865129513 9993606907 9533461683 4049127722 7012570675 2801396804 4468394867 3871997296 7082654083 9520198776 8874312776 2117176145 6145441111 0096584118 7067434039 7567192565 3226426379 4009562673 2796482498 4428853013 6438013533 0636255506 9463991503 1875055490 9697642868 0733204610 5195253324 7925309363 4892768800 7569261870 4473845385 0937243452 7316019035 8798003767 8608262499 4848641742 4699955848 4173467047 8695542014 9366562377
- c2= 23495597 4930325494 8211705416 6847396697 8292837047 7015550721 6559470877 9151958067 3722817246 4715866621 3680875324 9138614944 1687773415 1730279004 4682557562 3277646063 0895014173 2262567593 0609256696 6987154285 5337100350 4133633730 2474969778 9178842057 5475982890 4209873770 0905460936 2459844416 1837889399 3728627054 6013816564 9834737261 1238113924 9643370541 2559896310 5673475110 9023330178 5201716138 8259262397 2394096518 2697105925 9460758422 1211710822 0686845428 2451097706 4274763572 3715951823 6969039658 6675141984 2975416674 4986261439 0197886940 8214742269 3126818010 0307929456 3670146007 4133369138 6358290327 0595504758 6123850322 4627659853 3368545458 5220637023 7417827441 2986215323 4845325070 5837075223 8968025169 3125091603 6825902472 4155952546 8114454273 0674375844 0998732051 6638830246 1661850070 8666779716 9515760366 7919317331 4403425372 7026297303 1787667206 1601325968 8455798846 4465144352 8731157088 5401915080 3242058585 2355770140 0054969539 9900119891 2019086421 5390494860 7578744432 0578623254 9044100001 6253902709 6836091256 8711768162 2468628517 9669229037 0855802497 1477006208 5099744036 1992772363 2832437992 1080601267 8825859611 0405782541 9132063449 6974505144 3188630559 4658255646 7074148431 8746951586 2426888402 5525191588 6343820048 8882540583 4853022723 9486226563 7226355287 0660123945 6446122963 9698695250 7174693764 4056629174 9401213684 3699949682 4365896384 4265434399 2826331900 8194985236 4355837856 9999258307 0696668441 7934179037 1076825871 9310614137 3453903907 8668272271 9041203823 0981419560 1714396981 8664449770 6343701071 8200924212 3741409965 9966477863 7871519956 9049083289 7157522425 3459943087 2429401630 7563740941 2528993982 9653207637 8873788913 7426988608 9649308344 6414447911 5010264949 7545856472 3127253233 1287896384 6774146220 2520582691 8525968703 4526996962 7010883021 3841016182 2116104150 9659625587 6129390518 1532322341 6532891510 0114394756 3809064044 9189995218 9842684404 6888851831 8205079244 9485147008 8408991247 1924659355 4719355700 4790754477 8374441250 0005473138 1393804584 3291438564 7372884231 2218783972 2185028156 6017896175 6273906699 2197498004 7721681078 2355214690 6895823922 0774397124 8586047922 5226285165 8462604104 6793977708 2787454330 2498730847 1477064977 1130711712 8401496880 8787711668 9249478329 6060086406 4353658310 5723374372 0052526586 3051442709 3584442403 4133373477 5783540694 5949529998 9014085454 1969520481 9238392232 6740874884 6307622018 2492024802 3753133259 3158304111 1904855485 6163549415 2974409340 7248941095 1436852957 8909653868 0928393836 4017924777 3459782523 6297555402 6312217732 4273993288 4579370344 3480002811 2916592228 8148393632 2378717051 0718108307 1750186201 5700024954 9096812708 1756697790 4921110775 4563565086 3054927042 2727212817 3289792864 6483671962 3330985511 8154210147 8361335059 8194360003 2000601298 0822185284 2952199947 6856368395 8375286453 4078612119 6464558972 5850181958 7025053328 0621881623 7539636450 9115535688 5178591830 0096161943 9724266929 6829920009 4679415432 0174908613 8003070079 2324154202 8013184814 3927426108 7341722509 5845760295 8536770564 6420284032 0515423000 8120955192 0158273973 6427470181 3897301371 7703759649 1006993736 6783438269 6504041913 7558780644 1422931906 7779865146 5513511956 7008711955 6763325165 1989142666 7073614138 7434603993 4545419402 0429455088 4109444312 4225648038 6323746256 9202298962 2701036049 3691140467 3949568442 5947516181 9882699312 3298123829 6808141697 0445161216 7333256416 9599793426 1092534348 7766069186 1532061638 4546042488 8914989390 7829726232 8635158165 9751206612 4964076430 7804208868 1522081658 2172255347 9743488388 3460874446 4254356668 1268845735 5304638278 5242235418 7851372231 2517450253 4791378479 4855116427 0442344932 8567550812 5613677841 8532843333 7167534197 3475983144 5073576692 9839844443 8355983926 8182676080 4816768604 7827177595 7117568981 1345059867 4284732217 4642142178 2773450831 0391055959 6334157076 2440046493 0867801588 9879024990 9413744480 7648073621 5305096212 5773159156 9599978903 2041626636 4643383478 3344741580 0734175917 1444380708 0426051359 4680635205 2259044710 7857033444 0783767890 0588306930 6638273055 2345978403 1675832349 1543541906 4534033331 6095551576 6908585396 8835588320 7682883420 6823603966 2447695089 7118910553 0743083768 9948028882 9553744824 3370247456 3286075494 5534111918 5276274134 8091294138 1289865639 1958863560 0944194120 8826757827 6389901643 6746870956 7054587577 2766623477 8613813397
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 ≡ 61 (mod 64)
and therefore cannot be a square and N is prime.