Primality Certificate for (2879^2851-1)/2878

This certificate uses a theorem of Coppersmith and Howgrave-Graham 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 28.154825% factorization of N-1:

We need the product F of all the prime factors from this partial factorization:

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) = 28.154825%

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 = 437 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 three 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₁= 84444 0133582458 8611651218 1826348226 0194231505 4936942023 6842252945 5176329365 4214019830 7010505832 4160137478 6543886167 2274516388 3919579311 5119620641 5223418443 2709783262 2524263144 3265739785 0176247057 5929211782 7721727497 4434068610 5127241179 9196140462 3995623209 6297748384 1708037511 6349574374 7045863579 1959880923 0624710651 4827587020 8312803239 3232192623 6680060854 2567929395 1306218238 5690177600 1333541300 8240717847 9265650484 2544881186 4983244646 3455773329 7713219599 4099675700 7305073262 2124097933 1511969418 4796332676 7910529533 8307369261 1977439136 6978305156 1918464802 1532073187 6810156200 9125125507 7725688416 2934090149 1857308539 9629359141 8885868407 2321382850 5315060676 0837987860 4355298203 5008736005 1240236047 7270630333 5820670326 0950920660 3977597663 8410860510 6228886142 8517886806 0772465704 2223052905 4759502708 3635504236 0320016949 6314332942 5882515121 6172940481 7395755047 9612283774 3499017868 4555162674 3170098668 8139499389 8998328222 9323143378 9511214372 8939214593 9766233681 5653854332 7368689130 0082992248 6410211371 5895278090 4677697963 2437536166 1530217199 1617961847 8210698671 5283536835 1729840635 4578612428 5363697003 2680490245 5341703938 7687764511 3838119932 9360836655 5041571653 6781031712 0315435793 3095433873 9656840969 0849884202 1770050548 9256208119 7530081903 6728725909 3288505572 7332899899 1817638857 6902643402 8170895743 3668278057 9883420637 4930252981 3458961170 5242876017 1797686077 7783434112 0713470424 5314574554 4466322352 9985143937 5115224382 0641771378 0365948371 1797789458 7959643046 8939970207 8701774265 7224778012 2503896939 7902012115 1160975490 4298027872 3547894239 6640704803 4947439778 6124777777 0576801190 1810024897 1060086461 5281137822 1928936159 7462184133 4452674141 4164217735 9199537160 9971654843 2216767336 4605636115 0041357361 9669780052 7530631117 0238605500 3437936607 6377450448 2989157723 2464169907 4213504407 1668566577 1299673192 8027289774 9836974588 6873056012 4406785128 7560027666 4251734276 1331004052 0071817318 3649888688 3325331120 0621494466 1855498497 4586983352 1636261609 6419991228 4501183498 9732285643 8522511383 7756238242 7686879771 1155191740 2162802913 3561634034 9751634791 6119731824 9094149953 8887846280 2431213074 3754507071 6175928291 9791531616 5639979241 6515553613 8194610450 0147837916 9274841525 5873152828 5031891494 0937807468 6547387380 7803914734 7882719039 3167562984 4424798263 9479459787 0137184935 0317714646 2046084767 1468744807 3079342850 6734989024 4487393243 8002168106 0720455690 1846934984 8897270338 1322901937 6791749057 5080169338 1569124918 6933580723 4386857911 6901568695 5617703696 2219934028 5442100802 9583560112 7051128269 1343103371 3824658284 4683378889 5561721514 9427747170 0715683325 3783417837 8929549724 4740355884 5624325172 6576316401 0543057824 4375515777 5940900109 4082674384 1198297850 1522906617 7954965416 4394832305 5544605941 5029801154 8997585628 6595415851 6454405027 5369044012 2721204677 2434009148 2895053416 2014752106 8096291701
• c₂= 22974422 7810880508 0671671982 2121961452 1262215100 7501171357 6778573245 5938913047 1274864997 9172185356 4334484960 3721872197 9534052059 9145383512 9996906219 6174089865 1393110152 0921496043 3183284434 9613525551 8936188806 4999789537 0596671665 1289988652 2537600841 8263640301 4005614355 3224325512 0942621403 9913417149 7907564755 4796594904 8294336486 1102184349 9695649021 8636000384 7185408741 7848012327 0575812999 8439469030 2471592621 3575011638 0410075382 0208842074 2674764095 9223534475 3117869812 1412027034 9927809116 0415156034 4417338762 3914247994 4110202713 1992376076 8309985082 6221859984 8373417480 7217153386 6869616949 0787826895 5308251906 1187564200 3692091376 6699220031 1328963324 6495511298 2829374439 0859911850 6558416625 0737608631 6438489758 2227409247 5970008794 6113778908 3735058872 2476875741 9783511643 4259000244 2243609044 8604449544 4150235344 1509694919 5698456195 3932592301 1659727261 5020289142 6830674561 9081392479 0948665754 7896682031 6204487790 1606198886 5134850170 6428326871 9142236103 4148789765 8578374999 1200402151 4572395815 7475138085 2233074087 5113511172 2055880387 6449371999 2283987989 8355241844 5806478093 2121652716 8046533255 8209717628 0882366391 0040433350 3029605532 2240948621 8000253210 3269194706 2566749539 6930076008 5451768299 9206607013 4733383557 6458351574 9949902779 2289629997 0483277054 4905418350 1656152415 5517753641 1834482946 3321056851 3027940401 7047023968 7291009402 2729062994 4027171543 4440670632 1992656490 8019746574 2648324352 2805314675 3786111463 5994275054 5752373018 5050211213 7648701995 7135043879 1691477129 6308839710 8295057022 1853051858 5670756084 5986662042 6044858502 7705839184 1017199421 5306794834 0074896445 2449987525 6621904664 8385911160 9462819394 5671346619 0360429128 0251731952 4312154027 9316530927 9732235732 4885268020 2088579183 9693245064 4142406892 9512765746 5975313076 3209508538 8391270761 9908124590 7829664629 0062648358 9381387209 9389564499 3972776690 3676767473 3373418256 3431483022 4511782609 5059645923 7793317178 1023744429 3846862202 2379157162 7689894702 7785424690 9898817106 7865790174 8491044526 0067958870 9696617277 1410494274 4699080082 0723127011 0039264302 7286750801 5652830612 3015817421 5726809067 0215779114 6541284391 1666399560 3467144104 0454553096 7033441381 5228843282 2642516368 9202558312 1442478001 0474670072 7167535204 2621897837 9727007034 9943246132 0317223494 4231900168 1180032941 6886025228 8687545722 5834379340 2338481952 7459617366 2203648309 2850514162 4377482667 5410795538 0675012664 2257582813 3484714677 3434651165 9007503432 6309587904 3036585826 2806973410 0467351466 4807962496 5845740559 1664722707 6194002264 9141529698 3292611705 0179126300 2704744123 7987689654 4492594083 2529725237 9373082445 5478933665 1866499031 0214989664 8125103135 5850533883 4235644693 4431014684 1338972370 5148292016 8537492261 9219858954 3719464691 4304585462 7972881905 1211630961 5785674490 6442341147 8032168068 7316701113 4319175061 0105490537 3861018503 2189151574 1996312537 8791741308 0258979806 4383754600 6115091931 8963848716 8572943835 4964041748 7945696186 2068380228 0735102513 3326478246 0251201046 7300291151 1392705872 0034007055 9820081927 7096509072 4184001200 2430786317 4675521213 8681210747 6670609828 7915864252 3975603362 6694600926 5086204268 7749406315 3908328864 2106488282 2687454564 0375814662 4034871965 3968716226 2008250656 9172572479 2009516600 4115142242 6868745508 1724861067 3582259997 4882977161 1890423290 0575414532 2099010433 8497578720 2792109094 3481408247 9729383880 0955877036 4556896605 8124572172 9110687723 1104871318 6211009390 5672801633 7683988255 7891679234 8670722553 0323586642 5087439981 3600235891 1579452854 0565311807 0688790219 1023667988 6106112369 9371548457 1908978125 3505994417 0691418463 9147396807 4687119580 6199462526 1602953724 8327592756 0552884741 5070036975 2532038459 9727472277 0362101808 9409694240 3564413066 8371361736 0342623838 1547721844 6431556404 9507818622 7235439774 5600536240 7558316809 8775730930 5191595565 7782965811 9920065035 3479176314 7414274697 3544697582 4545367716 0552421435 5287730878 9723024508 9016330443 2119589032 3385640912 3781337215 0749207773 9991385472 3181188723 4992992475 1493615849 8715397353 5859869734 7624979489 2639473309 0760900464 9262920527 3197045391 6348965553 9609710343 7977846303 8287757746 0212281185 0685609688 2794060145 8708695961 0092919410 5613545013 7030971134 1416712612 5318570122 7869488864 6781927758 2738577653 6586954647 2524945752 7256453110 8214959330 8133257122 6880148123 0659152952 8532526954 7734268345 9445019938 0552235696 7453148040 3120511498 0006891414 0997578614 0478222204 5316017602 1287151221 9926039266 4040001675 9787461693

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N has exactly two prime factors if and only if c₁²-4·c₂ is a perfect square.

Here, c₁²-4·c₂ is ≡ 5 (mod 64) and therefore cannot be a square and this stage of the proof is passed.

Coppersmith and Howgrave-Graham

We are left with two possibilities for N: either it has exactly three prime factors or it is prime. The non-existence of exactly three factors is demonstrated by the Theorem of Coppersmith and Howgrave-Graham, here performed by a Pari/GP script written by John Renze and David Broadhurst. Here is the stdout:

Welcome to the CHG primality prover!
------------------------------------

Found values of n, F and G.
    Number to be tested has 9859 digits.
    Modulus has 2776 digits.
Modulus is 28.15482488% of n.

NOTICE: This program assumes that n has passed
    a BLS PRP-test with n, F, and G as given.  If
    not, then any results will be invalid!

Square test passed for F >> G.  Using modified right endpoint.

Search for factors congruent to 1.
    Running CHG with h = 8, u = 3. Right endpoint has 1532 digits.
    Running CHG with h = 8, u = 3. Right endpoint has 1437 digits.
    Running CHG with h = 7, u = 2. Right endpoint has 1300 digits.
    Running CHG with h = 7, u = 2. Right endpoint has 1242 digits.
    Running CHG with h = 7, u = 2. Right endpoint has 1125 digits.
    Running CHG with h = 6, u = 2. Right endpoint has 924 digits.
    Running CHG with h = 5, u = 1. Right endpoint has 733 digits.

Congratulations! n is prime!
A certificate has been saved to the file "2879_2851.out".
Goodbye!

The actual input file containing N and F and the output certificate are included in this file.