Primality Certificate for (11031^4177-1)/11030

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 36.086475% 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. Details of the proof of the primality of Φ₄₁₇₆(11031) have been PKZIPped into this file.

We set R = (N-1)/F. Note that GCD(F,R)=1 and Log(F)/Log(N) = 33.492822%

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 = 5 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₁= 10606 4165110102 2417741190 6861205320 2967445734 8857090118 7655948131 0264044684 0646055069 0560506312 6160485399 6765397623 1199435743 1081810133 7683339137 0877491180 4654505441 8491970380 0211214959 7362317803 3371621317 3653596432 5378815771 2353505378 4238980611 2623436567 8745927666 3777821419 2157266812 9850418358 4321308701 9701360045 3955145352 9761003054 7296446047 6595332353 7694940004 7758909812 0498269488 7158949098 2775445459 7119953750 4910854845 8441312520 8356224549 0544845269 3178999801 2216764151 1808868585 9042656730 9603221018 1904466993 8491651576 1523960572 8235095562 8271238104 5806435956 7424212608 9377284453 8854068417 7699809962 0426928052 9937135596 4241988627 5472646218 0613259421 9664285100 6707692436 8708673744 1545503740 9953266923 1955556215 7476318270 9795221201 1335097911 5370887190 7325764544 0779442102 6969125233 2462848650 1041799266 9649398852 0727244109 7369956695 6631721379 5462846024 8006465588 0549319342 0833449723 0029278720 0036828640 9124796163 3991191359 8185674912 0954779930 6048125962 6688112817 4671722918 0328446317 7411335780 4950842247 5476031595 1063502470 0966061838 5566458153 7950422705 4029334037 3262521138 5410196749 5545215452 4349055630 2474072586 5253386650 4093628197 8346490037 8431305936 7447022012 2566668329 2486312935 2551181972 5791583073 9977769000 9532441138 7959606167 3785186156 7748043978 7001453698 6145854184 8291661905 5204642930 4943231268 7024079359 4318985526 9613659273 0791523128 3570125315 1902418415 5756513128 0557999888 3071621992 1604021524 1522814589 2422627151 2924171827 9427483835 5758467332 2618630750 4068955166 8003209573 5342035932 7969930721 6312055789 4045547879 0839505366 2015903162 4503922774 4432617271 9671431998 5251309133 1653033018 9541365834 9386866947 0669322601 6792260089 3668831263 2673409136 7633606847 9671570858 4535115513 4525612204 8748241890 3560108178 7690462391 6599297047 2017149111 2931108154 7190574924 3942439058 1214312410 2997927790 3994581415 5342261720 9740005483 5549786947 5232975178 0062411873 9495860053 9318544219 6661169455 7110857924 3176699422 4732940142 2685000501 1446827940 3126308777 2587764118 8623814081 6944167463 8890231515 5125478941 7423025325 9853898757 0508434022 8944779352 1691250389 1123774233 7489020415 2477225101 5008573243 2862578984 8117395242 9216381628 7333419635 8657898852 1181402362 6258874054 2552655150 2681590979 3398592901 9683283127 7429797324 4781975882 8421380866 9639529155 8116271161 3825600452 3439842523 8967869869 1946210197 4677424002 1546105800 0945957197 9288692734 2682958260 0697245131 1464162669 1761881070 2882599645 3070151905 9560186923 6968607765 2670839524 2860003132 1028736098 1277466750 9836512989 6368262958 5605889508 1929614295 0867600029 6394651578 4598022856 4789027477 1527095577 5173758838 7495125132 8257165195 5549799237 0609401795 8285049411 6806914993 9542184106 8570009716 1745988342 2615075711 1807472281 8748649513 8335385030 0802874499 4822571716 5290209292 3947681821 1629783209 8055709450 5834675109 2927610546 4368537244 3688132648 2962908178 5607794443 7886215552 5364024546 1804067618 5186131922 4647063027 0962283977 4924990725 8139274516 4437461693 3487743971 4729034057 2326807358 9707630256 3838021331 1991186218 2800304884 1203927213 3192109709 3354174581 3162704302 9456279675 8039832420 2729117940 2660460502 2615725291 0780777446 1244579537 4771676394 8329135738 5389583489 5096820850 4468163296 0330519251 7554703587 2228999707 4144387108 6893266461 2367418699 3136225254 9712228420 4717579996 1016849485 2462121079 4526567395 6493219884 4835915919 9781369363 8748755328 2291261532 6839555952 4192245006 6760216777 8374516419 6610012314 3004350890 5361263106 0145948482 4694889825 5944057008 0517764497 3764934065 4624644925 7014447970 1036149860 7122409755 9368213968 1822846882 5171667346 7099145102 7794576573 7922917416 9708847356 3533020255 3748004696 6156883783 5270955342 0312193385 8485447034 4180303099 9231386486 9838872736 1622551781 4182107960 0876950216 5830757774 1563898712 8633063225 9725813029 8319293794 1799228970 1365020558 1448657528 3601484031 2749532812 2089998155 1026894559 8494101127 8838499466 0732969878 6366463607 3788184652 0846992883 2297805699 3396039316 4768137420 5421481101 2405565015 3273413654 1319018910 1339600369 4686626024 9377338900 7713739508 3131878494 0311828240 5938372358 7381084489 9424912037 1219403343 8091666525 6980561298 4570646334 2663268150 8881988089 5754281046 6366042429 7230578401 0823332725 6792368005 9961410439 5028212090 9281564565 7158403152 2548794403 0422925171 8331925106 4617092904 2370257404 8660683958 6351935336 1419757632 0465563900 6914387388 0958321850 8079860865 3573198184 6349347887 5893758889 4229064259 8282024367 1678119925 8763877614 2717040560 9770360126 4716728250 6640300253 8262291694 0818391835 0173936740 5647212154 8839576936 5757956488 5195957604 4714189806 7232543584 2300184261 6952975122 4895037624 7969184205 3952721120 7465889162 4488847221 9436180469 6252719590 4490542245 7960071987 0814787812 2729036417 3669419843 9669666255 4290428600 6560309877 9883401064 7595936674 6293664502 0253850641 3204943725 5327418363 1312948377 5905081229 9720267472 9295778686 2230688977 4781045480 8357390682 3456539955 4459593205 2345512269 8693948265 0701028027 9970607309 7709793696 8556663813 0486847830 1152088665 4568596863 1627258626 8806656160 0224396424 7312579145 7764596021 1641660279 9773551626 2419004677 8685445500 6708824115 5353688159 7612713149 9823595099 5315591859 7137313925 5699660296 2521493819 7561903120 5811901912 1040778846 3555868818 8998352537 5772210594 9076110961 7260874107 0321758361 8770436188 0418491458 1312452817 6943576913 5914965932 8450845540 3369396116 3581905240 3160804282 3550957002 2158913715 8441443117 4212913090 8618045470 2183727670 8962943353 8719316930 5942722276 9629536514 0031803160 2489461636 0836183112 2422293198 6999251802 0603655321 6153781532 7356323142 6514079765 7711197609 6217272974 3590367612 3858298461 4746077460 1341645559 4561002819 5572731955 2203073468 3875760308 8372172627 2559619842 6424656518 1077027919 1852714898 8564215077 7599487223 4787721760 2720734265 8032308714 7738353210 4667346846 2204379249 8962662990 6649551493 8813412147
• c₂= 2953 3600857203 5519457077 1721714860 3517394875 8329642124 5955166653 2727972001 7945279429 2546061984 1624198567 9035838045 0896987407 6086448661 4880946618 9215879080 3946279430 5834899758 3477685924 4753390302 5608131972 6490133761 9052004179 4093294841 2343811680 9148380772 9584856982 9210544789 3006965224 3227894348 6800966834 2831890489 2930402344 5637692753 9602897756 0957536361 7217337615 6628074168 4824823055 9556049995 0184312245 7194077316 5112841903 8153785300 0786374341 0590876501 0282966294 9012744022 4955193226 6865292453 2448855377 6922138822 6982639348 7477347174 7884609270 6945187361 7487774719 8076670461 5318434317 7514941179 9671646494 1777543850 3735863930 2660806222 1624880159 7475043452 9591005194 5895069554 5355135394 4789542801 6533747738 0826933406 1853843954 8431559370 9853960508 6633566069 4686485083 1779387638 8297434441 2393461315 7093135515 6330938429 6505525532 2932265187 5418210065 7191919330 1415622505 4241923029 1330773253 5566403672 8833581609 7083464223 1159504348 4386450754 0378912036 6439266963 6360603617 4968173692 0043917329 8970007912 7367854534 9257137084 7135264604 3194700417 6041573956 3135768300 3182551022 9551165697 4742481463 3260710441 3545329293 4163728770 5477468806 7125378226 0898983027 7752337772 2650878697 2919017411 5930452438 6136347233 0140878731 8570052207 6300336716 8784208911 4374551302 7279796061 9932466905 2086034284 2168214136 6871137429 6542421540 6244701295 6147432878 5886668843 2506136692 5114964609 3852963468 7006203301 1973099543 3663212502 3977726580 4583533595 3036328061 9721657491 2864380466 2667973765 8320998234 0479794009 4972560583 5112458603 9348786633 0114989265 2987366336 0193851506 7510541360 1333927190 1939709642 5698934043 1235163483 2098937946 6299454475 0089817557 6260987249 7377644537 6827034985 6122053520 2498108521 4239051906 1621183392 7399354351 6783601586 7846673270 9362714088 4644536593 3498597382 1139616091 3172329070 8970099750 7644900839 4319382170 3259460647 1864932491 2639902089 6631202680 7709056821 1831301782 7188360843 0912075364 8377315705 4172272081 7499508115 2601671728 7155945165 4442415515 7980942145 5757215658 6168307839 4804325484 3288156332 0396823117 0432018622 9602958077 1737078592 4392337251 7325698877 6835675624 8969629107 4311997081 1185740298 7940399248 2256910574 9122634208 1162242053 4247577201 4056657894 6006847831 2174912735 9775061985 8268218710 2062696074 8437229009 2929470570 6790440181 2349541947 9415425191 7480004910 2215279779 9221458142 2176917134 7270908824 8926923074 6257162024 5300484943 0313021634 6286376128 5111118818 4180715489 0101224750 4214307938 0069978560 6328882446 6725278122 2951494981 7617061632 5274704489 6138535112 9904045638 8136844385 7250388975 0195520133 8038063945 6694350715 0775849244 2518533547 4456072344 5675309697 0627196002 0795640999 4911903586 6479527189 7632680419 1843162650 8701431367 6975772695 8399084567 2385299923 5773320614 5650644932 1776103437 7330671270 5610016148 8329534960 4351048588 4744145286 5872058750 1418873437 8493646901 4260625493 2612731114 3241120802 8044418328 9720214603 8981722372 8750623734 2347832635 9964767842 0215613000 8142577739 9962505048 3239568738 0572204320 3484763129 0506511719 4862700998 7785947440 8836690611 6464245502 9169369501 3788314893 7755043394 5013362372 4790047962 8307479539 4654304174 4507082398 7865784097 9614530927 7135669843 0489384974 8503239339 3537512485 2040369187 3712254701 3578354031 4338062103 1447783369 8360989841 7478777392 0429788745 0793417640 7507497932 0067011695 9873184797 0703524033 8750861638 7104990032 0550527388 9050240541 9578021220 8795102962 7463923031 8326507470 9645032886 8388528164 6874651090 7066920237 8636654942 1790465494 9695808745 8674343085 3031457562 2111507422 3151830724 5769368914 2731638448 4659411631 0025183192 9516581186 1037511979 4549947881 8862214139 2793625345 6732734712 1919933990 9652169501 6094371913 1758401946 0921791358 2597493935 4688158016 5534611184 0360809120 2728016749 4633798784 6264490658 5129862427 4273351287 2576169948 7836540485 1966353231 8567974240 9855322536 0534816294 7816029134 8592189798 7981138727 4828368042 5073888391 2673729835 7260751826 9766970742 2758013404 8105253285 1086791692 5318545156 0809955473 4304918671 2182698623 9016715461 7948748895 7776560544 2475677339 6328857159 9588349470 5644616296 9994544540 8217689559 7015952176 2728164142 8915320315 9683953000 5980539941 6702969355 6333791028 4985099106 1852809472 9875754208 7244710546 6276757148 7809512608 5562641061 9185986403 8759255011 6990258613 2714434684 5205801187 3147738231 7678239410 2946611818 6664066983 4317092243 4533539606 4952911024 1394633959 3818088530 1851809914 3180986835 8804412794 4338575546 1071338233 3887882829 9424434551 1769438312 3568155590 4348107060 8305567339 8437962019 6200086672 0177273384 9193953148 4816982929 5556614961 5661072330 1057805676 9256045421 2451665267 8912627474 2252465379 8326041958 4966078381 2774442257 7484951617 8815462798 9150663996 0133112432 9708067822 8417122516 0510240885 8857722005 9239021132 8819484702 0773726942 5559848414 3798328612 7319058230 7983885463 1477189918 3202005207 2377005282 5695528848 6014665758 3393368538 9048013148 4885071240 0651915346 3149697980 5810507170 2740376323 2405084677 1037718137 4305540008 8250563530 4458740485 3664945677 8379852846 7156621603 9360684848 7192101216 2667965849 3904910677 6188313104 8792509653 7831023722 1569408731 8326466998 6488982026 9824887973 6934805819 2267066366 5659080967 0861484777 6444924183 0086388230 0288058427 4582963810 1838195250 4171826383 6477173276 6715781860 3343469328 9698639686 9559822151 8257250166 8080164662 5603024983 2674148221 1903817937 4144004396 7838428913 7825965722 0951344138 7168585033 1696712302 4430761536 6454707143 3515041299 6527855805 7910209935 8906782947 7359293000 5116882970 1096867353 4329106010 3504583620 2990208478 6298445610 8356583169 0790323554 9309911217 9670365685 2914373367 3313221567 6247294105 7499202534 5473863307 1431878844 8511083834 1842421587 7241612709 8558766723 3711139200 6937057805 7502447806 3529381839 6446153514 2755969731 7295811908 0058385509

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.