Primality Certificate for (2153^3877-1)/2152

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 40.257103% 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.687998%

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₁= 54 8127648840 0144511460 0686327195 5871316888 9489908801 2335691221 7951384236 9666840137 0945251923 1346948941 5326458748 6045425952 9285683860 9977147477 4533809223 8370719442 0260839251 3786416810 0658951217 8556312252 3657946150 5880909344 0675154253 8801873149 6528661624 0092272343 9919341035 5802444791 4499728216 4150561219 6507166523 5514627542 7803813513 6863283336 5340907967 2555816159 2963905432 8843102273 5749936356 2723378451 1119153608 8659349897 1693533346 8199570084 9086189615 9293766348 5634997945 4554578819 6307824363 1754109522 3753174276 4127054186 3122012689 6591271109 7375260068 0109258674 2473305885 6075992948 2993263705 4972164872 9683220942 1881375946 5046466734 5454559542 4031680677 7466527863 3909329926 5995275223 1692232707 1614465811 8287205926 9842189544 1445069484 6700633907 7740538604 9656579015 1118149292 6650083007 0790373970 7904287208 1629153582 1686930035 2561488359 5857022787 1497862495 4820263668 2768196280 5495745999 0216335762 8872232298 5240162446 0883844772 9945388035 0301071142 1855195222 4417088514 9968544201 2974174169 3398434037 2927644562 7597445196 1306610586 8452004854 3485621421 6287922540 1851374885 8504626756 4475175733 1794296784 9441685874 3867174535 4766933378 3672789312 4458590431 1499178713 1904344893 8860263123 6261337314 3644764360 4552609304 3658551816 3852177696 8659287355 9845365437 5894954656 7658748757 0781333057 2878148213 9914128136 1547897373 2046152590 4192997992 9453012101 0587409765 4695086318 8213772570 5133329154 1922885782 2035256316 0397418770 2038992446 0046540445 9867611939 0149579137 3195362660 2666893702 5846027924 7866878075 1974504293 7699833399 0900869047 7260881879 4533780712 0919896672 2277145483 6282729826 1070540825 5732743561 2859327788 3237967105 1520752235 9396414544 4441874498 3847207528 9713081577 5918860354 5257772394 6253782463 1184920327 1283304253 9941573158 0518306250 3125262499 7070820206 0366851491 1926669841 2120808404 5392911936 7191193717 5455746966 7630464928 5044315510 9883521870 4210716811 5456389392 7389496831 8028414091 8883063432 5674586734 9864303618 8070447465 6819550763 7281546754 3147674677 1076744765 1603597015 6953058302 3340070223 3406597281 2877212294 1432292251 9907466131 0257066389 2539655402 9444208638 0719651283 0735474623 9361171887 3261221463 7364693142 4215780388 4989264109 6251426350 1276831422 4682633712 3320721583 0472075210 9992008012 5459715343 0860479034 1024517131 9204308937 0027699480 4804216713 9912004230 7761297013 2003209523 7070583414 0336295641 9634429840 1450839544 2981514202 1060061855 8800884652 5952841569 9890709467 6010325657 9269943596 4346233091 8581578647 0054336414 2402589974 5376350697 3026324281 3170658585 2464321207 3466341071 1212555507 4526079716 0117095516 4572050693 5924773818 7918183032 8303117739 8338243938 3654923426 1646659586 1089488833 9316727158 9944962869 9419775930 4219253248 4165818033 1647708579 4581072161 5573795850 6703901869 5343241482 7958735005 5981440715 3354318287 8493968789 9037015871 7969072289 0660255265 0262562403 4240311247 0269872294 4849323922 4238237897 6336212719 0330224454 4640955406 2528797487 2676683047 4629733109 5304770718 5983391069 3337445675 7445006117 1914602487 1822859454 8146988079 6441677647 3234564537 6639622898 5391371192 5740199042 0252848412 1779537433 3801613610 6147982401 3649656020 8103710933 5966497521 4812167195 7733178496 7387214860 7475333852 4041229838 5705294454 6509959837 7163132046 3740577420 5068579877 7797174088 9149566450 8199846772 9545578979 6735476022 1237306484 3317559341 4880437662 0629806124 4971886589 8680486757 3133166592 5460073778 3057948400 1456994517 1495030743 9606757317 2318464117 1556144737 0294553759 7487316816 2029117470 2065691129 2955382203 7449393173 2293312468 8489913955 8054148453 5221070983 6807027575 4083307437 6204032874 5232067594 3522724324 3978920272 4989282283 9910046754 5573912476 7111410937 0986284811 8579596776 1376076810 0506242695 8232764066 8511891675 5290603084 2591760357 0424526446 0730016918 8284194457 6025435826 9675950346 4780560368 0890283303 5070775240 2234554701 5181875494 8569994259 6097123131 1414445101 2030637168 1695121693 8815878997 2633414646 7905306865 6005682839 3934604713 0204190183 3913430647 6618211281 3197967100 3998269160 0929743730 4088962132 2989482450 7305118144 8695647167 5170922979 9426892866 2672377029 3375083251 5526454390 1493255595 8549933854 0270309644 0472808183 1281815937 6989634554 2621726405 1106050889 1331587182 3171488480 5750479970 5106102824 0560166844 5118806568 3482457479 5565610819 2613182192 4304272904 5341772497 1635456139 9739157599 1383293455 9320644421 2969392588 7334626661 2273754911 6212755435 9780496334 7734699112 6563346734 1579920459 8663767203 9090378062 7325920767 2169593242 3922451068 2823710672 6682948720
• c₂= 45237 4709026950 8566640992 7364990591 0234925293 8990133365 8054363055 3886396417 4469881909 3374638750 7972109554 5395137381 9857219251 1235557651 1259244654 4498795975 1445003166 3861076257 8661124293 4831437115 3498835922 7357914594 6313604518 3032575761 0449018170 3711896108 1907685766 1481832071 1407935614 1405735476 0604810678 5199549952 4412228135 2714709370 7958776401 4194068595 6602935300 5242918409 0463003572 5693205308 6549884474 1876487009 3089833979 0725864425 3867452886 7452877698 1105054094 1152917321 4336205701 1307323016 6425942882 3150116620 8442613697 1397909328 5958150275 5167236981 9297719626 6064554260 6631337252 1787092465 2724637047 7019061930 7437845290 3255105914 1739601167 6511655432 6786685804 2417452275 3536714501 2823958299 4203221097 8196517805 0587329551 0330808208 3696218679 0145901941 4201889470 3230142615 6423779264 9042602171 8370975399 7821086448 1596640307 4340123113 2014602141 6815290238 1797963593 6333998670 6575665627 9706664695 4471306511 0060763269 7500011531 6448693844 0719215459 9626454013 5394266594 7289099945 6336668512 6839307158 8284840302 5053994461 2750982216 8733846879 2336154770 8510679486 5898536348 9420462517 6856300895 7371289254 7884836698 9352821793 3980148419 3822554293 4429048242 9658049120 3425354808 9058188746 8559206998 1090850723 7685875849 0692200247 7111028316 9664086080 1762739736 0785605497 4072350140 2967327374 4538537458 5726699141 9040466386 8398590848 8138641537 4429812564 2808700759 4353628480 7628390752 4210360279 5925575200 8394339015 7711671736 5795008436 3119574270 0520676206 5404426806 4563798486 3675565611 9339324864 7343251635 8031585994 9583059712 9144556573 7138093492 0697869874 9209313895 6080221708 9823306550 3343624384 3561624214 4577597666 9660689283 1797888443 2090526306 7253718354 9255037208 4648111040 8701388246 2786706650 8109744198 6451376961 9665249021 8881686983 5659886531 5509239260 3840314209 9961139698 5390201518 6458061731 2167754320 6270979524 6114464794 1973845827 8007586115 8390935568 9593608055 7896847065 0390175578 5964707393 1332679995 5218362469 0564986246 8314421943 7629022894 9937310104 0847042870 0273005056 3946072748 5417019872 7379524379 3970356803 7096832618 4211454631 4984965942 7937807567 3394297779 8710415816 7785025105 3961220414 0513208883 3902841296 5774275333 2592905808 3420985755 1037222839 6032852346 9404069180 4913563396 9907690298 8520290391 7248498637 5945019894 4829623302 1043234279 2740072994 3186382640 3739583654 7075180896 9559900156 6671776113 5552941369 0518881117 1248107883 1951189456 8978413872 2296687462 0530930544 8619049652 2352301018 5472394815 2338624663 4864789600 5645593182 4788353247 0989793195 8366600815 5432115814 9083141424 8836685867 0587559780 4272269971 8523724457 3927941011 1385306641 8968189022 0174758755 2013429035 8212851154 0456925629 9114447542 5652049654 1337287189 1612399947 6588700645 7881058933 6678696411 7255690773 9373842828 2665323858 5153197004 0756492320 9811973614 5185679121 1168021057 1102279674 4639433823 4448018331 0091848499 6239254573 3173894503 2344903823 2180108940 8983274978 1214275728 2959518549 6863374475 7674913532 4224159803 1824096510 6340997013 2617317093 2309238403 1230907150 1667892598 9067904338 0705212659 5532411779 7758928175 3821034381 8244531576 0478498044 3349361206 6011013228 0580394977 9958073948 5332676135 7208008352 0948996579 9623216091 6464097921 4545397652 2889627369 0694351927 4804047132 8629727421 4725151342 3375889173 6939248836 6627891726 9631373835 3007963147 2365109862 4573223640 3910786523 4974062041 9131867482 5233255410 1717277489 1660523838 1945499424 6158092634 7510405814 2165639852 5439993820 1113073639 9927077073 7945323631 2407739876 3034284601 9737399609 9970447886 1684931018 3196469543 7944134355 5473695847 9089754593 5005009045 5218357481 5825343788 7636512507 9650444650 1747191052 3045904421 0932021860 8340566680 6377225170 9981339962 4478993387 7533391854 0706935094 3575216218 2891872438 2099202319 7871243757 5963035476 8784219726 2239895020 8568370407 0628278541 5175369816 2164798985 9700210490 9103498068 1309230837 9783173393 0674204275 0349711398 4428900135 6504633483 7906716775 3109605428 3945010979 4672469688 9980005670 6015002612 8795743040 4452707251 5186523527 8261180544 3933111513 5033949416 8854922017 9944325445 6097836432 2797646202 3865673900 3458804662 0910861387 6875480298 4354344584 7632947009 9911556573 5962359495 1908582372 4968207415 0754546050 0607052891 1312858563 6138490209 3397112373 9373758977 0406096909 3841259322 2617190525 8105273684 0273060700 6912806854 5709267964 0731064585 0131604541 7827181450 0519461868 7043109380

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