Primality Certificate for (2781^3121-1)/2780

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.235209% 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.385127%

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 = 43 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₁= 16055835 2285455572 3726008012 5674023677 4180062467 5265596053 4969859334 6153384446 6568171592 1768666106 1141085157 2545620446 1388855328 4181941246 9426001090 1204717235 1504449406 5122024222 4279462357 7747434626 7443231888 7269654165 7960577011 2316948867 3935505199 7701129664 6392374149 3511541733 2835694982 1486041533 0608005325 6927891557 6248662380 5713261454 8162570419 4659984628 4588669133 7214369215 8216612373 1590887853 8371799779 3901050153 8363920073 0008869600 7912987698 5332276720 1869073088 7669061201 5079813966 4016296261 9470814076 6013022386 4354306227 9384312406 7432372384 5261759852 7574578665 3019865519 2013878101 4285783800 4994970166 2654952961 6617082259 2209184388 4429068165 8510436691 5162012845 1679080326 1977833247 6618267529 7242163648 2997390132 8467784924 9574119622 9242454680 7339490040 4719870323 7868194314 8566627921 8378357971 1710655613 2855282457 7225724685 8745278657 0268495026 2427056615 6660722957 1733003465 5534048996 9441477463 2377536863 0979406826 8979636520 0100258608 1715642670 5522364693 1935499769 5196502871 4096732576 9512610033 3576621461 3075918606 3291065510 6992856296 4493391665 3852266312 7121774327 1508321107 3535316461 2497017519 7578741900 7475933257 7504280896 4799286592 1908398600 4724782190 5967979855 1766375131 4951794417 9786540804 8918903284 7053717236 9041316558 8998015398 9278628111 5667202971 1600185207 7965794573 1825221567 1910160167 7468622053 5401334589 9389498133 2439400291 8318937371 9962112261 6095713281 4082032299 6910280781 4542746281 6349285615 3017655772 7895617119 0857785102 9074291423 9945616544 3892410269 4665857812 6101462835 8335574691 7375655867 0431255048 6568259212 0482814748 2787920142 8379989648 2578870243 1208844544 1639793040 8177338545 6737361442 7504982011 5295366889 9060546651 3474726909 6954432703 5842345545 2900934772 1728386527 2050726672 5060934401 0395304404 8586960613 4884410465 8491779121 7925457645 4456155144 1404301472 8884847742 7237420582 5515669761 7197215474 7258123715 7548695784 4872870075 1664784634 5924797348 7385112278 1009859524 1045965455 6298002932 0042700653 6518682305 8499781650 1375742849 7915898888 1848979683 7070180349 3439618668 4030298555 9272941422 1373820301 7263126276 1519351394 9636061867 1553128618 7894103582 3912682896 0426522477 8628474136 9909380947 1601884863 7615801298 4395100108 9002602716 9327123802 5358873393 4957883402 1636798082 5416499375 6519439359 4764122490 4315627767 1058540664 2569222931 9347596703 7499412208 4018171328 5965149666 9965995473 5123602194 3120239417 0387936262 0401821724 5385601107 5428138488 3690414739 0702139044 0114629808 9226678246 2344532101 0002924539 8265041504 6193475793 7712854251 6051296569 6032840529 5558805688 1012774313 0443602672 0002794507 9885876789 0324069994 5075041969 6329784780 7152613386 8337543782 7313959236 8237995495 2534366530 8588051056 4495848067 6268373446 7356997110 2749959126 7814055204 0154411203 7280832489 5491187511 4589054740 8763334277 3876924406 7950267847 6443568741 2585485867 3868910622 4868389345 1866042745 1266823190 6829974257 3975890011 3939068747 1089822516 6024697896 0893855272 9268465378 7944762618 6980941406 9810414445 1682636865 9363283575 0803459777 9415274050 8846943894 8045529174 9613825205 0385566663 1927813861 5165722628 7142444806 8080187441 1827686578 6261575633 1492389199 3713968669 6837835457 6443565059 6081114334 3408304753 6503087861 6929200140 7781600173 3084552075 0658861920 8410961696 1338041250 2128078353 6684672865 0264703012 0074027346 2077319062 7565284705 1315993497 8732171638 0908525944 7854710663 8543589449 2159475457 7399703581 5121814128 6247561668 3829006005 7547456400 6637129945 5647497455 4066838280 1319062680 8755975235 5148076592 0827188910 8580747914 9756482930 3866862473 2250711015 3343878353 8873699042 4448508667 3023766779 7039184453 0853634491 5403844107 8604950540 3421294283 6673705501 1118785635 0198640341 6751410682 5491837268 7780103560
• c₂= 6 8819003877 5661170462 6659855516 5608734496 5491626276 6637763289 6687200753 5939244661 7966236346 7351407935 8569459782 9685907057 0708555833 2004041435 7994919979 3546876108 4139892889 6294199738 1364332715 7716047937 8267165823 3596812862 7407754463 0383215749 6854638031 4713129493 4924227725 6020569686 6966700365 3507682743 1797444575 8652283030 0558083257 6630441434 3778765990 4331278510 3589886414 8109297455 4410020190 0447011851 4493552191 3727761749 3063544026 2712364450 0790436510 0630917260 4391320657 0871648915 9897343709 6923201475 4327544014 0188532457 2356616259 4770987341 7384845384 3070384779 6915427729 0541427612 0791237040 6896002027 7691952244 4825209588 1825795801 5850059102 7763548227 7704770402 6338468550 9047550934 1187173023 5486488355 9222971036 9277677385 3200954983 0990250054 2639425781 8237847599 8613713137 2852114265 5680467729 9988057990 8788046905 8012557109 3394394257 3768006254 7563918213 6468547553 7177893091 5510198482 9742524698 0634262200 6287314006 4432832733 8022059598 6952941435 6218956372 7598025119 1317853642 9080132312 1140687050 7420523566 0831613821 1282949309 1892916512 3673496090 0166964875 3892787756 7579903350 1763525301 6696316044 9709794949 3888076059 9604471227 5376067119 5104914148 0121971187 7844806227 4167418059 6879794504 9200752612 8375437561 9140282527 9332998518 8285383187 6450732417 9615770785 2890528419 8212559750 1821888140 3626395578 7065539775 9488664073 8769575062 9709726358 0784453569 3413250509 5131371749 9070150560 3502384453 2905835274 4225238295 5870920377 6370718832 8314872279 6999088974 5624299502 0951126099 1335674042 7340162538 8787127365 8906161113 9265809317 4984536750 2002823136 6916302940 5269794251 2586904889 2759123693 9650701938 0991701263 0482953185 5641422471 5532889527 6101165592 3089040627 2608412513 1025361175 2405014346 7598634654 0604537906 2060894545 1864312422 5392970004 0345059327 1402565611 2504159945 4834940774 6846004518 9645799305 3113852151 1691713462 3403859411 0415627758 5779979767 2425361418 0827582128 7178122141 0944811932 4434048322 0117912462 5337256615 3021813688 5421166591 8829329092 9270512283 9770142328 0326563003 9125979359 5520535955 5062684958 5759498979 0183636905 9833649386 4242873192 9454619410 5677201294 7871614055 6777801670 9668909081 4700336920 0776373793 9621731713 5545826090 5263853633 2997153734 1457620978 3424865287 2057941255 0231777533 2930835552 6556342391 6216500030 9985179442 8382769046 3854858108 9536047841 3860019751 1176023949 9963960473 1789102480 0045938467 1872285911 0334272381 3613733187 6279921404 5655111763 4982031368 5396756433 4491596335 2218533366 2095638784 0413932447 5177850952 0590050533 9009935237 1927812441 4116522170 5183703149 9781918502 8342806210 6912216642 5046440078 5838772814 1546502464 8921006837 4699540071 5721772931 3480589916 5334184633 4559410761 8154903497 5439774520 2602380383 7613471001 4995767617 6743594623 2105215219 4244179414 7219875702 0288059397 5713324327 4242020002 4749000867 5548495776 7839807832 1660532758 7170469263 7723363680 7939201875 6245609555 2239796356 8622354783 6134370611 9222800056 8794632791 0022172263 5223751570 1260635754 9614008819 7500618434 6854129947 9924509587 4840554702 1553473774 2864073526 3373992475 4466799309 2916642508 3162981651 1438193390 4262378219 5089779979 9456338024 7491585178 5396045637 1438364060 1047007764 6931968252 2207938765 8897873774 7111164834 5596441241 7043450212 0249830461 0251699915 7986646941 2520800827 1102644047 9789548983 6406227801 7548943088 3248162072 0694929423 2595762595 8516044141 0442448809 3607062883 3071250244 4168145095 4322844535 7810579891 3297914272 2027469604 9755357196 0778578109 3663369908 2738883744 8151453824 6206567587 2616850967 0288817266 2426046190 5961041308 6317112893 6348937936 1875782381 7133777253 0027808833 8589741018 0998430049 8645481382 5470304880 9927599352 6987588863 9025415533 8223016041 3055714036 6003777480

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