Primality Certificate for (13735^3433-1)/13734

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

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 = 77 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₁= 20 6171023134 4412827361 9950054611 2475622889 6017857271 4056759176 8327545717 0102537185 9241029827 7845299203 9736854605 9971684239 3269604892 4885119427 2377960606 6731406055 6470007545 6797730539 8047726143 2819693391 0806243583 2060365725 8825261613 1327367630 4683905484 7821587014 5656970577 7695495185 3061450626 8260678408 8385065168 4569663219 9853205584 1353544071 3730913769 7644439052 4060668192 8711696195 4749417634 2889006310 4465519786 6610103592 8806442367 0524649495 5851784811 5746972411 6252210549 3218367767 1506089618 6073570882 6741443758 4914463810 1888183892 1438757019 3598401755 7671708649 6753220765 6275707750 2830045624 0048728110 5709555731 7462106151 9414559462 7850902537 6046236333 6291098823 7768364827 3541535356 6815440444 1178569512 4265317195 1481662546 5573927937 9213012679 8137785410 3427711523 7849794893 6993249735 8696071160 4196713440 2836568360 5458114060 9887608591 5045551930 9327801085 8807637064 3093752269 5368925294 7511536589 6642338873 1823007661 4991741861 9529718212 6517415854 3990439898 6178903676 0782938836 8853879968 7763650079 8990992221 5830076063 4925353790 3632378183 4964216518 8385421118 5195769843 1379021416 2595438219 6085723604 9884137609 9309326007 7141401629 0530115314 2350706744 1627403013 1583787690 5680383100 1427761291 0543354639 8019114064 1857905822 7207960594 7349556769 4148028509 7476551088 4938865111 1256013744 8685603021 4541363356 9823654071 3684761941 0975197088 5270295914 6179033715 0223665969 1407676804 8453362791 1399750126 8180622833 9051140527 1368843412 5585586074 8122011221 1692969435 4542176567 8547480648 4024086190 1935247198 9773111165 6446070665 0806176102 2857402517 2651807139 7187167552 3445761114 0615499266 3042559858 0434136181 2579673767 1254710672 9420719662 6076009413 9138046899 7612655249 6103084861 0658341742 1392347825 1012726788 4454808258 6415690073 3750957295 0165677294 2684042042 2566031823 8529351396 7573803914 3371062421 9057725468 0564794351 3455878166 3588340041 7542239037 7366429204 9964418220 3682418288 8432334620 3272159110 9032936099 5371472851 0718873176 5642073818 9421138000 4469501877 1214181818 4182586766 0759311175 0176842958 9642493718 8815557967 6894594353 9349412920 5315877481 0046894171 9753598570 3948708683 4739325197 1218250965 4497264152 7294877897 0470273681 6634221099 5523910801 8117347182 2778178321 7513791238 2188549390 8744677639 4423015935 1198265157 0585428164 6441148820 2710987555 4768744265 4151202754 7826433789 9216964286 5338950068 9289998822 0980897879 9113171871 3511674494 4847275663 0185966255 2630507845 1258184467 3024718889 7419913517 1507061733 0984006612 7965701063 8458535116 3964049047 2800130314 7636847145 9896184328 8098171387 8212588018 0459457668 2616797126 8516046861 2835518019 7889659474 1480222664 7422530018 8779275769 2954962048 6512561954 1004127130 8885031198 4868690242 6185396793 0862853072 3122756076 1188126858 6206564677 8515622604 3382083515 1343812349 0535299558 4950458768 5544603494 0254030621 1457416200 8280397864 0403286525 6455530876 3515423806 0098496563 9448406413 7242947488 8281891518 3620592255 2227765952 4346781973 5203925263 2557764226 5184239074 0396912393 6327671299 6724009663 7439174912 9966305515 4019056164 6715130856 4859290462 3659936326 0971630700 4072134497 0832834114 6580493989 8092264389 6533587151 8875781152 9722955176 3402366096 7965091626 5103313862 0453622590 1236793220 5739094220 5051566111 0626630578 1659030107 9817239417 9104901203 3443380404 4722935894 4541896559 5481973699 6662429913 7908943344 3196235803 8918297806 5824464710 5313886660 9050039354 2057720677 8768722691 7911729650 3940960985 9564044116 8286700621 1832912079 9035471807 5119503694 4667575775 2055592723 3269242962 2422696873 8417703771 7888584431 5076980849 9525396605 7413391961 5911558735 2129081478 8146615131 8367414077 0962766797 1345059663 4897296215 7424614712 6470160954 0591411713 2619570718 1172807664 7662549755 0985927840 1119316701 9966087184 0525141020 6646080389 4964226831 0538491438 1094961242 3604470651 4593732229 7143605619 9449046813 0919003988 5774438314 0786815427 8769337432 3532874169 2605554664 1887044561 4142362419 3015800322 2007965219 3411568668 9738855430 6195568303 6061332316 9980382639 6430857966 3714867719 1474073454 1923297844 0032484105 5485584402 4354832606 2171032970 1657511030 8791535678 0928400409 4140010971 4135740031 7200325748 7052736745 5490310547 5458031277 9272679659 1490918337 9652731125 5561030930 5032275723 8790672668 6394517246 0623801030 7996857861 2939203642 8542842231 9298725875 8526908336 1132906183 5550576041
• c₂= 157013900 8505401500 2784756945 0665794131 6795523238 2532234773 2920205120 5585145458 9550754343 6385159253 0485387331 1248846604 0489888222 1369006604 4653824130 3346325754 7222819531 7026060817 3627167111 2456810185 5616070996 7538038752 0185707765 3052297390 2605538296 2854567794 0832992466 1811693216 4110219387 5374550382 5537539251 2060099677 7007549179 3706321437 0042410025 9075695547 7544809796 0060916457 4591667380 5097489764 7894878487 0834500816 1608737398 1981179400 6321903410 7413562930 6540763091 7396997710 9691650756 8782223656 3371584829 0419329385 2938769399 2403205617 7561423427 0875914211 3283545418 3886700396 0046774648 3379902992 7653854727 7415648511 5943977466 1775653715 2297052266 7599407129 7916244033 5928188357 6282645154 8035487122 7532453027 9647088967 0587700456 9115515537 3539399225 1683574605 7142240276 4558334162 5024729922 7706437013 4432035772 0702744167 4884323918 1993157208 4590099250 9860770121 2476755561 8488844387 4049973806 6218471407 5019848610 9319069169 0196260578 4038184450 4671514706 7899761245 6450442257 3026831408 6839913610 6265197472 0286582708 2691513709 0780382693 5347409418 2383437400 0551063499 5657138485 3869641675 7747160099 7324052661 4944949178 6111166230 5635240560 9184319702 7331646448 1491610566 1080761581 3888209934 2263814212 6010802880 8232447024 6892398887 3981612560 4471939285 8481511298 0381859698 8949319482 1408278900 2782265322 4073040976 9921038292 9185396230 0068666195 1674658992 8929663786 4383240803 5760129594 6603839377 4324797329 8825015647 0302919422 9838976425 1572328239 5556207934 7911028646 2296143973 9619203551 4380831945 8337474596 0608250654 3172391933 6495213631 3992550691 9488313945 6576796920 7365411785 1802850549 7829983179 4306683763 3814174396 5828617995 6310749232 2574241530 4227448887 7075661046 2939335977 8441118757 6442181346 3129992688 9396386291 9626437024 3313134106 3604772068 7314770957 2959246326 7899914247 1975661464 0656187996 2140763910 3851121096 1452201431 6799225932 0326734724 2642025379 9003976941 6157715011 9623994569 5349764629 2567278794 6791648217 9903368174 6184425135 3552619513 6694032580 1404614174 5727073506 9732304466 2688957066 3261561935 1459444345 6283166881 2301131386 3371602181 9822863464 7809814175 2025486701 7005843785 0191974432 3733707644 2454104481 0258930751 2051212294 5743563871 1538779882 3624800680 3840843103 3770013197 9409342560 8716268919 9638727942 6939325621 5776411494 0371844657 8374318225 2320492872 6584271647 9968996633 7666719911 9179378659 0507624101 9684235967 2410858000 9471701387 6270873112 9491545327 0608373779 2910796977 9001931979 0905147399 2779924592 5292305572 7322035046 0935799051 6450876553 1371650640 1518231609 7770388127 0176485127 1435930936 3876633400 7524171170 6841264744 4052381028 4457447702 5009539414 3050338011 8108657426 7106058594 8119974729 3224896173 4480833086 7990304753 1238291573 4425056384 0258442037 9826779391 0065957272 1147526125 0742308329 6785720679 7153808301 8037071925 6895173145 1478194337 2441244476 4315465007 7454030544 5802529187 1445134931 0457233697 6470792472 0432503673 6893711487 1381381701 1350165534 6642566261 8099600489 6287963037 3046136477 6692682163 1135648778 6849995845 4323602432 2402361440 2299258185 4558988943 8079410903 1117300099 8454776580 1190004160 4139771629 9893969772 4946400140 2800364607 4413609328 1726039181 0203596453 7797139383 8800029715 9406880149 3260519979 5300934326 4132278793 6257079939 2744770963 8938758245 5906039161 9355054596 0123797372 8310318431 1930909039 4060549213 3021466887 0905654716 4689767594 0763519740 6006760846 4781246133 2548575313 0964308050 2796756301 1209939123 3210092648 5574114519 5591903866 5987961317 1713209669 7557349404 6088969447 1676286017 0691685830 5881265647 5951612848 6259280364 4297618017 8763155132 0550983218 0963581723 2425331830 0993531866 3350697220 0772553957 3401343607 7303160984 0109796032 6970624558 2150467323 4141109360 7634096458 0847922884 2892375342 2239331830 0285712031 1114960902 2236684078 2324209610 1500475578 3925676165 6907622748 8783564867 4712120278 7043062302 9230250934 6531459989 9882677345 2075444889 3800948916 8522828458 2059657011 7970840912 8028696372 5036349470 2578988211 3397876932 3295302810 2039148045 0484284161 5476058419 6829765026 8831573680 0818046849 2427536583 2059272744 4755381210 3989268079 6892830818 1093089326 5795849686 0071784222 8300735357 9754990011 5165162422 9696294366 9084135400 8765407902 7662587559 0953527992 9022207492 9693491313 6548352329 1944511508 9938487687 8638643807 8342966345 0352421364 7488340790 1166435821 7723659103 5296955801 0159534072 5715197894 6494885525 9076182195 3821200716 9930234664 1943806905 4148847761 0971881285 3501809199 7434181007 0169667273 1731889364 9600256641 7968956729 0232798833 0198086957 4175662267 3370283040 6363656077 7415549961 7596022355 4596685712 7184829158 5744506252 5076650080 9058243701 9617766817 4047379893 6772384113 7416058085 0938943380 0803691755 9273087236 6733141543 3958227464 2717729878 6508934920 0686959400 7161826895 1915955401 2857871957 4729580533 7073639290 8440939387 9141654661 4448274257 0615281691 3224717097 3622100367 3755623257 9430493517 7696122738 4080657251 9714287366 9137825396 6136229668 1049444944 4917235427 9569968712 5463399227 8160085071 4634300091 8312813760 2599769273 2647926170 5187534048 5317749439 0722051447 7809523059 1707841444 7056409394 3970152770 4185292398 1608124119 4743741723 5956630610 4746593855 5421844448 7287903780 2701854380 0442743555 2084846717 4187638410 7891455854 5204938871 0311001748 8904318572 5136607720 1906331481 1011633792 4860264669 4917824885 7731573278 6581902797 0793673664 9368843091 3137437404 5927788428 2977473349 1527852432 0623834165 3798202180 7808370242 7145153843 3273681497 4806573184 1953265925 4662325197 6544030172 9330870131 3320878122 5280503013 2461465893 0173702355 5135463037 2811225340 6434366247 1006730999 8860383513 0367809984 0511793650 2177622495 5161128004 4658783745 5184159352 6749756568 3538139284 8821900329 7216780074 8285109990 2875864984 9854409147 4690565925 6316284239 5008137987 4656685050 3013738671 7833536157 2311223343 7594537517 0377319169 2148017736 5526462043 2428017662 8418840680 6604164998 3446727450 1434574012 3353863049 2645774157 0814964575 1746323857 4641469973 1064706128 4906340786 0952054615 6410407753 9332435402 4902044107 2744146693 3877530734 7973607489 8583531136 9757195375 3419947530 1222225104 4760878555 9862861883

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 ≡ 37 (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:

realprecision = 5009 significant digits (5000 digits displayed)

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

Input file is:  IO\35A70D69.cin
Certificate file is:  IO\35A70D69.chg
Found values of n, F and G.
    Number to be tested has 14202 digits.
    Modulus has 4162 digits.
Modulus is 29.30362529% 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 1718 digits.
        Done!  Time elapsed:  258718ms.
    Running CHG with h = 6, u = 2. Right endpoint has 1500 digits.
        Done!  Time elapsed:  263188ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1182 digits.
        Done!  Time elapsed:  14484ms.
    Running CHG with h = 5, u = 1. Right endpoint has 977 digits.
        Done!  Time elapsed:  15157ms.
    Running CHG with h = 5, u = 1. Right endpoint has 566 digits.
        Done!  Time elapsed:  118671ms.
A certificate has been saved to the file:  IO\35A70D69.chg

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

Testing a PRP called "IO\35A70D69.cin".

Pol[1, 1] with [h, u]=[4, 1] has ratio=4.413418078 E-250 at X, ratio=1.237490834 E-815 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=2.434797276 E-412 at X, ratio=1.265958758 E-411 at Y, witness=3.
Pol[3, 1] with [h, u]=[4, 1] has ratio=4.056777760 E-206 at X, ratio=6.38579335 E-206 at Y, witness=3.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.2998537915 at X, ratio=3.905988040 E-635 at Y, witness=7.
Pol[5, 1] with [h, u]=[6, 2] has ratio=7.77719552 E-219 at X, ratio=7.80611958 E-437 at Y, witness=2.

Validated in 3 sec.


Congratulations! n is prime!

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