Primality Certificate for (3429^7549-1)/3428

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 33.453689% 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.336446%

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 two 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₁= 112159 2521401140 4818849764 0851934487 0562281186 9188462351 1563499994 3943868490 4610638921 3659252138 1678588625 1162841127 7988652916 7727671461 7030055829 4685198336 4042051183 4598012790 6350976702 1371317908 6767325419 3286593599 4334311557 0468889962 2616428078 7867617296 9632583732 2165578609 7595545866 7932174980 9522734482 0872356597 7269935467 6914648161 0587075129 2531206848 2250247864 7758625803 4958863977 0184010772 1721987534 8647856265 0248700701 1232683243 4538910390 4733456875 7011739347 6184639877 4806982079 9330136445 3809515236 6180604686 4523381889 1830734201 6397745071 2995288348 2635876711 1090823235 3948975634 6399156143 6153881228 5178332843 1433049134 1655755879 6820991527 0991584523 8455770346 7936775216 7857166637 4738918470 2416538168 5286097025 6918548896 9740208534 4836045720 8666425016 6364849895 5580510875 5621651053 1479946761 7108492483 5923497822 4256191848 1348727856 4018501959 1503980376 9144480285 2785992692 6202885426 8215472342 6211503160 9181177743 3515135999 6537182671 3858828870 0635755773 4561405311 1694667076 3313524867 1174092486 6352848380 3570459459 2247901282 7914276111 9643510117 2147315284 3598756831 4533830953 0227365131 2829763191 2629892114 1299089880 8614035858 5536925212 2909737915 2901171228 8163849253 6280667707 1558832054 3584982384 4490552612 8110002615 9451945162 1541110276 6512847400 1266043723 8022637061 3435490807 0656926914 8549731195 0303150961 1645604553 0193073732 9436128395 6670817304 3036456606 9064531194 8827651680 4975887077 2457888018 2064215619 7674906456 3512727726 8235318596 0193523039 1367930268 1594017260 8629407375 8473065705 6694616535 4953077304 3030031243 7755001070 2184067161 3905593679 1923337074 4792089639 9731663720 8474149193 9447109823 3205764240 4847029879 5062958728 7432298865 4216920257 9151718084 9282461928 6404892264 9104383517 2040925510 2951314044 0433518018 7394962720 5330926005 3131079750 5521348178 1808106399 2145394490 6093031259 5855841327 4846075205 9613408476 9739812023 4626827074 9093023845 0815685299 5448990642 1932812613 7258174990 9246059071 2778220958 4128195644 9595022984 7293136694 4080987539 1295769947 5273165058 8566129289 7335441053 2324237242 4616412382 7486938977 1757029214 2725246022 8609086548 5450273698 2391113544 0268145195 0222401754 5258958320 2464384166 9404739439 9023013274 7545390559 3075142373 3428071119 9968992222 8200798042 4371962578 9653184519 8959622640 4219303122 0485299468 5532387867 9005085813 2677366721 4718841137 2231907293 7719721292 8968371450 9657438785 5328531218 7292278798 7751161003 1370768098 3214492717 5066987614 3336898990 0315057916 9055172377 4287915823 7486825158 7801977057 5094554293 4277147979 7189868384 4953615317 4286689066 1192028385 6071495211 1560059822 9856626381 6653912420 1823413934 8326877948 5315889648 4498754235 0317310901 0534253734 7632798268 0205157907 5655672976 4701401044 3129114279 7216936392 0205304231 4939043391 2508860121 1220818998 3899518336 4606971585 9972138450 7907809231 2959588231 7816847749 0094396314 4888991206 6353640463 1441597120 0177385996 0292402058 5036639400 4068318682 3173355477 1299221349 5519000055 7720144239 6470953825 3664292441 2549181952 0047571576 9023057267 4853889793 6452473428 4851523503 4991364174 9161833937 3868198095 8046427883 5410460660 8992113960 5761331448 0299635744 9557016985 8532604537 3220534187 9046875779 8673121154 3509136638 4842978201 7862315651 3826272751 5258169223 9415320161 0632646424 4672373607 8321547029 1353177095 8465009777 4961012911 7979636896 9041917013 7102628709 9853068036 8201569052 4827933128 6332036964 8560403284 2792377075 3315139970 5518984345 5328129751 4679957885 5346291605 8865450739 5674495584 0311520939 4816630908 4844427333 2609253594 6765223856 9315997666 3405993491 9067057303 3379271059 7280003709 0113203173 8535019855 4157703303 2651844212 3257438417 0102021006 0983891618 2521455311 7148046799 7128994143 3107730554 9381742833 8886651738 6093387186 6793521395 8924458288 3114309004 2812234151 1971561352 4674443972 2965706085 9017821062 9227663523 3897781705 6557819662 6666708127 2117191158 7961733468 0654301999 2793851786 2040167676 5342876179 5075279373 6094794824 0548746634 0519383413 6867291678 3434703046 0678416412 1862171657 7277051844 4037833324 5961739243 6370932886 0827988951 9822229232 7598568214 4270457769 3353457648 0477250375 9734604769 8976466700 1150502834 2917614384 0292436095 6626576193 7635144032 2940180013 8593464414 1280156639 5542174105 7561632323 6750154822 7771162289 5064884302 3999572926 8245839909 9801819084 5701519713 6072034302 9110047004 9712190853 4697217756 1110634491 4395995659 5987069061 5075576589 2963241828 0556995783 4864053786 7138689615 4187399147 8294935171 8700941119 2222666092 3952781341 7940388994 4439030813 5386301003 0709918566 6833584585 4380112684 1997686056 9742232856 4138030591 6781198859 5268486389 3363265215 9890780320 2279071523 8597482704 9420579241 2599894125 9079043621 4652846697 8036744826 6486448196 2752702885 2876549357 3340853322 7968633613 5863078214 6033092923 6018491823 7236843173 6064541362 8824112693 2685597323 6525903539 2706165012 3319176237 9309543066 9012448761 5780636340 5579205031 0208498161 7901613142 5357134292 7807326003 8388335914 8393725188 0176917499 2628957780 3843033781 5531414815 7241139502 1435826538 1112702215 2809483369 1133511718 0052548655 5669450694 8666223315 8612827613 7510029532 2823884992 5224682075 2396459073 1158702914 2796841113 7949205673 5360506634 7964378022 6377212483 3153315950 6519930663 9230520162 5688318963 4747769188 5543587561 3009845644 1923374682 4839271615 2293303670 0900336550 1638748791 6600022122 1594304085 2622227315 7049183988 7682985835 4216918120 6978223964 5851256553 4158291636 8148979899 2769863779 4045899926 7394684760 5770250089 8247433996 2534856744 9056494837 0048934297 0229567530 7635492705 6559066665 1534202685 0619706935 1467837479 2117479224 4634992604 3184249786 7508965754 8696147979 4698075336 3758965635 6537403635 4484224575 1562177936 1056639593 8899857328 9316546729 7121444514 3062526441 0126177745 1588545209 1371566116 7295662083 7609377573 0305870733 5952852320 8906925898 6229623744 0054569583 9117595030 5300578259 7230599117 0621122491 6059650526 5012847218 7414956588 7743790525 7334009410 1589882702 2426090395 3912135253 9893452078 4974396334 0876889223 2815946042 3825457399 0120280595 9920379043 8503108339 0838902757 5602199396 5616684288 6868699638 7406865945 4338303354 4825877592 4552358582 6656467849 9346836551 9558040217 0474092935 2479750162 4446222962 6262862438 6717088054 1285307483 5908631234 0397075819 2732431656 1466566735 0190160409 9284884470 7840773601 1535986386 9450815225 1885181405 6840799882 1208541040 7919908873 4513776043 0263541942 7223562068 9757143742 6911561464 3027366829 5792229085 6249403207 3248937744 5295860872 7850881607 7027099028 1945341722 4249929812 4654817711 9032842203 3233893960 8234848041 6148803432 9865226191 8253213490 9085459107 7293968085 7518537116 1228854937 4608180795 0846338645 9873157671 5515021082 2258725192 9194473154 7504163330 7258306029 6011563264 2751272090 7037148822 7012614827 9785946802 1599869471 7498806470 2590429705 3456923495 6920435658 8297549312 1522786691 5541996213 7494056053 5151197842 9550075526 8230082432 7856945912 8397431750 0520552305 4179431872 0855169853 3854540975 6936778620 2861300740 8921112819 8379232145 4065358251 1237951532 0393602394 6152587482 4071274161 8105287099 9877961867 4623516549 4773913258 7996533480 5301662953 2444481627 3088169903 3336587698 9244202605 8628899703 9084176865 8747918855 8267307130 4184150674 9626199915 5323502841 6670899391 3965509855 5456047101 9064884768 5327619725 6233716984 3709358009 2741283897 0378936621 1339762110 1416659340 1329698868 4893763988 8093492507 3734720048 3309003324 6090119365 7010375418 0690132152 2730032151 8396527316 3718257927 6537871411 7974011444 2312200553 7608427793 5759030065 1606843771 6435603370 0758641702 0108883783 9153684651 5207067625 2832906593 8804939745 3801692674 9297147449 5194987370 0252420899 3693582322 7010654414 2713859212 2822705930 7731055653 5025631427 7102938338 4571774410 5976514315 9181074072 3258073888 4691219960 8674422910 9911218713 0004749325 9139425856 6759901047 9425522345 0586582412 0956904081 6264272635 8696183483 5382768836 6315497603 9095426497 2967408410 2199333676 2847969859 3147052871 4492364055 3407261930 2275767017 0309369620 4364680421 9451502193 0189750421 4746507405 4831380398 9821381552 8624094744 6857270908 3551774203 9697783371 1051994590 9748443509 9605558867 3319841145 1648474518 5436090471 6347468018 5531202731 4522152492 4016620318 6264743897 0387343089 7263981006 4351063491 4665588077 7992234163 4234685397 0939263404 7302663623 6847288970 1930041680 4543798413 0546515596 8725156282 9553418045 9569076987 4293954755 4550752979 2313004714 8761904854 3768852774 2056424610 8990160357 9022517921 0229401920 4647591571 2108085872 1152011625 5615647652 8990654657 8970591965 0544086704 4415735430 4817180188 1425194610 9738712783 7464127464 6228976316 0146534887 1193245123 4328678329 9783267780 7283983866 3959741853 7884126986 3130770183 9140780239 3128297032 8714967288 5218360396 8150807846 1364846742 4114612669 1196923357 2769072661 9872326687 8316474707 3851552557 1579173036 4550108835 9537505112 0964322906 9800091661 0413596964 4647040803 7508966513 9043493510 7581003681 3407578836 6467240337 7436812520 6409650178 1729526980 5016360947 6323029041 6157418724 7246683995 8960981487 0819751380 6427927511 0570850361 6318107428 7033934877 1581478091 5339704694 7350838495 7736082317 4808459073 5188753574 4367236852 5300007913 5194276388 7649255645 6822724847 3883814935 7154586978 3887691988 1268055724 8527349992 5925910473 5310733131 1040359320 3601652618 0037948568 6525343247
• c₂= 660 8360331331 5167817976 4446798545 5620155522 4892339059 7168414825 3113723626 3841130326 4234640680 5324853776 7947681902 8573653112 9164782249 5679550143 7564954994 4885174036 8757783773 6965272017 8465458440 9987934621 5147791817 0768655775 7926227935 8724411007 4077268616 8459740163 9037696887 5648304082 0913156337 8830356628 5963557215 4696151096 4855514565 8907693972 2395920003 4445051207 8943260906 9967253875 5478276914 4735230178 9716233471 2178508247 3246699655 1573203550 2224936194 1244016310 4135377420 1080450959 9314022746 8762256513 5412807021 7933140997 6080218652 1837098104 2774417877 5562607611 6602298236 2356906331 8124056088 7898382839 9403815664 4189353676 0332005933 3052422510 1276944271 8102592663 4138371430 1730419464 8581041187 2517139398 7065821548 3202366581 3868547923 0840334994 3929127023 0325586223 9450757137 9739196886 5393616086 1895037159 7809792009 7630373740 4671575723 6697846637 0838526713 8641470981 2293426331 2289728365 8445060405 7826417646 9875817179 1403096227 1049829240 8672638574 9261650389 6784517510 7317020441 0309487430 0555857650 2608616708 8538198673 6460441483 2381944801 4505845076 8244960274 1997728837 4862495269 9744269218 3886084279 1577858699 9921774431 6991448723 4967986207 9510748544 7071980100 8751681150 5820996351 9979864976 6204996012 0110975950 8800566249 5177545008 1772352767 0281503496 8406451999 0854823137 9073973669 3227325240 5417930872 8963610733 8934814787 9981135261 4051640781 9294723969 1500062340 9248467269 6781786266 3982282054 1128547468 5338933103 5752225107 8538045751 3199193744 4963695972 1797406309 5932194971 7284299121 1623006454 4458186104 3778212904 9345275776 6387450935 9418431305 5046270146 4797090470 6498689203 8682130187 7266667910 7087836416 4914536426 3956016567 6567559831 5627232332 8280776651 2664574524 0426977236 9865169112 1344117262 7587794136 6988403162 5923716898 1189324581 7671666000 8372934532 9698037236 6275891852 6229609450 0000017906 6867895588 3957727903 0999874925 4845340294 9701968329 8805749824 1154792171 5380124267 0515603561 3750234601 6010406257 6456466460 6634632309 5610374504 0558799376 7448712250 0309610632 3922420297 7221565914 1757770769 7316985599 7874803102 2861314684 1374986755 9499383560 9298123675 9325965628 5943218871 4574193745 0559627088 2682173420 4609629723 5299724380 9603962024 8413065350 0299042309 0736159048 0776914666 7803493687 7787290328 4163937164 6744557001 7801405222 3856934492 5096550891 2288487793 5989679405 6643082790 0393190519 5449609039 9334263982 7694661164 1013329875 8692821717 7533522545 6947887040 4188509810 0367138902 3761432964 1939384089 6539303851 6589787662 8732548394 3510403084 4296428491 9104096611 1947034295 3557803090 1996467232 4394490529 8038590238 9822178060 4022986401 2434141507 9136481175 4737499873 0175801461 4826159867 9601728622 4054265338 2119353899 5171836534 4535582707 5368004613 7445642628 5623010470 7764191277 4311676851 6114966181 6492197570 1882976072 5943822501 5761657637 5787526664 1766581033 3892270244 9352359100 9972355426 6081390734 8370889803 6869140684 2512844655 9937770333 9317677163 5037684031 6404545556 2469409268 8499310193 7148219598 3388851503 5101169907 7817904614 7460671960 4819873176 2872366046 2931088265 7911356587 1228988632 5257639547 3692279800 1949513698 9318769127 4269739212 3505325810 0002748044 1094718138 3097908780 6933623074 6956382188 7705729150 5049935944 6058703495 2643419975 1090304457 4836477263 3169506971 5682849051 4487960473 5899092623 4688037995 2551467703 0892136594 2884835301 2485712942 7964699755 9350366035 8776415960 5874319769 1941525908 5595662512 9247233864 2401017542 2475529796 3103422580 3567616003 9907004709 7246833804 9841813321 6337173209 2856783879 8236342931 7172462386 4544032618 7941669432 1694717608 6079894712 5535742344 7416494493 0849077097 6373731478 0772202486 5979667864 7605392347 5579837942 4497013289 3341571775 1272063930 8090108995 2150046562 7639789387 6493649266 2683137501 9240325084 1221695053 4687502327 3963760695 5236223061 4046878413 1715419870 6346040747 6195697226 4295061989 5469555129 4713503610 7294316867 6869162925 7682590587 0567166235 5722082697 6378639674 7064190760 2378454638 6084021960 2045596151 7993585416 8006904271 1614299572 4466981175 0249556023 0184441867 5897464384 2703454489 5139553001 0477695033 8267451359 6264665478 3407588660 8566681501 8526434452 7887678410 7805987559 4699776314 3045697954 5960546897 0668436911 7119339767 8238499311 7427607807 0783957476 5736521878 5284242831 8543288771 7007219741 5751283879 4225480779 1088607569 7530765434 6988565982 5191599988 6555984981 4493353365 5643966736 3179857615 6395915563 8725563433 6576298379 5411288592 7960594586 7962745992 8786249805 0629158946 8346047936 1980783177 9196016527 6769930269 0775782420 1294246500 4719465401 0368148026 4888405812 7072392465 2740963543 8290953614 6330121749 4244561942 0056653491 7347437681 8741832794 9166454354 4711902791 1816427617 7066804243 5430024698 2205624533 5686341712 8150366284 0459653083 1070181484 6000510956 4931705424 4835346833 3159462545 1923778352 8859613644 8850524312 6798376206 2225575619 9299780566 2239516711 9285344454 9518229036 0417455968 3456704928 3873088655 7824453040 6524392583 3794977484 5549259011 6625690112 4811020690 8874445985 1613337407 0765559239 0589247944 8266046999 8111918882 7294256710 9558629702 2903714901 6339220147 1660097134 8864147999 4687491791 3294623268 4421112680 4122392746 1686228744 2931049097 3633444004 0109974456 4685443842 6102543627 0031190769 1249956169 2458225311 0611948539 8343310669 9057944847 2849579661 9214815826 7161720892 8790810381 9468031159 8041129669 5028476038 3812428027 0909169405 7916031929 4012701082 9853641237 6381585201 5671817123 4370627795 5666348003 6044307041 9113132052 5856709417 7321366080 8422994378 7168824239 5333234916 6660365833 5091037632 0780067026 2268527508 1103825292 1571557499 1747446957 6114419097 5240729948 7259576013 5178382463 2123783541 0494219376 1875810489 0817697262 2680495314 0708469295 3874311543 0829937036 5950448609 3735762452 8527458051 7420016791 6140220584 5966939718 2529771842 9382467244 2912575639 7000577743 1047122881 6100315172 0696018098 7552204100 6317943812 6082778188 4568484832 2342938639 2125824881 5401860260 5221826365 6821011666 9768821586 3405829245 4831206204 6240555503 5625915724 8874679162 7982013149 1571383813 8136532813 6242308594 0105654363 0670928921 0195495634 5382218405 0699533897 6924696326 5178434396 7059759727 7080755475 4794325604 1960528584 9397307730 1835617369 8536289247 0279803972 2314792627 2861354551 7956384564 5563551528 2341705312 8151084779 2982171115 4820919972 2861237838 4404874042 2102493966 6148779506 2767550417 7279678441 3757922906 9340716849 4367381726 0698238250 9622549244 9625570681 6559124939 6882714341 7270127182 5864879471 3681764151 6307044302 8453048861 2043170388 8493227178 0669466939 5190978399 0957932723 0718816619 4573843567 1480542662 5682767114 3077084995 5849824699 9972400856 7410703171 2433517399 1004938855 3047735816 6950083818 8706352668 2034540911 3676494495 1856208065 8836135824 1740908968 8558651569 1346805618 6675079962 9482956956 9532691422 1553454133 1048630779 8507361654 6399098244 9070126613 2056269498 5763239644 9741401591 3787756323 3916959208 0866355459 1612065895 0266395098 7516504530 2952733587 2369388230 5822800593 8763792379 3829058405 9565557950 9729115969 9505827809 6448419070 6436266721 6421646566 1889744516 9652305263 3382167427 1905635459 3013532607 5963803951 6768730561 4207012021 0888513519 9530169040 1114148969 3331358976 5496921819 1034304445 1512576783 7673357539 9449511662 8097713191 4898619408 1629597657 5179952095 1245305083 5768379239 2064018475 4318716627 1710301817 4794801910 9876592523 1868054710 5549772903 2257432565 6003461807 3762460651 0815665432 4338082252 7560984727 4872667138 2395416495 2529012981 6886146327 4985234501 5805267665 8423316673 7802322329 7054766093 4463961417 2928734073 6171862454 2874667889 5486031906 2334176932 0285088953 3739758399 5971276924 6642274391 1632738526 2900377013 1446756191 6684919666 8101484063 6195309822 1778739195 3432896576 5459315115 3220262780 0459503649 4733082838 0549666034 3300224955 4418223606 2336912243 8702474799 2662410344 8454404520 9092513443 3128526565 8102614887 0140454396 4768876931 1578603388 9869883081 4969939519 4295334462 6015962327 0922565021 0359610443 3069050054 3979446168 2082673593 8727564057 4044173209 5592116615 0567181517 7473502004 1738809076 9100775923 1598609904 8027005146 5888569968 2951266535 2100516799 5313414010 1229208103 8403581035 0833283677 1081446430 2829668867 7517291140 2299252546 8682823586 4367006726 2586769033 7680349889 7148743292 9968356607 4455168287 6795271344 3307036828 1922861329 7262523620 1498251332 3163134355 9707967384 9737685090 1894190524 4828680446 1847504357 0626759692 4525923080 4276682715 5002229508 7863329999 0312328947 2787898658 4286343666 6878710757 0982375763 2971026994 3598238797 2245736219 9803258932 4261054391 4919179775 7668475785 7527299404 0547044658 3464059671 2296987937 9304031150 9869681639 7449065722 1818769542 0697355574 4703090989 6702855756 7336584324 4192010722 2078002625 0310845169 5284646720 2650733475 0538416734 9147897243 2179343454 6783641098 6560770865 5030212930 9534558362 8123497947 0233323378 5509593772 8705106194 6631063710 4470509873 0862590161 2505464627 0481757089 5826700295 8380532283 8391571256 1735100089 0526110763 0651032756 6919072147 8199322744 8001055618 2297485459 4743827764 6246404301 8064001226 2172112841 0707340162 3566884807 6886157032 8339871672 1286763314 9635079060 5709110673 3456286539 3205119546 4426408152 0901768872 8307876391 1449296028 5792129361 9877074190 8431291810 7429343318 1953196063 2870579077 0209902451 0340788342 6348845825 6834147443

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square (given 2F³ > N).

Here, c₁²-4·c₂ is ≡ 21 (mod 64) and therefore cannot be a square and N is prime.