Primality Certificate for (7372^3889-1)/7371

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.701049% 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.701049%

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 = 2 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₁= 164551 5151852154 8676070985 0878916399 1143584937 7878530792 9629239073 9940932473 8160767568 2304729831 7239704237 5707425980 1347242984 1338412411 2552541225 8124320048 9837573167 0278885941 5874168611 2206255160 5391690818 7964282325 3993793507 4428785271 9497892898 4527201616 1135755880 1151613814 7802092721 8645177608 0880937268 3307580300 1690426598 4646616179 2879835595 5928196043 7679515325 3685562051 4372270360 5791388318 3422997577 4223392732 6033876918 3177050514 4389083273 6326498340 3947164417 6022021783 3100422560 0035930471 7550136260 5749239185 2138247459 8960796633 9122024282 8685112155 7005227969 0987821403 1288307322 0797119048 3839103200 2064564544 7514766395 0332259042 6667865020 5071580500 5013791062 3879736854 5039891909 7313034410 3784388658 9609090413 2256806929 6872906951 0525575988 0825766031 5257945238 2326398562 0824588188 1410173128 8915120657 0187238600 7209562868 1991365563 9646664260 8203563352 9123276251 6493828803 7508379083 3146953395 8182737768 6023252998 5764421444 4116249858 7532779582 0525592427 0894755364 7788524162 7581777831 5232914122 6743659891 3685950832 0614826903 2070503400 8293068260 9648246648 0416609672 7104726776 5164047647 1319130584 6073853064 7895509714 1838603368 2923651236 0436714350 8056312846 9391512418 5444559671 1741267439 7152441710 6488997395 9195857296 4455129133 3392720573 0836069519 4523712829 0488506643 0429839584 9901575214 7811885409 6205402149 6041706869 8090060768 0424455074 7813866273 7638347881 6018605753 7179137399 6742543823 1803824790 9560283377 0721550940 6585212256 5225339965 8674169888 6872761926 6462140145 4879401442 7652513164 1956698311 9885053662 6303764981 2370600096 9902077953 3348859393 3626889540 7849065918 4523107329 0754824734 7914588491 9913760583 4144278824 7922321023 0361242099 8571276839 1058169576 0430427432 2403498603 3890690088 3555197591 4564176042 0483124356 6058762345 4317227166 2489969290 3277301040 4309249649 0141024624 1917027549 0953214904 6399156480 9097339478 5400443162 6601651633 4057668419 7685338361 9374968233 5103810706 4881899856 3581743398 9214665465 2400343022 2776252650 9358004055 2151334213 1171690729 2502764435 9143242891 0572600327 1685908867 1014203695 7221068235 7836248014 6646327082 1170954826 0329798714 3446626150 5049053286 3256034281 2650401978 5743336597 0936022208 3129250436 7700926210 1453343177 9981586097 7145878712 8024869857 5541520811 2002061959 7947327499 0540360809 3812559679 5425672492 1053098238 6360799463 1046556839 4657126307 1952885941 0386925481 9711261027 7066868958 2277965367 9112479444 6551823727 3821389136 9292557393 3681133392 3767504229 0325273025 3760008288 9038435288 7906452697 4872983950 1398700306 2728004141 4750822041 1206606755 8607191363 2381364701 2103232054 2892330788 0142207526 7388803832 3957028099 5910320462 7458233382 2715221188 5439704354 0104426794 6879493642 0187193671 1619599944 8330467966 8683119127 9352118593 5081750426 9739657203 1743636567 2636816358 5403719059 4766826469 9474499821 4091864715 4833919761 1558794669 9432775932 8473611671 1508726218 2383132485 6127270069 1359295881 1735790571 5708079582 6258586662 2155714948 1458724722 3392916264 9377551065 6781838138 3816408464 9675701647 2487489020 5950927666 8941812579 6660150326 1746799538 3097777216 0022835417 4929449003 4347596463 4829889481 4080247475 5554208171 5235535319 3561876679 5826392811 7959507409 8798607403 7039089172 4134799510 2540994239 2299202982 1251875195 5294521565 4964213848 4068596964 6791312013 4790188155 4782873779 4290788058 9194290187 4439276867 5418317448 7697961755 9304964688 5900423267 1783997235 3921130403 8231533593 9815896015 9858627738 8514932966 6833869502 4796681243 0662251286 0923180212 6804750242 8916967296 9266340488 4427050062 8623678653 2309140455 6861547259 8861739921 3616956707 0671590867 9458794699 3273055116 8681467660 9449549764 6617466542 3434293932 9901934602 9471732852 7875875926 3671627571 0463897608 1340315139 7356398244 5078365210 9779488967 1341996895 1017317668 1155574191 8366662702 9612575871 9260131332 9296908891 8370743339 2621735717 2140289222 7387296388 7606380359 3849625193 6136841317 8672725373 7230863843 9684854993 9384530576 6276569041 2055193641 1540430920 0504910226 7450425971 5457262821 0370427391 5495735791 6321888081 0762210802 2005279179 2807054434 4726906791 7741294260 6500975917 6540313472 2137245395 6652706241 7871467230 3778200544 2092988052 9320243573 8139704038 1022621772 8816263142 0285409341 4831154851 9951227838 4214683806 0118845093 1646562619 4013305823 3743239615 9404304797 2549565088 2582199551 6601721947 1086052521 8985743621 1051665263 0355490725 3591048926 3912444808 6032391601 6877565940 1844388653 8221111229 5116791877 7385882608 2988492561 3537484033 9414007053
• c₂= 330982 0201240169 6876407984 4791521674 9677792676 9546804320 4352561169 0505698562 0344754501 8327695014 1959794842 8254676805 9032566142 4666189113 5651943553 4585807873 8595771686 4608782206 5961405525 5934549895 2890821818 2677346420 4121567902 1751999244 7488703939 9671394507 1971271944 4767088164 9877277044 1932843286 2980180408 2550718949 0395915115 0670521140 0963625870 0236745869 5778537854 0213678407 5701601955 5217941185 3753947958 1060762932 9788354585 6482750594 9419915186 5462593500 3223439574 1315256049 1627333896 2491556370 1098957633 2386510564 9709024037 2410579341 1619314664 9404239883 7151892710 8563241074 8886195747 4415437104 1516803797 7109175203 8868813855 1620502962 5030061675 0250984629 6025035751 7332249066 7820100255 4235213574 8239122524 8533047573 0958549555 5332770693 8210229640 6256242115 8477007812 9461763867 5238774437 0217612111 2248170309 2283919750 7520481337 9744475424 2251784927 6001126742 0989036418 7053778588 6990085324 6883702858 2349082508 8569863983 3392151837 9650681550 1269260964 6103872634 5617266822 8628449808 3369354054 4259445105 6133292054 5650387146 1559436591 3188099143 3959748481 9914651012 3341954870 7600238487 6017832160 3307030012 5094552005 3646207876 4137465122 7487958135 6372794799 8461770204 7004182795 7404971039 6867900371 9601818932 4470861574 6169370624 2877277563 2317518947 6011368698 0851220648 3700128589 7234314367 5387200419 1218361223 2194372197 7315734668 6292129000 0361685197 5392401063 2118963363 0173895875 4043787341 2030722941 2632867694 3406346134 4025865602 2837192567 5512374947 9940553095 1019195666 2444434882 3136299920 0077589639 6563983061 8818883658 7466564656 1968245460 2990805775 2620858338 4456087415 5819712863 3483921629 1917823195 4630409383 4316008617 7266284251 3668826247 9894041700 2814869648 8954173000 1284822273 9458590660 5918996109 9751710416 3139833720 0521813063 4519584685 2398049256 3340107544 2818737501 5797103138 9870904187 3848441640 1407121398 0398039498 1105625658 7555023647 5158755795 3220509311 3702071046 4896081086 7339902573 4300686585 9692421709 7439070959 2125292169 3547798600 5158120979 9570129448 6645385939 6681654787 3391088359 3231225813 5380414966 7022691860 9656671298 0409165211 8828371522 8881754829 4090618006 4108625185 1272680378 1271220146 4227014673 5451508472 7766395050 4653722283 0720159312 7139833618 8918335579 6852236771 6225570445 3536381243 7773571176 2594662096 0144800592 9353176102 1273816892 5747878563 0034666425 2065856414 4780965537 7072371727 6131397280 6398058857 4702476360 8775240052 2621558321 5622983211 8970777246 9381000179 4329917027 2233912258 6744659820 3136445440 3132880737 7664595468 6412902003 2711847347 0782803263 8892696395 3116695523 7787481869 4460063489 0571063812 3951886708 6157569661 8190717334 0036605992 4547800626 4536190993 7656154243 3135778646 6820396816 2748854571 7950754993 6498060888 5585411839 8815496673 6361036934 6892498236 2936349300 0339819875 8122515872 2306881580 4121432118 1008624386 0716640049 4381650918 3435289607 2414177763 1314848335 4368408351 8599252591 4305211180 6252758568 5473408691 8136926152 2306613925 7428046083 0073437744 5141589630 8884972709 7024060077 6646552081 4958497319 2712707403 7019303306 8290422032 9658763443 4522887022 1153639853 1744381615 4246110347 0368983081 5747117722 5727717570 9225493184 7264021059 2267074704 5039046960 4914410721 7345672909 4411120170 5714079482 0877975080 2621008132 5030694721 0090009617 1646803321 6302130387 9983011503 3021072901 6057747277 1105172635 6708916900 5704008476 4609113729 3165733402 6639348760 7860219810 5622779675 6907658105 5356921138 0436921241 5835853240 2817311146 8810673248 0996798321 5796040940 0386484408 4805310608 4840344322 7306076913 5454497390 6799162174 7963070625 7679128663 1104107479 2803620605 4715601149 1306075256 9704033607 7863220051 5988533033 2600815217 4369506490 8429159521 7673478999 6108849905 6904887002 1971136098 2034425403 9245764278 4936945085 4339050104 0953842329 6824113638 1996617244 1703269896 9659426191 9929192985 3628073158 9605822761 6665052174 6126643915 4257906508 6507353682 5576119756 5994246640 5786228811 1488579098 3953996878 1763676087 4972757505 4905687041 8872037885 1110238525 6446273424 2482704747 3129742172 9775964525 8423390730 2778951248 4083682785 2553215700 9258602789 1515266490 7996201350 6825996953 8429245690 4345015624 5875467175 9212954495 5246707523 1735968932 6920322196 5165822187 3567656227 8497330805 0960135062 1686116217 0468365549 0819084457 5927070085 0103587143 4233704443 3189509878 5110016358 9332313675 0528544911 7256956115 6627955615 6527043044 1031888356 4994366718 7592698966 8318417432 7899344778 7446337913 2482048123 6542445882 9539491455 2018783429 1320021030 4914318660 0184024500 4132696326 5226235622 2632706125 5643573510 7105251245 9238751110 9741328171 9557726043 3585762855 7846318345 3740083791 8435981534 8098034535 6760972313 9534091174 4678198053 7368957197 8898473671 5294964628 8006987971 4956917994 3887163739 1274440517 7322747305 8939894183 9559781916 1348654987 5082527728 2770920414 5278803215 0685876316 4739047118 7136523148 0620932707 1716935647 7247736676 8130383124 7939426355 0987551071 5828804743 0332721037 9603600926 0168140000 8768219191 6805413151 2690885794 7973427388 9033432162 1303584381 7919942836 0236167048 8698677806 7733508775 2975259022 8075949569 2765419349 8188073736 8406231965 7000004454 6405994373 2462199468 2840529052 6806805155 6692018704 0681963198 5972970354 1877766773 0796512807 9674485476 5538241622 5014020408 9188331413 8697330572 4215018258 0035011653 4860044404 9848883850 0826891507 8600927514 9747815564 1897489918 5812693963 4942728312 5787350719 8402690574 3332164251 4664694269 0560019614 9139491046 7333253089 9763349212 6473205083 5023245234 2064046056 8733454257 2784562604 2216604547 9974352954 1137217115 3997379134 6140024199 4364253929 9333525701 7347159020 8614592533 7217967998 3912409721 4325260404 2492906932 4038606657 8342187168 1494542069 9982940595 4267013872 7910169925 0258948538 7257115008 3469147870 2644837901 2867385591 8182655607 2582779712 0802067670 8180244183 6455469137 4106703100 4661460894 6093087932 8200598364 1113791430 4072433396 0786992248 3311357598 9294558670 9846166081 6596380305 1963044202 3916951813 1193449968 7756974785 0820875620 9734939707 5687421098 1967742431 1774607290 8853767953 4078925254 6864391995 7186619431 7205078035 5394151035 5551359390 0579245705 7673321697 1824767529 9775652750 8636157542 8656814119 2571031890 6989760696 5598953350 5628838495 0230343065 9790465332 1631887019 8709275111 4126563005 2196159710 9017306021 3682734613 0903204352 7576108837 4668446723 7285877333 0527304017 1898319216 0343345107 9526338262 0508056569 5900085254 8195231609 3055534774 6555899402 4253410837 0973892463 1445859635 6920607402 8529203652 0617982911 7273845636 1293404785 2678418246 1506187448 2961984963 1071963079 9482750301 1344619675 1785658863 2623931654 0971673331 0660387077 9793384465 8854399974 2347602081 9022417315 2668401450 6861275758 4359001928

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 ≡ 56 (mod 63) 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:

realprecision = 5500 significant digits

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

Input file is:  IO\1CCC0F31.cin
Certificate file is:  IO\1CCC0F31.chg
Found values of n, F and G.
    Number to be tested has 15038 digits.
    Modulus has 4316 digits.
Modulus is 28.70104869% 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 = 6, u = 2. Right endpoint has 2090 digits.
        Done!  Time elapsed:  80281ms.
    Running CHG with h = 6, u = 2. Right endpoint has 2050 digits.
        Done!  Time elapsed:  86672ms.
    Running CHG with h = 6, u = 2. Right endpoint has 1989 digits.
        Done!  Time elapsed:  90281ms.
    Running CHG with h = 6, u = 2. Right endpoint has 1897 digits.
        Done!  Time elapsed:  96109ms.
    Running CHG with h = 6, u = 2. Right endpoint has 1760 digits.
        Done!  Time elapsed:  93985ms.
    Running CHG with h = 6, u = 2. Right endpoint has 1554 digits.
        Done!  Time elapsed:  85172ms.
    Running CHG with h = 6, u = 2. Right endpoint has 1318 digits.
        Done!  Time elapsed:  50109ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1082 digits.
        Done!  Time elapsed:  13953ms.
    Running CHG with h = 5, u = 1. Right endpoint has 725 digits.
        Done!  Time elapsed:  19266ms.
    Running CHG with h = 5, u = 1. Right endpoint has 11 digits.
        Done!  Time elapsed:  83515ms.
A certificate has been saved to the file:  IO\1CCC0F31.chg

Running David Broadhurst's verifier on the saved certificate...

Testing a PRP called "IO\1CCC0F31.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=1.509068209 E-1287 at X, ratio=3.681551371 E-1298 at Y, witness=3.
Pol[2, 1] with [h, u]=[4, 1] has ratio=8.51320480 E-85 at X, ratio=1.336525116 E-714 at Y, witness=2.
Pol[3, 1] with [h, u]=[4, 1] has ratio=3.734497202 E-359 at X, ratio=8.42808031 E-358 at Y, witness=3.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.620921835 at X, ratio=4.774383266 E-473 at Y, witness=2.
Pol[5, 1] with [h, u]=[6, 2] has ratio=0.570504232 at X, ratio=6.37134345 E-473 at Y, witness=19.
Pol[6, 1] with [h, u]=[6, 2] has ratio=1.157740796 E-206 at X, ratio=3.305211267 E-412 at Y, witness=3.
Pol[7, 1] with [h, u]=[6, 2] has ratio=1.543130723 E-139 at X, ratio=2.896674199 E-275 at Y, witness=2.
Pol[8, 1] with [h, u]=[6, 2] has ratio=2.253421094 E-92 at X, ratio=1.346074505 E-183 at Y, witness=2.
Pol[9, 1] with [h, u]=[6, 2] has ratio=2.337806268 E-62 at X, ratio=1.070961285 E-122 at Y, witness=3.
Pol[10, 1] with [h, u]=[6, 2] has ratio=1.967365861 E-42 at X, ratio=4.756468842 E-82 at Y, witness=5.

Validated in 9 sec.


Congratulations! n is prime!

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