Primality Certificate for (6797^3019-1)/6796

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.679270% 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.376352%

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 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₁= 6013675036 7595529016 7616065459 0172594851 3613737650 1761157336 8789196657 1657722772 5106089684 2539826895 8098733491 2757621165 9701004228 6027685569 9115284962 0510596982 6968538943 4491671703 0596401264 6704231140 4017169074 2620727196 5655717655 6645333197 0395614311 5090212952 9554690063 0582554390 1087008047 9526658791 6043376134 7914019716 4774772194 5929157589 4985903447 1224187940 6983381318 1699273165 4517887312 1867865582 7856195616 5285672203 8381955824 6279047847 4886284808 3670364119 4431523752 2122083055 4124209358 9099753572 0544991035 6394982375 2122475358 2112525910 7288729545 3470176717 6228463342 5993402370 0266258272 3818168344 8720310441 6075426222 9023379554 2347448814 7658590979 3778406159 9481428048 3221298400 5453494467 1200289497 9705673813 1573742209 4289790203 0766503168 7445347232 1140875130 8293212703 0595660460 3348908917 7806864060 0398595868 8467977626 9664176004 3722301993 7495947422 6308863251 3091324331 8387514068 2935428329 3894965542 6169671028 3127872019 0956559782 1570032083 2559040465 6926572987 9006085593 4590064245 3817308906 0583968250 7427514495 7047966150 0926319147 1080456281 6397082977 1605195245 4471223918 0438492975 8276717878 8532060597 2692655125 3850737243 4285433642 7673829913 1999982461 1290547472 9339374338 7798588095 8307088662 1196335279 0346386372 0010512290 1703602531 4722795606 3992901009 2561836388 5200579807 8909057510 8978255377 4720794501 2286474580 8676840507 6432635131 6180609279 0108938434 3470769361 5378896409 5508144241 6331202144 7808223953 0004509196 9279814547 9091272537 1235199858 3291865814 1462294218 5696739829 2036226927 7409590346 8925012188 9465278079 0352168115 2512287447 3397909655 9533022417 9283697018 7583221687 4551399233 1686255772 0210612083 0059046371 6667625107 0702349103 6387790655 0469872771 5366490387 3256346097 2780305340 4587166237 4885290423 5537121670 9818085879 7151035702 1138241186 1566385105 6039618334 5424611848 8764125854 8165929015 3201687929 1751837991 0294211015 7764184306 2644877407 7659562719 4513882296 6087679825 6052548547 5245520607 8695210076 0483752795 5412115024 3820369522 6891358112 5507361160 8679645705 1206273487 4882983556 1256720635 3269250840 8456317920 8917828041 8917417363 2686497223 2322746567 2732381976 1907762819 3280073474 6882958159 9787598373 6086770042 9032894743 5843802678 4921796962 9749304120 3101300980 6753834085 7028478957 6911713650 3298902109 1891888904 0267979427 2593962537 1259323260 1186677860 1175079162 8966860115 1185067148 4855119982 1269830337 2254010734 7466210596 4517537609 7664803767 6680105145 3929506381 0066732594 7110887419 2470561453 1152554288 4856440183 7703534284 9132085122 8905018044 4599678947 2197791995 9665443179 4096011342 2252395608 6697574556 8205265646 2784005702 3705606911 4084213942 2197111807 8198017223 6238753324 2545478803 3144661353 3225703767 9577479258 5575428951 7020770520 5479471120 9383481722 9215212381 9335194689 0295911825 0160114770 5562557128 2979686470 5388668258 4710824867 9075446314 4768804442 7608101357 0378409874 5451972902 9258942134 5732231449 0718394114 9294828751 7668223519 3950659102 4695833620 3575610304 4725284072 3668492700 6740496625 5701488200 9480228046 2582324502 1267023561 6765925818 2371222696 8827004298 5510065869 7498655236 7704326896 5445623202 3296366068 4455310787 2717642049 2598025125 8167267211 4497523500 5451347337 1582365268 8939589092 4515834469 5306279043 6989821772 8933762099 3531492540 3161256239 3570414966 9351963365 1388253904 6000294051 0392441721 2398303525 6714911661 7195378515 5118543633 8403985771 7532547855 3944008848 8084909556 6829691955 3822668841 2736599156 5274361749 3185570939 4100227500 7591591278 6911157659 3161545604 1813443983 4787771445 1755645230 7068304252 3900437103 6239142883 1473610977 3012693225 4913186405 7036367478 8643068272 5530925112 0366114473 6415312902 9914727552 9671417799 6739830588 0678502280 5413257671 1159660098 2581675925 0412733810 9217461549 7702333032 2389356967 6190056052 1161010313 9415109897 2022360859 3794823089 2772150194 4332111089 0978009675 6019627864 6153063540 4383104843 0073359465 2288241095 4505414949 0897360662 9190870016 3705899860 4303850360 5192106610 9717204338 8484850655 9804083553 0642234222 2214234730
• c₂= 229227 2874004800 8448264152 0968456693 6505861403 4908739121 5921656610 4117000043 5502672915 2497527585 8595244066 3169706951 6020276086 8003233331 0901770671 9198790140 0568794929 9053457241 8019158763 8629963141 9519502075 1315865931 9789177765 9061556438 4312601305 1995346369 6748970535 1437119778 1813021352 0087934483 1226042465 5846458560 3842787808 5848958812 1305852216 4689144014 9707740997 3423556768 9333353515 5592723033 3969769568 2265186788 6544317289 7084053379 9057118797 3135518669 6810123905 9902168329 2300932380 7082677490 7820760964 8755540827 8815196407 6900690339 2699315580 1606515456 4239054379 9007510484 8463943174 0967798539 1579062610 0324673141 0828110567 5868986973 6395122468 4630979461 0171304640 4364292280 6243803865 2369987129 5995462123 7734738000 4478282555 5292336991 7021139111 3699975596 9740126358 3154203076 7431777321 3665942481 0960972361 6830478829 6494463076 7719277777 8461968292 4858874565 9200353634 8955431447 8656824405 1237317555 8743101509 5680820136 1986113268 0227069895 5942028869 9106466384 1019782625 7963881749 6577630408 7959889623 9890052133 9375980230 2204899582 4966123878 3045094079 1929054840 0669444067 2702244847 7535810391 1164992830 0340469882 5710009127 4763482720 9366186981 8823168186 7439769448 8016288543 8256521061 4765505413 5604624038 1965817905 9737352416 4645415100 3743699901 8046552688 6134116865 9532159136 0424475998 0425112845 8817273961 2574991098 9368173145 3438097918 8255877898 4398923829 3315468021 6298174426 3432762316 8893288544 1977225918 8818820918 6863844966 0975457178 0278021989 0456206792 2365834211 9195516019 4095633578 5909937169 5996521543 9264311754 4557329281 7086204731 4526715604 7818151953 1320261354 3713320777 0448166754 0497345322 3456384679 0470391008 5671409653 5094839899 8412447750 6927675916 9049073176 9862611520 8984115837 2015507297 7818222722 8281011521 6026011150 2477056492 7866931867 0662353979 3886231325 8153570461 5710032674 0444589064 9842765716 0032588383 9078199669 4067103717 3425229837 9312221998 9892835725 9562190614 2949102897 1314922151 2990590154 4844586324 7353483853 2892842406 3476794208 2548437549 2859921842 9665093225 5076025952 4239189929 3741802325 3937668320 2954778227 7136204660 7862294742 0396936877 6712351413 1232341535 7276833088 4837660105 3852152552 7338662380 7899611043 8057349991 1844117305 6172500124 1310835605 7690098415 2605965702 5304460709 2541473735 6728852453 1666431549 3818713481 4712735273 6568859700 0166077604 9743626881 3184907347 9591081313 6320935239 2764128129 1795061758 5566123314 2576590271 4951512428 6852743167 1443100122 8011635645 7859127733 5839722741 8048360359 1434120068 2786602798 0059649432 5164726373 7020437888 8597752903 8890956272 5881157506 2087376648 5037314040 9809969420 9348142396 9621626854 7327125483 5222750481 7083496551 8340030096 4717501665 4009430458 6666658527 4669163784 1013478892 7568051424 5321390509 9551391742 5073342563 8026894358 2374335064 0061471422 1959858989 2452215245 3618972833 3059480895 5180529124 3073337435 0894256814 4534290884 1440322670 4363483548 4567855462 3798629440 1719547308 2227890319 6327091779 4150972308 8325606980 2927610037 3378901247 4571814315 8937564939 2970744956 1621772852 4148781898 6909648563 1882780744 5281688562 6566944729 3571767876 5680153652 0439768181 7779034778 6282624187 9321879645 0851734948 3313341373 6413644217 5026029293 3400929196 4801327438 3022932218 3854974524 4994805126 9519431197 1877358222 6420289564 5012274538 5458366598 9613356616 9004164421 4544858167 3224589622 1362049713 2251158060 9026070489 7086319882 8744503076 5656860397 5265134559 7657517101 2202385673 0451235219 4538979005 5002771927 1143162169 1501082641 0207425660 5589193685 8787764431 2459117981 0518494395 4201805242 6332298671 2112987375 7699789092 1087633418 0182117999 5225135978 0209231385 0912241343 4166194247 9043205621 7963725311 5887143119 2965896928 3995771501 9255300368 6239106520 7442914144 3378516523 4489253082 9941826925 7508575032 6627620459 7598160206 4051016326 6980435232 3105112691 6994314583 1388734574 7350148663 7191551578 7360608285 9334371048 8738293843 7445881158 1248338712 2081262879 1805608531 8250376548 2951980463 4568429669 9426450238 7104705039 7091621384

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