Primality Certificate for (2632^3617-1)/2631

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

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 = 39 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₁= 418891600 2144868770 2511110115 3011625122 7702975333 5919803965 1059913086 0043084441 2119055600 9176758654 2741667567 2297261733 0103213758 1124496643 3760717425 2529731450 7441703800 0874583435 4352582812 8793807026 2633751464 9829538454 6481904816 3144634444 3319147458 4662241083 6790232410 5080903253 7125598204 7654281533 3398342225 6215493455 4047006444 7986038766 5079538844 1155483915 0095319271 7795963184 7726516170 4182636268 4542867762 0326527018 3944205190 3500329173 2326434615 3044944397 7681869118 2306944132 2866929097 9876012181 7943885544 7389749476 3696746521 6298738869 5038490943 8890333077 9358043626 4629184903 4222578369 6410005948 2848255642 2109414012 8595833909 8550801877 9399176766 3901301571 5189640486 2907082767 6360481351 1162272567 9500745004 7926343109 4038417438 5875401112 3444061413 5406395356 9193762579 9342076494 2435330523 7669138567 1022826455 7044780660 6073391701 2648015163 1776403050 0481067300 5453074744 6397932630 9286105448 4768209067 3519376029 9859760346 9870015078 8761828105 9216736518 0081368773 1339556054 5393630161 9047279638 2463563443 2442463074 9770963085 5058198959 3450557797 2993602018 2367546880 2113631953 8219308344 4096396707 3778787884 1416702922 8501180071 7526791731 0121881680 5830093012 3022966957 5160457882 1601436463 5878979694 7956609082 3741550704 5346269261 1951016693 6110739886 4742248550 9329413371 0690643624 7232561311 2590961494 3084357785 2541335898 1791485589 7790298494 4800695977 4463625566 2018137016 6421642320 4104032216 7500616667 7522039363 6024017413 0711513032 4145921411 9014606895 7951720660 7235043167 8897103467 2588315941 6176264775 4397469727 1204321903 6341171626 9263250658 0632032434 8531241103 8871698338 6572093971 6933595392 1080517010 7834224592 0563854879 1437852583 5686167260 5645550971 3389303275 0333452762 5119178202 5390362913 0961328291 7655423364 9877840158 2888295183 9617358293 6202301588 9100795115 3379370349 0561725275 5575678669 0038062794 3239613882 3051869898 4317001550 5117716302 1063345419 9190338927 4862349643 1131107999 8724873035 9573330640 2048421931 9669183290 9818139586 3038087381 9346274335 2358126648 3527974152 9681269254 5353521515 3681462187 8906772967 3751573226 4306125772 9628968774 0808269078 5997446987 3116855276 9152884011 3238557621 5216368742 0947210300 4260534708 8265891892 2952506208 6897195527 1453406724 4491164060 2587694565 8352229379 2983048532 4083416244 0080300048 9875955938 6181935430 4931423824 5757079016 5534124115 3349415725 1152768394 2096182604 3606187466 9499872344 6426116491 5591212052 9857497210 9462922075 9767858022 3234003037 4864629262 4852571966 9414544223 9435006290 2298758189 6981519993 5167077965 5503977627 0651080030 3034870745 1296888525 6565000873 6987546569 5642162280 0895487382 1210241256 6267977315 2590097240 1781655480 3036625263 3687460709 5235073289 7129159118 0552124545 3225198218 7662442306 7897411448 7043451600 1083963838 5487031301 0155817104 7593646339 7312502087 7843886266 9402546224 5336723582 4467007442 7646847843 1232927765 8382054581 4487478363 9804612380 1670561034 1784839973 1454721266 9852936679 6019741701 6516723996 3011747931 2187945795 8570616499 6341451369 8693557025 8755968311 5869661687 1479955150 6649731195 4254252738 5043708913 9701625948 4419652568 6204740195 6833628884 8792918237 1656675855 7875000613 7202086219 3671742026 4802719297 2897240437 8142723944 4133714135 6260998057 2137401993 7427779385 8501775268 8904859484 4502505836 0454337941 3566568610 9262786366 6421503796 1631032165 6811796155 7423787096 3175386744 4961528413 5939695606 6308278612 8410395913 4022536998 5908555362 2593540628 0906531275 3007864920 6321079702 7713592281 3684395409 5486757232 3403141428 2416939930 4935668124 7181168469 2662498461 4619236672 2681331273 9251869801 7877062522 4622311838 3518830304 8046504741 5173884596 9014321598 8922005789 7061142019 1714937205 7930276103 1953534073 9130243150 0470764363 8145760756 3639195657 8330235453 1925987777 8116102454 9510434043 7610244072 3638525738 9245381467 2677310584 5685684985 6981630884 0072649165 8081640821
• c₂= 2 5999696181 8347522292 9124059911 5985025653 8162255745 7369882136 2739182958 3109451751 8381775561 5124342711 1449418540 2212666403 8146105230 9792585104 0931275250 3293755917 6386006253 2017822297 4283734863 7574062721 2512541976 5620251781 6076621619 0444905999 8464273346 1278446966 6794438872 1705273134 3846902075 5115596020 9180668564 0246426635 7203965168 1810272065 8163362419 1970290084 4762924951 6228844610 1966158145 1945508673 0231312218 7693135865 6282541498 1577252489 8131003719 6026999123 4523975066 7389071146 8757508624 8043320038 4551263427 1162286066 3044317600 3807959392 0741507369 5888538513 1229414707 5067293303 9257811242 2906027934 4953542330 2173582599 4492108529 9834902035 4428816939 8330629782 9864474898 1473604613 2797011367 7159523759 1345812846 3353986815 3668325019 0809930114 5663880852 4898617392 0659941401 1078021249 0338311131 5161052688 6153392098 8918051911 5912429502 5354280750 2978582299 5680940874 9124591924 8599144354 6212299733 3254764905 4685394244 1513254576 4550273681 4928183884 5394253127 4192601955 6344944217 9687855660 6519174717 8831290816 1802054091 3187177900 2866532584 4056441012 4462322493 7495143544 3505206892 9208216062 0097092158 4021864391 7582116806 5320581211 7952474573 6995371852 3650148346 9078136291 9276755535 0212085565 1535174904 7857609031 8127673052 7967803697 7137407945 7598181338 8116070730 5970506441 2415675823 5373441462 9059905545 4435794737 2750303578 5809894887 0068063033 1553164596 7098224290 2263647578 0436324341 9571912602 1962561799 6442104774 4575960864 2193961655 1108200403 6023667528 7877827275 4371511228 3315995129 3757095811 3550800635 4614482178 0868402466 9080401408 5323454773 6246918885 1680205513 1608347745 7647366796 9021305111 5186955516 3503512247 2764107611 1200009760 3632161970 0212060033 4796495728 7272334494 0540727268 5519285960 0570080323 6306352518 5480435493 3316408356 1518907765 5801406447 3806997220 2980728273 9549677076 7809371345 9431354597 2443394575 8716758182 6469045364 2636649588 7798612737 1369466555 6258838975 8983429351 2389623827 6270950012 6376180610 4091438148 8243025835 0752857128 3923013466 8346571347 2832336139 1977057760 8685679453 6784242316 1520968473 7498528125 1515069087 6678501064 4373416481 6150798280 2674659703 1594468129 2962962113 8831595134 0097691860 7306692429 6652359253 7115665832 1270744318 1538198375 5288614635 5433282207 4608040865 2600102108 4672287782 2042971249 1877619867 6391322337 9957485151 8902380763 4255460801 7128469458 6990688348 7419492737 6517273815 9929252120 9309091793 9509762686 7789055702 9917928152 6281147291 1748034626 6788112507 4309200433 0593625461 6760511755 7245403164 2864400155 7965005117 5117565387 4142519512 0179155440 2449140225 2009926801 6390026468 6843801399 4858843174 4592204298 6837988475 0603591880 0428368068 8229697986 7799928205 4218852836 9869181603 9916715508 9244570170 8835576076 9169516144 1729574382 4713803627 0488795450 6771492696 3282990369 0865259605 6200333352 8110739718 6997639205 0578751916 4018459193 4265009009 3626306162 4589275851 0375152159 8437018415 8922898419 3897590213 6140018138 8872283674 8369301247 6991029121 8668871027 4457839496 0951101640 5576986617 5871560101 6246676804 9276746545 3935432945 6905312523 0211828915 9962663500 7196507675 8995340974 6256285824 2305497240 6805103777 7980185901 6728249504 4197659467 7209055388 3555483357 3403043709 9187899238 0678752281 2158373178 1054742163 4645581093 4244425203 6496259040 9450881739 0236541508 8560320645 1715972187 5706922182 7824363184 4561240744 4667647929 9558070049 1971975249 7494212057 8672410821 0118670263 7874288717 3836785584 4863874811 6104752421 8530128024 2656023402 0728539448 7175869625 0534613045 9846324082 6903062131 3262145225 0222908638 3514692704 4541444717 2094983649 3819971519 5380464500 2419050011 4200281617 2706745480 1311752249 4222289176 0063169860 4005553147 7453554734 1523221693 6724467195 1626622811 4954398635 4773809737 4166035519 5137059255 2182294543 2958726883 0463756031 7815434320 5137117440 1017615164 8044296611 7172450715 2499065235 4217166667 8510579055 4557442421 1993628608 5953828887 5993751130 3807417799 6611386970 6360401661 8153286350 6403525076 2889138535 5754886980 0304729836 1146794712 4564070052 1131124531 8454384890 7726136306 2200585068 8133392754 3789922191 4012318978 2274605523 7523065153 4170939024 5768040856 0199648204 8530696400 1302768143 6845121274 2290558109 6260510850 9710076374 6812442227 2463407107 8478714829 7606236395 2882754052 7981004103 2362755377 5314206706 1724846496 1396198636 5643633522 2407591422 7626126782 6244584362 7852583887 3238410973 7714667490 2361342818 9709732335 3941257005 7382301386 9136501308 4253843982 4073300931 0127033140 2907663098 5648748930 9689589469 3829860538 3407739453 6166489853 3083248422 4193875664 2611576149 7309142677 9213330173 8776837338 4879660293 5109377871 2241084733 4607116350 8526531009 8187772175 3070992502 4911218372 0632847945 7871863399 8182635683 6239892714 3602519527 7396446874 3073024465 3016557374 5335717558 1918835052 5669480852 4768231393 5173800322 9229829498 0272028690 9572458725 9717864685 5487202601 5664239223 3140439032 9423237109 7296008783 3455205373 8464140493 2307532230 1784675986 2502072802 3255863688 4477165217 5152897305 7274221410 5208695156 2194779251 2072454649 1375025387 0831562126 2156378807 2813136699 1803801845 9967287447 8323773794 9893584318 7160717740 4318582096 3024593368 5530609179

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

                 GP/PARI CALCULATOR Version 2.4.2 (development)
               amd64 running linux (x86-64 kernel) 64-bit version
          compiled: Dec  9 2008, gcc-4.1.2 20071124 (Red Hat 4.1.2-42)
                 (readline v5.1 enabled, extended help enabled)

                     Copyright (C) 2000-2006 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and 
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 400000000, primelimit = 20000000

Testing a PRP called "dls2632".

Pol[1, 1] with [h, u]=[4, 1] has ratio=3.715280655192518365 E-617 at X, ratio=6.787739470112804259 E-850 at Y, witness=17.
Pol[2, 1] with [h, u]=[4, 1] has ratio=6.787739470112804259 E-850 at X, ratio=5.594781745581891331 E-727 at Y, witness=17.
Pol[3, 1] with [h, u]=[4, 1] has ratio=1.7860072641053985420 E-510 at X, ratio=1.7860072641053985420 E-510 at Y, witness=11.
Pol[4, 1] with [h, u]=[4, 1] has ratio=1.7860072641053985420 E-510 at X, ratio=7.834181316568072071 E-497 at Y, witness=11.
Pol[5, 1] with [h, u]=[6, 2] has ratio=1.2462162916566370035 E-524 at X, ratio=3.121502232163474070 E-1118 at Y, witness=13.

Validated in 1 sec.

Goodbye!

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