Primality Certificate for (6113^2767-1)/6112

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.717119% 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.377225%

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.

Express N in base F

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

• c₁= 242924 7695331782 1943884820 8308317005 2367754969 2911718674 7556459063 6912001994 0693975210 4009007389 1814932344 7540162895 8856841329 6705331717 4144650243 7005441370 6292913099 2961033909 4740923480 7048636636 8589772540 4118987386 1030775240 8377919946 8142979405 9287052354 7617468017 5656870605 8804602685 5693081443 5569966211 6577789605 6490429374 5156011651 5987497480 2293198181 2128716304 4986238544 9240194525 7737316991 5440964475 8187539748 0157332452 5384496173 4074693755 0903137188 2732619775 2080187290 5729932548 6115478351 7750923006 8830526354 6369028943 5959344416 4409085714 6054938008 6215416397 2701850226 6419492027 8187647732 8871044066 8984448145 5022951565 1349047439 9498344032 8516875929 9604177299 5436886300 4049813687 7441114549 7002905029 1569755315 9401934576 0619029632 7426101712 6623623685 9036390355 2375401379 5532953859 4574537766 2089587092 6084715619 0908406961 4796936475 7544691498 4646997108 8277459888 1262133134 7294206050 4563604294 5487850064 0592576554 6984066973 4853137761 2558916503 9203519739 3879542417 5213420581 9145976765 7450480919 6918855127 2892253064 4992616353 3251172288 8005936619 5373989534 6778626333 7875872026 3683863117 3744116222 6479683484 2627654708 5117956397 1602532561 2656420011 4903090078 2280236536 3818229114 6962956763 7172530890 0237580556 5720555140 3600831755 2703265495 1388216621 8257371337 1884849855 3794682111 0929219614 0276344007 5186923686 4747775253 0135446976 9776907657 3160465647 6010774308 2182097959 5063343937 3903164898 1518492382 0313351045 4506478025 9129943976 4822191992 9599455960 3727007379 7219522572 5356932981 2337945445 7732294238 6324167914 1239757793 1933133369 1445977918 7776422707 1544452520 8102963898 1414039535 7081268681 4756803684 5429295264 4112383097 2228605751 6739772010 6086515714 2300631724 7609262713 5357457038 3669512672 4633697548 8685566697 0811721767 4367480144 7486330289 2160908760 6315907508 6793822724 6631197765 6015819760 4798624192 9756723937 0976043180 8779866664 1101702090 7252796048 9230772624 8020132821 0233432195 4965346518 7167612761 9474192840 5154984149 1535339326 5556333144 6961015979 6045651698 8902747479 3366289783 5509295943 2817183357 5517108032 7039925620 1087769928 6449955923 0063710455 0406783526 8720783465 1738651622 7774718175 6626190195 3432589502 7413853328 6272400777 5471975663 8401282898 3151815541 1920616417 2802821772 1085793618 4904274493 7175192250 6551091895 2243506486 6287925501 5967387491 3551339869 5584754182 9876147676 7379768951 0424919652 3701621216 6604463209 6398166855 7063898923 5008926912 4532919269 1388488448 6434872360 2107116121 0525149119 4000622221 8071541524 1829313834 3509772834 8947246247 0601159918 3954547323 9609737011 1496809823 0100875182 5150832365 4407478229 9659081269 8378723394 3652779964 8031570109 7966619328 5171466978 0967682085 0832844710 5881880756 6097517150 4932952139 3003856689 7018410760 6358702955 3347187295 4482126626 6348253073 3886879113 1216787720 5775560379 5012001891 1583749482 2432012778 0856815624 8926104705 5265029437 6989833594 1510732832 2068649919 9744264569 4386382038 1680416807 8454606416 2224232109 2963546431 8068798197 2840150463 0052350594 9063481771 0177674999 7678803894 7679105502 3851753987 2228297657 1075590460 4878146810 9807008035 6529836590 7593378914 4613607220 0649071090 1586173058 4460380451 1246086339 6585675125 5669422233 7490450115 3834522405 6962685192 4355926080 5407164447 5467224624 4731958421 7247698371 4611830406 3780614904 1017856363 3659196590 0919726944 4116656619 4111659154 6487946057 7758691042 9081369182 6113772136 5320800504 7924371496 5265796228 5995957217 2359889447 2525980214 4989318532 2661661888 0517847776 4130347004 3579412644 4422312840 7062203131 8515518848 4274553563 7341727720 5471898733 6344166454 2846805505 5687904794 1337482767 3984489145 9972834528
• c₂= 54 1100383965 9115566588 5655991766 3604289126 6979909724 5741149460 4362957527 4113399778 9598912244 5148941234 3667598242 4209542245 2331677238 7383886222 6956509543 7867323933 1089303888 2069937678 5372470982 6716757150 0475909980 4871137600 6774346113 5623353122 3360160358 8968901682 7187041778 5915486579 8248595851 6442479089 2407778795 9104168845 9042199651 5517358624 3151185352 5965457570 9365113784 4655249650 0686756771 2740667592 8540983247 9440510158 2041180464 1546611234 1456665931 3634807152 8536980865 7024070217 9630141947 0680576973 9721914426 5580988061 4929827066 1524251746 2315256628 8136035580 9128468390 9700574277 0982427687 3375491364 3327286036 5358028044 2026697586 9966155846 5974627415 0706362070 2451383365 1623593371 2428035937 1236390212 0303548924 1902726398 2819767125 5481046722 4008242137 9218801135 4020249735 8083676657 8038707653 9728141757 7701590436 9606779931 5459537774 5941111549 0200568405 4167000700 2890089552 9978834747 7115770222 4155105908 2066012011 3383992050 0836268320 0308497070 8850907873 6672668095 8894198414 2791578041 1581351275 4524688691 0536769880 3608856329 4736921303 9344053599 8244238808 6698668838 1500273880 3170538153 9923915614 8489093317 0970913241 6734416486 7038318282 1784461931 3721035385 3501830202 2092513895 6758362807 4997788480 2619907159 2915311289 3304425056 8182069811 7364615077 6808020501 9516089431 4949377005 9754105993 3675264886 1435363460 4763107676 0626705134 5122423177 4586485005 6988001600 1187541270 9847568813 1306134043 2964414346 1554943613 9287749724 8561879598 4259157720 4506569857 8511007202 8874945517 8182894767 0148878708 5054770923 3181803294 4671240784 4066751933 4793506269 5472997731 0270233199 9126997876 8752419161 9441389265 9875558601 2298058761 5571533163 8564290877 3449654743 0689329780 9384580581 1673928938 0226973495 4993511343 2485747781 2575343547 9121999159 3716562047 8032135943 1941541490 7283692902 6332726157 9943883470 6652564118 5639663364 2273279348 5621617491 3595982906 3238094014 1308676070 9312829604 9471369916 0342820388 1836395796 7795177852 1043178857 8192110860 6789779542 5194807884 3248309176 7971672129 2419618835 2996904617 8580558183 2319159036 8212104541 1339188907 9066700213 8400341043 6660202902 6552650798 2185468897 8158863951 6388798785 8724961499 6385167527 3691483637 4934301806 9753758054 9860601694 1740074700 3259941383 0387662259 7150256527 4910444050 5719490386 4461138189 0804987715 5860382644 0253131791 7792627716 4034613081 8733224924 6541551471 3915891169 7438374627 0010785383 4619595877 8882801501 6844515784 9916301830 0899108872 8289435823 1777382318 7136146492 5766155942 0777001618 4582369366 4747480099 5445502135 7254608231 3205934647 9560297982 9704058482 7305632995 8465806611 7991032979 4059928989 9213962605 2309386981 8145444414 8670528659 3070799985 2042939539 0959943941 0666592025 5060905082 1863988127 2123460297 8150167950 3805799937 3603625593 2038548901 4413781746 1891436244 9430092514 6897643942 4342407637 5845306583 8813544816 5074843970 9295955217 5022742341 2569892473 8257783681 9620471484 8421984635 0194928572 0036197038 9359220119 9435029382 9468099063 3808628027 4373299089 5324917597 4422191519 9597226547 3719185900 2949381786 0542261449 3556931686 8468236255 0250852433 5782730736 6466660506 8998471985 2510564429 4929530257 6609214231 7115216524 9608953889 3523449150 9972474118 8056516938 8881276874 7435976756 6017384853 2108396837 6906650595 5902437723 8121400665 3867072933 0521712178 2295399685 4882108139 4283092462 2034325415 9048777650 7001972397 8526285245 6497255018 2878028859 3765959252 6914295197 9609435157 8990848971 3230789163 6297452167 0452242920 9398967887 6309314014 8094381891 7632562079 7461897355 2227964814 8964257138 3681205994 4412757937 6161841283 6261056811 1095006275 4099190601 0814426417 2657701294

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