Primality Certificate for (4469^3257-1)/4468

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 35.004666% 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.457160%

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 = 19 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₁= 2701805 4011726332 7610945502 4150952650 5641011192 6720726210 2151680885 3538110831 7361080209 0738204843 7949168335 6960382775 6480732844 0257162053 4260446264 7137263215 0746196311 5825155809 3230086211 0658095774 1542413508 7477530197 5017743550 3000244092 9107953713 4357052185 1213886515 4166954378 8766915844 1977797697 4707238390 5195334448 1297673889 7323477386 5586006257 7565105309 5645240094 3700485304 0249940524 6832169391 7423145194 2124800743 0842940486 3437799382 8945865921 6278469273 4074039720 6049377516 8243307534 6520752484 4977293975 1155527786 9478418165 7976514998 8628311826 3146532369 4946123693 7779267286 2412122169 2878541444 4510144488 0690961535 2072450613 0659980053 4953701868 3097285084 5669259430 9872798436 8782670749 1579941947 6270732505 2417503116 9957424832 8272046912 0811580980 9420558486 9780100389 1071947629 1515087954 7007369423 3922612441 4890731968 8821862070 0340637568 1342997146 3296288108 9206770745 8528253203 9740157939 2292074762 6022375169 8992065512 8573707044 7741103049 7922048565 4464353535 2999335312 3426472253 0453408201 9287653725 9275734014 9294821863 0763376042 4368717395 4354655276 8032177276 0804241846 5094560542 2786611009 5764722490 9337018557 4325965047 0732796163 1614176359 1315248760 0801772603 1514340736 3965803704 2071542443 1991350735 0730958699 0469033175 5799125063 3297996259 2581464136 5057075202 5198261071 4775701424 9093016686 0597827656 1629266822 0979281966 7487999911 7610582201 1751358750 6657856710 6444215278 8615534649 1283520616 7894432268 7570792608 1283406367 3263421746 6818528689 3998524886 4760561964 7631350721 8496133473 0916076204 1846607201 0210370313 2074036219 3311686350 3480750287 3345932694 0425288338 4530380791 7205808444 1460628392 9816885676 9983970043 6091277069 2174617678 1885913705 1500966026 5005303700 4455402693 1098960380 2101551875 6164525761 0392631959 5443443562 9225811048 9636230467 1017968961 6334791252 6569004422 4479640085 0781463541 4434747923 9592867757 7827333841 5165804177 1229022535 3380444352 8985642995 8116791064 7870937334 2117371739 6366603401 5708132966 6369551050 5016890691 0705725149 9498093751 3577060935 7625556840
• c₂= 182 4529751538 3465328891 5723408047 4460690945 0501406675 8252168125 2788548634 9791929504 5253427809 6403089725 1117964093 8288140646 9220074339 3533399346 7095931548 7393837562 9585230451 2778344154 5925786891 8218225605 8545362944 3892354387 8837938801 9227732352 2071147986 5201286909 8274501305 8842034305 7837052148 2127573856 2853518858 8669710096 0628272544 4819504056 0224066703 7076428266 3779303346 8297707236 5271523493 8142534188 7897706506 3595791981 2081203201 5961655297 4462596812 8383654324 5983513698 5220331789 3205964188 2824757701 5623504635 8417273541 7532412601 3214911089 3202913083 0943066106 7446502741 5251521280 2665850238 9287274801 2968490148 7713212887 9556839672 0205383749 7540400988 7808726086 3518940986 0347189188 7229755195 4912528513 7659647378 4395693669 7287766777 8597504860 3130913317 0353949399 4859260257 0273901846 6329051947 4887780418 2812789573 7469611204 8139968092 3229756787 0724274439 1582107415 9527773403 1217457876 5452608994 5588927580 9667863987 1894346306 3895018841 4171219658 9509094313 8900388151 2953042724 8527597688 8279432061 5747359531 5662758564 4935586825 9896765607 2882487528 2537220600 7285508036 6519173931 0365828800 2753977804 3743486275 4728291810 2345224559 5267223264 3227652271 5764190113 7272427882 8147833325 8164785132 5106052699 3809233146 7892377870 5477366159 5528041991 7192584016 3116695526 5519886224 6979746420 7279429325 4196879853 8829423844 4459823753 1799311767 9721452081 2915222961 1500286124 9113044896 9954276230 7097042246 1388066173 4125630918 0867723546 5832597813 3442293180 9342325187 2381726912 4821294754 9855382781 1754008278 1931856303 0962488146 0810652978 1270634226 1391489338 1086239326 8527002160 9611201194 4397238581 4353802898 8504069822 8444043371 9851739368 1260958841 1595043858 0123904479 8546526381 8569514562 1293544594 6145769433 2072171230 3662410917 1535804016 4295857891 5959476009 4691476411 3872122450 3134903839 1680077615 9445546426 2561146160 4103359022 7529642681 7835200262 1027193907 5839135776 9408175323 7513322040 8515426114 1779275272 8612427931 8641895869 8379012644 9845669478 3006734192 3930300296 6842273129 3575272125 6137240954 5510999997 6695515409 3161751070 0871947343 1820739910 1428654633 4477134408 8220248633 3598154787 3082925917 4228775395 3776665567 9944213546 9241023103 8785192567 5173323536 9114609766 1875234794 4780688943 9956292785 7079508180 6191153111 8113990624 2601951651 6986917116 8130264783 9137719932 8107306413 4016733623 4636266113 5996228983 7762675623 9321087173 8869565310 7146592144 7451754367 5489753272 8638051046 9453377454 7905683236 6187448898 7601770448 0494472137 1610213108 3476276993 6535212228 7338842908 2855247150 7437506342 2227115347 8959786980 1657415642 1305779462 1552016184 3468003407 8533835103 9780704151 1764232282 6675193209 4970409284 1326204090 2863283993 1709089132 1344312855 8164761202 4540565281 1434393406 2646497473 6882572998 8282967919 8002350850 8375451614 3301227397 9765449289 7704040548 7272309838 4600287273 3825822442 2012350053 3134877892 2686381870 4620083518 5780665538 2731516670 4466897005 5366454210 2082363891 2611198166 9229247616 9124891859 1511974096 6177130827 5802672315 4615336759 4679645662 5084491196 5998706494 0639186052 3472533260 7384377388 0177063627 7679442642 5663121881 2483822808 2317480654 7303345048 7446710845 2724169056 8733831800 7600389678 6213753853 9922736955 2241031818 1402903781 2543268288 4880627718 9732649983 6917245602 2232026227 7972789353 3612238242 2678493602 4117666884 8081648778 2729703292 0223937935 2113992583 5141606301 4513524750 7919990312 4435491670 7508959528 7562209970 2574318541 0664341432 3876642471 5049269466 5978242696 2065481014 4497920526 1406506654 5669957051 1270264996 4860625023 2939147701 7400716733 5490093310 0201003818 4822899032 6002839276 1629479092 5791087834 1541245584 8107652063 2269039590 5857087963 1912642330 2869249931 3670833983 5362891942 3169840087 0935255486 1668742996 7667607706 3987867444 0800466434 1676715521 4481039228 0317906547 0966364074 4673473088 2915366351 1415434071 9281978620 4079157993 5212723336 1267374344 6601241355 7921674452 4121056861 0369748546 2044720744 2230510583 6622780182 7281311648 2561806201 7061951798 0793102363 7728119130 5149945875 2576303890 6610812692 2608451879 7309931840 0455153682 2358260800

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