Primality Certificate for (15679^3499-1)/15678

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.622981% 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.361659%

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 = 11 suffices.

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F³>N, N can have no more than two prime factors.

Express N in base F

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

• c₁= 750905 9953478983 5849899926 9531051257 2815684925 0920884878 9143885898 0818231288 3236451426 7478642910 9935364908 2855855731 8790251632 0051235982 5358655261 6904252018 2837742827 8007982094 3427891573 9651039806 9053917052 4566887584 5849203236 0651041851 5795624680 1180069658 8943577373 4166734386 2393028679 1236870955 5507708814 6366779002 9555478376 7073149937 0385572782 0607935202 9795456253 3031068947 2203345875 8679031972 6924326977 7371722752 6089813237 5310324984 3590903904 0303511751 5824060477 0248268269 8698170967 6078893129 7792908486 7261829303 7700422437 2186598563 2986713674 6080801379 9374391574 2552733868 4441101769 3574693111 5972883934 4753330375 9879634898 4890106448 6423665988 0325976732 8185738004 3139127769 4327198784 2961360427 2881349623 2285096215 8627204689 5347310095 2749705695 0291092857 4714810477 9780824632 0937546700 8733069824 2245125536 9814631469 2812195428 5258547572 2521047813 4582411365 4244810410 2696446838 6681040330 6828982899 9308007214 7692531934 5109782066 9633437947 2920014900 9663438366 6994053899 0479325798 7210058021 2784808722 1131946307 8156726605 2617034005 5532037355 4825555021 3029692296 8096851331 0902082296 4307339551 6599336507 8121831014 7247327423 2897503775 6305664836 9344460334 5909326949 4616381194 5729550763 2927919391 7313824787 1236797228 6242879936 4409096548 9379038738 2642796342 6838010559 0986021246 9026888620 9033106040 5846138538 9965304791 2124642093 2489667456 3093228013 8824290858 7590929728 8838825393 6003448893 8597976541 7778957791 2723199941 2965351043 5690682127 4193421811 2634856308 1168792875 2033188412 3721998510 3469007657 4014483285 3167182663 4612823817 8506355135 9501782503 2980170753 8774006942 0941496299 6203180165 8425017921 0917588869 0830304117 5130245439 2349725141 6613754733 4747492727 6532083012 1915315738 2930157451 8034546926 9149039850 9916876159 7217609716 9352965523 8052917905 8505793186 1751482017 2018337653 0749201090 3327938315 6279868850 1255420613 5825873035 8611365472 3023438932 7043469332 0010608537 5754521820 4041022358 9535684736 9971002546 4294300238 0922024051 2179031049 3180000665 5972901550 8010367904 6684547243 4828146664 1883776510 4355555213 3790105153 8309139941 5973675929 3319845117 3990420960 5036375609 8398306576 0599010866 9255309772 5174100105 2632357996 2143382399 6876212168 1301684213 9228639913 0477514975 7429612253 9300922546 9848569182 7562302303 2635108031 0470351855 0857260480 9309143608 0088621805 4561360049 7419833745 3654661990 8565645814 5433869189 3024105784 5359726199 5594582582 6649275565 4671214459 4069393481 7563574143 0265321123 3689063015 7076967091 3760147710 9263155377 1730836480 2945173894 9591366132 2950385556 4462074859 7181465752 8853139129 9804238647 9533480129 9301486203 9137003532 4920733199 4403374384 1277852727 9653699485 5587657284 8429580771 1939252701 2174754498 6840245533 6508096971 9620994697 2396566136 3825500416 0926096183 0171037745 8663940457 2759573279 5678022705 2356312166 0495232168 3942467131 8334201499 4941175536 7961301969 4103310889 9164982220 3067570418 8742969903 8505979961 9429527281 7377293713 4859373848 9077520987 0813914772 3562025701 9464368935 4051640315 0062200629 1783315506 6710990872 8222136284 9551347843 5168796755 8171408430 2495072998 1076835985 2229002375 7388408588 8162851503 5159064305 9924475542 3708546216 6296981313 2044909894 3475974013 7108451217 5531158714 3422423791 8045906940 1516920437 2533714645 6549930424 7097168341 3995108471 8381417690 2214471271 8169437585 6305153337 3236057379 1281531001 4334598289 0718587999 3951907490 4714362713 9698592484 9705516257 8665792720 6260745894 6946603307 9749239753 6889075420 0825882218 2026116679 2069716570 5611716548 4817205561 0938734931 9382408167 8042221945 0731813447 8384502937 2947767738 4172943408 3434857894 5778885442 5195269418 6385106529 7007302252 3656076651 3388413815 5167862959 6107964380 4496851442 9863501221 5083275993 1994294643 6599338151 9899196813 1920045557 8444412460 9598733640 4466717215 8963310092 1412858897 7553247545 9624575870 7745922437 2575359209 2184265434 6487526381 9518232874 2194362853 8612466224 2868309988 7644286087 8442714559 3217886521 1945952461 2904354938 1690592259 1114609102 0452600577 6199498976 8194924605 3950396861 8027916835 9213067574 4232278798 2789802807 0692659793 6925403685 8419832166 0655833482 9096354353 9022120915 9876166777 8762843722 5709900649 0710959304 4128163549 0950088362 0258787326 5517900575 4691480956 1265869009 5809542340 6639755773 0520235153 4774971118 3254543411 4746372942 6528993314 1719184871 7951474245 6195473155 9517979317 8126025259 7298176073 7712576743 4071911792 1945247491 4331428187 8182395045 9723450562 0028179357 1213598547 9131703036 9646206604 1301393912 8700502818 1045075241 5789477154 9010623707 3929447929 3689993427 2380822280 3096560313 4127587503 8369711392 0607912898 3614088718 2621373851 1899359493 7583703734 1108224222 0826422924 0031803552 1155942546 5447056320 0585256533 1451814061 5983266441 7724851932 4990662738 0232667197 5988363884 1588299889 4383856148 3806526914 7229169330 9577058449 9793869480 9603551531 8454991071 0129596406 4338700687 0926686021 1200829107 8616866096 8034418806 1200604446 9873637160 1631123364 5586510817 7179830314 9636227882 4146874417 7172513740 4249062447 8471813823 6187224135 4449542425 9519875312 7741043361 5626138158 5813774734 5982189774
• c₂= 2675 7969009550 1933782276 5367212770 3306520048 1993555088 4408357783 8523786815 4828650438 6973147667 6942626879 7374610983 9774399186 2169979266 2545305272 4122649509 8159794890 2665370115 4650038737 9003405677 9828654365 1301360220 7666879891 8371762164 7969639812 4194716228 8175270734 1583834480 8253292560 3960638708 8607586242 4557026078 7032702864 5066840110 1972460051 1401356511 0133321060 2341309915 6678415891 5305515651 0830498212 4479225732 6606068014 6502765860 1956681560 8073013156 8281149703 7555835956 0180327456 5934186666 8781551244 9328368098 5189438161 1481196275 9038918101 2964385948 4061979527 2189153690 1102478491 6880682311 9497454048 5826981729 1343042011 5837213298 0478315422 4437834218 3293315578 1687637701 6104911004 4412526294 5110435033 7832574155 0438240490 6759981638 8561717512 2641887628 7771820096 7867552354 1617607351 4345334234 1172765426 0680480003 0815622969 6637097424 6713604362 7716450382 5994166121 1345184145 2210916269 3139139332 1121532405 5618540692 3772405359 6521797625 7969785238 4957588290 9288844905 8630404872 3708385395 3546241894 8242541230 2187532107 3927268408 7120413482 3907333136 4322056414 3981631726 7792633382 4033272261 2092921889 1904053161 1031656115 6335416461 5671839077 2467096453 1175440998 1754464404 6530546748 5379642270 2987949982 0586989342 0567484592 1401873025 4955765663 3676250052 9471298731 3733451601 5111625559 8250979918 7009762441 6342657508 2939221836 6937125035 9837120168 5131003403 9745326171 6616988114 9538759020 9690102646 6838735664 6305974361 5579163765 2754304036 9677373583 7745823985 5679273637 3263192097 3714451160 8702634376 4019796317 4964083352 6175602924 4376496687 8947939690 4712864756 4481573691 5348992430 6370983901 6581627245 5369157681 2890761496 5462247813 9202575411 9825330647 2863870286 2146156748 7227509597 1354356761 7964916443 0382213313 6968271135 4686007349 5075789412 5012041292 8778312830 0280106518 3205733016 6104088030 5468910320 6727081493 2042938986 6499796918 1104148526 1034629348 1306080784 1256131302 9798437190 2495390995 0458440019 0571014757 8083028374 8912548207 0078729284 3907207368 2318460818 8997105673 1989940449 1925361784 0505973968 0223010892 2208703070 0376364600 1091263112 0312522697 1640477244 2547587725 2619531194 8418265579 5379276158 4904070775 5404381028 3338851570 0782652296 4979211826 3580343005 5897306551 5247994665 8507298446 1397350838 0222224517 1939428142 1986867811 0497615003 0105432265 9692218563 2049525622 3755214467 6363999557 9619084180 3929953660 1107057385 0720525470 4633963990 4102998141 6381763324 8088991406 4784636319 6608444416 7980811923 3673873543 2650449275 5629019991 7797783777 9974079934 5220990362 0186351439 0027012798 4935838427 4809352107 1747322024 7921945307 6043303863 6353514064 1081052495 1359457911 2257689063 2811130626 2759530967 6948039114 8748851721 8085004356 6558720784 3114955338 5375446060 8955772933 2901914096 1756882343 6876572913 1777051117 5299399339 2638123225 7609396400 1209280531 7763798708 9064793546 3759318662 5076566524 4263735288 9823411010 7614421048 2433951384 1943507626 7139534430 3274393473 5842216812 6595094618 1264796133 9617412695 7078965424 0954940565 7297644527 6996935089 8347737579 4362270621 6549792054 7834874704 3274866831 9279968506 4741458031 4699488860 6023329510 3855784147 8832060669 9149183720 3627062457 9206071217 3198760234 9263061302 3916908809 2833839516 6351410620 9295964966 4674148743 8637922366 3057541679 4712663322 1342259089 9790319752 3024612245 6112579840 6626879866 6932403698 4867785140 7165826366 6421609829 4624828866 5346345618 1413510862 4888558174 1887313215 8323757370 9043641754 2040969770 2418082521 1833784940 8135961629 7810844150 3464981799 8527222169 2401909057 8174106322 5900414630 5994973577 6539611793 7050236340 1700801079 2464802145 4653226854 1605721425 2960893939 6193857257 2149475579 1841833435 0346987991 6272629749 0070260953 8371691587 1259393914 8113329730 0120964645 1860749779 9377530052 5700167721 3990791254 6375016153 4419278075 6934020025 6513560013 9164157540 3447283969 6752062789 1859452975 8410999373 0985615168 8853309925 3821561892 6078377681 0906975804 2214278997 5094573437 9012700610 3384754037 8661956252 0326505997 4241627751 0359535676 3806483376 3141583893 6604607341 4580383767 5138195957 7605488697 0310929144 8822250386 9271217389 7015962790 1225070681 5122536666 1294102435 8087004745 5086286300 4342400521 4304389778 0361720607 1171228734 5291417494 7908335026 5300495100 3053929338 3961829464 8547656913 5558903102 6621524641 1369412180 9179074452 1565772025 6733749879 2301204915 1254541612 4479604643 2094859827 9072292978 9392693234 5104560517 1597724953 2526786770 9354523746 6984668979 1140161361 4267658849 2850127972 8169862060 0719782979 8278392021 5525642081 8157868387 1706198615 0999713343 7703330515 8921885774 9731291435 4709798352 7169763215 6511259569 1729921089 7325947881 8208855724 6554902758 3626609677 8156715533 3201844756 0551950413 5985942299 5658891921 1633959848 9164739386 0746955263 4278028740 5648054692 3234373624 2037625614 7774290647 3993511209 8904197150 2171668671 1071517082 4337237393 8094521984 7490701658 8928921030 1279120910 3691021546 1814930289 3122646678 9908771365 0735806847 1828129792 5947994652 2075468617 6755384088 9523514429 2757802164 6078848267 0782318958 8202880719 7243027712 3234738961 7317299722 7337958754

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square (given 2F³ > N).

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