Primality Certificate for (4867^3187-1)/4866

Andy Steward	11,748 digits	23 December 2005
Primality Certificate for (4867^3187-1)/4866
Originally by David Broadhurst & Bouk de Water 2005

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

From	Factorisation
4867	31 · 157
Φ₂	2 · 2 · 1217
Φ₃	3 · 7 · 211 · 5347
Φ₆	61 · 223 · 1741
Φ₉	3 · 163 · 1999 · 27883 · 487648536841
Φ₁₈	19 · 109 · 88700923 · 72353549179
Φ₂₇	3 · p66
Φ₅₄	1439803 · 10161750584137855664233850077 · p33
Φ₅₉	26100421 · 722526391 · p198
Φ₁₁₈	c214
Φ₁₇₇	5179021 · c422
Φ₃₅₄	565470397 · 3119477737 · c410
Φ₅₃₁	c1284
Φ₁₀₆₂	1063 · 3187 · c1277
Φ₁₅₉₃	6373 · 691363 · 120239641 · p3832
Φ₃₁₈₆	c3850

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:

59 8064129682 2660380714 3168835175 0684328702 4936791073 1110256000 0048369946 2687231393 3905379357 2418284487 9264154970 2855158348 8747787215 4744313477 6939661687 9878239135 8166923130 8509623183 1501079542 9345991702 7706100106 6854909948 8784828974 0678937169 7633075600 1040236829 8874858029 4390563960 7182505385 7025230871 0355017927 9648520793 8249932195 0015042306 5008880116 5256971503 9509667173 4095658508 0902445878 9050607323 1317130913 5411802875 7568690123 8373187042 9291732026 6426822120 9893533044 1437353321 6642893802 6157789587 0783311492 7150326492 1461077292 8900748091 7744208866 3374697383 7526932235 8223089436 6189784330 5616332078 9105774051 8562713318 2656518197 2559613214 3082313614 4777762059 4965885057 1331560977 8958540017 8943228712 7123743763 6521743312 6164317491 7005320513 9896349210 9367114048 7483802082 7397326492 0562963135 4847498074 1698015624 9332616891 4606300624 5489813400 2470446583 7203162955 8626540629 1620724355 7001006385 0764118711 5346809461 6173824747 3828023568 6935040882 3127495323 0826476700 3690573301 9493680495 3101021766 2185260432 7900226382 0133411050 6247791381 8199239974 1265383383 2976740280 2449654340 2320820359 6715882693 4883969694 5190010036 0353625253 6277907120 2818279129 1062882328 9678664003 0306163045 5935264375 7219184671 8729761633 0064726073 9324771257 1421340583 3391028592 6520513790 5219597560 0778364852 5126674206 6914788728 2484666911 8890273901 3743486731 8030353208 9702785051 8269370556 3874334718 8960412631 9493542887 8663879140 5202406859 6298379450 1268583805 9251499510 2565598627 3235866060 0319503124 4009042842 7170086644 6689558471 4575647120 0772836304 4138862302 8266026186 7301661082 0494331189 8319961645 2028229174 9352115029 7836661665 8975675559 5850429051 5224998502 5193233587 7319455110 5583508614 2961447627 1797533550 4993350545 6625691113 5306816073 6148725878 0312905154 4784560351 6600397739 5949093920 0744010203 4866545671 9260377065 6702847816 6255653395 5934740083 7030259250 6936115893 4890599789 8583500140 8703747244 8110350732 0028246635 8946108524 8568023773 9820336817 7318381315 1358516677 9409904403 2405898510 7846545346 1373194693 3491228754 0279347636 6229429929 4943323628 8765841634 7354816909 4443412632 7407619343 1478946339 6979925176 5063169278 1978045144 6594741480 3945809794 1835050167 5882977339 0906127252 6768828723 8843813325 3810964687 6848718376 9823753460 1124222982 2304881744 6313520827 7151129001 3054367839 1733467306 5413018666 0838139777 2541879842 9947958569 3968145663 8584434351 0549571763 5742091747 5891559486 6411419472 5783138710 7941185117 2148597575 0353261786 6882859122 5263812928 8473130426 7775829806 1963134895 1832329663 1415699564 8845164938 6556980857 3231761883 2127124089 8973109529 1084818045 0970838945 5254625999 5424973435 6540151295 9096266705 0053656020 7194570906 3771885859 9714700631 2444554862 4473721670 6360189258 6534470885 9428413951 5091363171 4165924415 3130270510 5320541399 3926315047 0562271745 7657496979 3714716474 9231723938 0485249382 1182703280 9414057816 0512386506 0461412531 0456756774 6723915075 9324284628 9661957110 4097558849 3763042177 5642694101 0422213826 0597507858 0037193820 2491103222 5285062925 4493627679 0721994123 7824587588 6920144964 1278193302 8873620016 9639418594 1005868091 2906228897 5906850690 5146850588 2804484860 1060826625 7728791943 8713045706 3340698821 2556741068 7242483954 3675530898 5322968889 9997147965 6529156909 9969235510 6847179020 0250034406 2457604698 1452500546 7669429746 0731754529 2439668307 4946068395 7018252716 4482769861 5118413405 7064743105 4802113894 0247733607 2595272270 8435310085 7524739222 0617740990 8256608532 8652663774 0810266512 2069795310 9938822270 2581151578 8536553960 1673711470 8192342540 7256020069 2700581106 0789618011 2582766332 1383837371 4304140828 0441704182 4063059865 8294224141 5983035630 9837803898 4560010694 0571194434 0024722777 3866407188 0425416739 2424463782 7469539505 1443800582 3475807926 9603447184 6031820708 5926120472 7042651627 4260668645 6563221045 3634834307 5531905995 4903115382 8021046876 9030255548 8638408030 5268936087 9502187164 3624181388 2139029363 2384218279 6921262915 1863132886 4345326254 7551175071

38525305 9567783926 9281319207 6771925730 8796321311 5493311989 5950251915 2425917233 6742845893 4421207005 5978242037 8412730243 5442384039 2270214696 3858021643 7727051994 2800355730 9825290989 5791003885 4055787727

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) = 34.299410%

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.

Express N in base F

As F² < N < F³ and N ≡ 1 (mod F), we can let N = c₂·F² + c₁·F + 1.

c₁= 55712 1541930719 6035171828 4209389734 4316968874 1819230456 5575510027 6341249441 2818452767 4719152691 1382379004 6293693494 0419972950 3076231121 8248771619 9211157536 2798660488 8232238406 2996051808 8751506771 0678598454 8030591074 2331555821 1753276891 7462054517 1075469650 4018572810 0117200803 5843239068 6756958589 3520459111 3028929004 4143825045 7320973954 0166712130 8981825878 9667245537 2219457923 0265552575 4544244635 2235233891 3148141177 2725196024 4535040475 9813754392 8623171750 5170223598 4043969239 0879302510 5781659564 7544590229 0329575813 4395814158 5677388015 1919819532 6634773011 4377139036 6823148907 1887666003 6273031822 4673149688 5561539341 9642704969 2581259612 1315364580 9553339856 6030941534 5030771154 5116427947 5027976477 0833017985 3222226849 9809432931 0324319021 5575817191 9664410456 1139273396 2958283535 3002647032 1202805246 8479019247 6881599234 4837869683 6613474970 3054608659 7946648398 3051621326 4819039566 2054370480 8673553259 6422226555 8670001634 8049112328 7893910596 4201266800 7898972249 1240511266 2845502496 8767261644 3886148740 0982466964 7788280951 2042911280 4310099907 9515375260 3062678767 4359097662 2487593175 0114295837 4041888068 3480995994 5165168900 8898176942 5573687022 9101105259 0191081996 8056966287 3598419497 2826169997 3426239752 3939695661 4756857294 0708910952 9289661917 4222437872 6915001030 8077910867 1950880859 2177254299 8768213359 8861891637 8298638141 6954765098 2697865802 0553272283 5384800393 4114145239 7391288156 2074427162 0917799405 1424697933 2815474646 8738536851 1627339523 7275804779 0731316445 8158740451 3156536542 7358669998 5618599625 0709203659 2316583940 0608739681 6423979871 1353797077 2271905554 4632938446 7143017327 6987798656 4998238261 2342899243 0589098477 4954689113 8822070817 8617350728 5249959152 8678182900 9652374278 5819036749 6622013741 5985622209 5488321276 9871750413 0960545495 8412780057 1563126467 2639245584 6786869144 1480845175 3016495596 8828313502 4718813832 3072986227 0897850545 9860308742
c₂= 775801598 0807250994 5142305951 1183146964 7227777662 0125210349 4925472378 0918712114 3712221737 2266134363 6727304692 9993914369 8366226197 4238596734 5616156548 8677784926 1086951169 2698829059 8243563812 2738151480 7388891156 4066756062 1245176659 4348560372 0515392302 0177762219 6355389033 8343939963 1762732314 1858396243 5172859015 3220905169 0389598516 6077027917 3379146083 7646232888 5320843671 0061423758 8140260611 3098564616 1331940813 8824693655 1664276685 1688826198 7622479466 7786447142 4948223704 2036327237 5656998627 5306390399 9142190024 4285762117 9086200061 2140896120 6155034151 8681205602 7840740708 6764674587 2012410642 3578206746 7188772456 1970020387 0117425915 2768970467 9772772276 6513257094 9794147056 9830370424 7983154969 5519841358 7262327219 2176868851 6231182378 0168657899 1747819056 4044640617 7216296301 1485079603 7566962777 3326560378 7619038725 4511671326 2939954263 5381672921 5877338208 5143613402 1623720637 8026656690 6397367724 7577322192 8575012636 1352671087 1983897493 8916636048 4577726031 1208776778 3474746774 3512347418 6506292459 2901701641 1124381312 9508096023 3818276049 3568231228 2533310624 4163720301 8850877313 9692260359 9592691375 5712550769 9162566880 9016266405 0459038362 2688983323 3756971978 9339540127 3938398751 9410683845 6964539434 7041622451 2404616336 1152823950 6279323322 1116142802 4749523442 2658022516 3303816475 5937029279 6054743864 7220868129 2440047508 8044633046 2770695425 0013861541 9029944462 0357369550 3277039345 4314238878 1502296269 5946476257 6910989644 6168349597 2161936085 1994461034 0140971150 2900128253 0676801652 9608260394 8472716920 4331448829 9044878334 2641846392 8112949422 0292346634 5535227474 5940504881 8611297174 5741694186 3066383313 5836759059 2023324688 9963643534 6648821285 6334887587 4381529816 6200985268 2966412926 7811969709 4881457385 2137266094 8744095225 1956112636 9889577144 9097899944 7730255468 9420672249 8854784162 9640181186 8893297346 4303391993 2203637502 7323952035 6435438988 4001832799 7535975263 2136441162 0458556300 9889005272 0056781127 7256073173 0263822516 1695965628 4821397227 8369843034 7216868817 2596443496 6984537419 7005185414 6744964587 7531818227 6347653911 0231497297 8161139309 8870279818 6486372886 1453769902 1604897445 6097179244 8383977010 5332122949 0032328538 7835009383 3541749013 1651824231 4261585818 8092700055 4789452264 8964943818 4042982713 3189106021 1833967468 9470385033 6969719534 2758553356 8418947525 0519579358 9228705667 1872870927 1436500819 8533088590 6493321478 8320780936 2252303159 8118983837 2309405189 3751884995 7230813774 6789417248 8205254393 6541844347 6934379241 0503679326 8468102923 8483052919 9485901314 9292960035 0491875220 8940244010 7744919344 7341000939 2068489368 4695638389 2105311577 3657183005 2519245601 9155755630 5385301600 4381802637 3905402205 1480843125 6974366126 0507168171 2056487268 9225772093 2603698254 6895999264 2490905445 9197348600 2030812456 8681673803 7170076587 8731110152 3803164501 4216032210 3468416353 2397978707 5651730285 5799703017 4723049542 4019187352 2943470591 9092767203 6094329590 7109235807 5152538815 2534493314 8032397282 5076167103 4998963885 5428478741 7071019385 8752397594 9879731604 0489876818 8623318784 7144304893 0480967589 1597530176 6682258325 6507436490 7231119726 7127044768 6163861110 3272234336 8994581560 1661771645 0048989058 1801142861 4479474079 3460567596 9619901127 4743669260 7495133088 9367661704 8994566468 9393091023 7864274510 6620911879 2118327994 7186860785 7625435145 7514765837 4662519783 3601284697 8296554290 5968210484 0171229127 3867028619 3702281976 1320186477 9762647860 2224765855 8449616447 8788196113 0445365376 1363424967 9041591337 7039853492 9808968940 9170455912 9552112371 6384824120 1523334687 0327049164 5291591361 3319707044 8224194569 9976511078 8091309964 5780483708 0925027875 0887875459 7967377026 1292498946 2741485709 7399982691 2930445046 1699247335 3874400320 2970072175 0622719006 6596310515 8989963037 6917426646 7663383758 5882006900 6281175722 3163638250 5407584518

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square.

Here, c₁²-4·c₂ is ≡ 12 (mod 64) and therefore cannot be a square and N is prime.