Primality Certificate for (6588^2647-1)/6587

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

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 :

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

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₁= 6891932359 5493614465 8785846801 5454564185 1888976218 5855501525 7021307085 6835432786 4958690700 2264158403 8657135938 3636042258 7279347804 0715283674 9463825081 1762686672 6333728967 8632509314 5680947363 7690111011 5534884582 1474159272 1860564995 2806513556 5791195056 2618489103 5068612570 5759091861 8381875180 1299544920 6907812441 0789484170 5163440770 6154972232 9619889167 8038576460 4477161493 5738437789 8518166133 6088645118 7087478659 7189890669 7236945505 3864449765 2711940973 2454636011 7113081590 7339481296 9549856145 5694035097 9060915725 9790609633 2858575290 2322322078 8396668378 3623989460 1559461291 1336644328 9564400625 8385543743 3130873054 5737442932 0124139120 9993735374 1573289905 1353472275 5997081548 9328170842 5819563238 9255418082 8042166345 3424963266 8824626483 2628664463 9907338608 5211064069 7925523864 7467428647 5851883064 0631504742 0726718103 9595940901 6141889136 0965857060 5148725141 9636731095 8138400316 5962693506 3659664301 7898150161 1792812631 4840768730 2180785892 0892240691 8121067991 2266624092 5018077030 2133262425 6248490263 3291846043 9136467320 4601986939 0519418444 0576614983 7867488617 6290644334 0268898289 2831336428 6647829451 9855504387 0099935356 5882260132 2097283062 4115923038 0405347623 7320004914 4934096782 2782818987 6311036421 9415404823 7930981447 4337109218 4533499984 0977233790 0005938409 2542929310 5960275540 0183977869 7255165101 9783517136 6470984117 3248813569 6373926898 6429849649 2294746270 7525512749 9256048326 8983915979 6658965311 5604849635 6244561626 3949927595 5383249148 2849708027 7727553362 1458159579 9952410497 9819452285 2036049311 9124687495 6132970109 8069189488 5142064694 9131677464 4535512149 3743574279 6623118416 1587381851 1308509200 2967650227 3308552186 4853558401 2835610169 2774433040 4229676720 9581729442 7147602825 2090215684 4584307143 3396287716 0486692433 5196448644 2371296209 0284294986 5990547457 8635406433 3294814625 2039481826 1414041639 5732386975 2270786214 3058962105 9100679766 0876664190 8342434093 6736021629 8073792989 9183281452 1764729777 3505456339 9111489827 4421980314 0039523465 2775998559 9690592933 2545360135 1970495030 2571878927 3501729803 0071811508 2854245483 2641099591 0966106213 3298346296 2268982682 8463203531 4349130090 4903220450 5538482651 8856288111 4312303235 1755410632 2088088421 7253454388 8404382041 3760561319 3811225108 5308954599 9368391793 3364517334 9234406838 1820874316 6164799429 9242595376 7245432989 4381312090 2571359464 1195774327 4918323857 3298399486 4161247925 0483956735 8486303181 4749560014 9705477278 5227138326 4551248945 5277525774 0738014508 7544431452 8964808487 1110104133 4679659570 7532996502 7299662084 6491317263 7066247019 2549933936 2230941096 1750525130 2828138962 2001204398 3429202172 6103009717 9651953590 2855174120 5584385024 9851521881 1275516743 2452575537 9744129103 1958067073 2509696852 8292720535 8219297292 1649621346 1144252022 9741050039 1664475467 7341245447 3967979778 1872447981 3620979943 2810798401 6259980019 7004519642 6457225676 1359155788 9414770019 9234274799 8054282999 8666174146 2083094883 8851134715 2724107788 6113331888 9233006425 5215977250 7890434521 0379361599 1900152492 5211139348 4996993499 9923604313 5922531600 4161937400 9377707320 5291723187 5866390554 6635904039 2880181178 6630635465 9729842664 1351651389 8067671266 2778919818 9947660970 9315197037 1310093177 9133545300 1570327162 0001170886 4619046601 1570805315 0932555233 0697404291 1025097186 6593344428 0417644405 8785530543 5423010768 6974845772 7582840318 3918941890 3885871231 6329108213 7860093199 0292008450 4485953459 1998950283 7549537669 3637154568 1437491451 0615725087 1674598943 3018278002 2283837368
• c₂= 33 8357532630 9281723209 8522859252 7697587204 7696206876 4421450531 8176382012 8922885089 0874470081 2920712079 7974484395 8580267629 7121760203 0811082175 9623041575 4054775399 5251241938 9881670286 5447850668 5147130328 9122664788 5126262357 4890858385 4918382653 6739062132 1026528734 7772165989 6150722188 6542077964 1040502912 2159648018 0145549360 0410022969 5111539025 1046862445 1813971136 3551803609 4416330356 8762311792 1159038505 6184674295 3416807830 1437762592 0624111038 1817984321 2950433852 4393281397 7232860845 3628144190 6125282403 4424986276 0398841659 9027266507 5062514148 2713498380 1427737504 4425693017 0380614881 9964016102 6578031624 1695464359 5847819936 4564064592 3070137438 1094267856 4043268855 2601132399 5721475472 4462670606 2539760360 2183995874 9945287434 4532975467 9654121452 1934208987 3839265123 4129146009 9163149158 0122428911 1372343458 6993099177 3836001696 4051707643 0233067139 2265088894 1762378734 2552376348 2293650174 9045303962 2678781295 3848323932 3542265058 4963182310 4748124041 1786299524 8399575148 2449486482 8987270346 6302217212 7435886706 8075631413 9149898642 2954356891 1726286251 2872031744 0354385952 5522173675 1552971364 0182744535 0583136376 7473427309 9476394516 8065706687 0246282998 7395864547 1895854038 2287524648 3209473738 6630417171 3289018897 5677230119 5145368617 6165733479 3866582228 3351873921 1933093071 3283768874 7664946727 0552074041 7060167758 8805204194 3030489251 6208196094 9424067922 5593752439 2619940570 8981615299 2187487023 1879102704 8014214505 9261032560 1562854263 1334426057 8943287571 6010364023 3663080511 2070657970 1503600827 9212869546 2827839030 1895568430 1731425595 2360804557 5501876378 8053066037 1205597040 3839015097 6159186963 7165272313 2113039473 9257503273 5295308305 6434467569 4920296374 3324280861 8476790920 4975279512 5069447598 2115177962 8305967096 0672560046 3969978736 8670311717 1809628645 8767413927 9040061426 5725480230 4179682171 9707718741 2774216449 1295599832 5840953248 7656518917 8628631328 8051096390 4841514251 9235404616 3781797444 7944096165 7170025487 2135856923 3583644990 1863056653 8073618194 3174692716 9091952493 6360423133 4779200293 0643572121 7111825250 3491994510 3207206086 5928435674 0771786285 9150293107 8163236302 6970031340 3926288538 7528353590 6710015988 5511294352 6225229056 1099330956 6365409250 3254361070 1633625066 0635778612 7196525346 2705660051 6984059045 8360201702 7870607390 0034147870 8506284476 5782131362 9762427061 7455823013 8456734343 4617742880 5334052712 8978876063 5250886586 3505749661 0686789607 3837896054 6534023809 4195696681 5106770473 2824540615 6561309699 1215580492 1493740508 2781274180 6379843452 3253864322 4129725485 8674570139 1224333764 8860557495 1288910930 6676796234 9806988991 0866036209 0169598395 4608693086 1826941701 8980646056 5248311075 9339563257 5080106703 7136328581 8499049421 5160307816 8808132058 6413957286 9340789823 4344443472 9434148651 2834921652 4862040829 2906896353 7249686001 6029148268 2102226206 8745961267 3888634526 5161094787 3463909783 1610848025 4017881894 1511937308 1554946684 3793898715 7781291337 4430898624 1686905501 1914332108 4100835215 5951538346 3357937720 9360512402 0100043233 7795785449 4765418712 6804332346 1424451614 7890425523 8160129283 6375673277 4850375790 7368633209 7194919236 6367456689 4890174596 3562196441 3839189589 9621096289 2430810848 7425616589 6466719202 1848188243 9664567463 8110980960 2530050138 7313685424 2944649714 2668866427 0772267371 5104395824 1319020207 3570523493 1076573557 4081423395 2982436158 6813738037 2523360225 8482701030 9627434923 5121797910 7701617373 5054690245 0635149026 6170945109 1791394734 6608047297 7586456132

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