Primality Certificate for (4411^2161-1)/4410

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.362390% 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.343270%

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 = 53 suffices.

Express N in base F

As F² < N < F³ and N ≡ 1 (mod F), we can let N = c₂·F² + c₁·F + 1.

• c₁= 40922 6127269050 4651466399 0877438991 3161635076 9742905397 4423806650 0859865704 8583217981 6669930399 5591722324 3449201696 7783525766 6745950515 1200274833 2425411617 0793458866 4204775535 1947833577 7314296826 8949268343 9104757106 0235718602 5249419339 9828937696 2686236971 7515543519 8342231068 2189557386 7827868553 1467872866 3267838773 4173783610 5672315380 6229535244 7006564946 1245281313 6195141704 5297883540 5889913528 1536533481 2130538024 6305157299 2111739322 8857021123 9842186614 0605919467 8467718404 6102472069 5879999420 3060107462 8308597784 8591371236 3222397293 3861066021 5623068477 6847636203 4451629905 9382856347 0255533639 8694993183 3765732965 8460892973 9218897027 6159979540 9526168499 7471973460 4517333201 0725464165 7135201845 8897215829 7370263541 5577021059 0747368692 6924797504 2537591412 5422802584 1807114200 7021437954 6312229203 2215340364 5080085972 7736702584 7228540387 1083538093 3590691951 0032377445 9425845662 8029040319 2665159080 4697323894 0603660926 6202578174 5004335719 0743479437 4816862010 8503407471 0302017857 0177355365 4660654810 6815824655 9476865659 1393986976 2845703323 8406945572 1120943058 6626899465 8457699002 8609275684 4707196837 2375942844 2136858785 6366400905 2188754658 4006340404 7061979642 2638385856 5030138854 0783382952 2085525338 3890741524 8067900919 8885801710 6478766683 0361524017 7826055577 2589615570 1536043658 9568186117 4683174394 0944450120 9871908617 3410472623 1896901316 7201798212 3360438399 8808933287 6708688030 7280058662 1611772478 9314922840 7733273551 6848678912 6377441331 5377641789 1457724290 4327092526 6802358859 0453692032 7563773771 9706893574 3095677310 4996954370 4666847683 4520616183 9504794001 7676384362 9241797973 2853529629 6979207155 9101073942 1710669257 4319438304 4148222000 5354526727 8245862562 4885986941 2510668880 0107619056 0750635233 9590991453 0082645788 4626785294 9733256759 0273015651 7524980909 1304981765 1997197259 2611310531 4360934230 5357492944 7413669306 1879629832 8504869030 0119605726 7134398305 3365430407 8441155780 8914925802 5489548192 2223721087 0182323917 8631955201 4886654544 9742852059 8415677729 1477028185 5876573777 6554210693 8219861938 2829685809 0980531936 7150117333 0907318802 3658301595 2886523139 2061940292 7215121960 7574058749 3076891401 5701505953 7148694688 2545797669 4372007619 5200105763 1888450699 3637765485 5075003214 0346739332 7045361617 8318577642 6501348391 4261870946 1339442458 0466163810 2936241644 0137743018 5430775369 8326695008 2363616924 8010228147 0380316071 4380544922 1394259111 5566440133 5810350573 2280544220 3616311179 1974001377 8412011812 7265157206 0679306114 5696961070 2788189695 9147887302 1020427679 8529582054 0527487797 2705340653 2649837244 7504177774 0130179450 7038352874 7003579880 7678495744 7613126878 8839042506 8323799352 6757449768 9642158798 0227271805 6613294942 7387763184
• c₂= 317 9009455316 4128307943 2076200512 8624407191 9770315350 2260251264 5585299759 8200231494 8494190690 7003096293 3815794983 7723560604 6294141316 0349772762 8987515892 3092859000 3907642695 1379870974 3718902469 0646659480 7952183252 3483440070 8148882613 2276375221 0712589373 3365899338 6475515436 6789560805 3350235569 7399970766 1100476612 4869630903 8721961643 9971619539 4119716839 1027933031 6856311456 6854984526 3660476736 4872043860 0699839229 5157944965 6988102641 7445883464 7914783589 6960306235 1174511025 8418089113 1583823371 1576843369 7413004246 7758478349 7510290062 1448727153 4023824808 3675076139 9618784957 5819537957 9154934554 8390571681 0792808612 4466168140 5097977281 9447431595 5582051515 0448345163 6219512923 1730610403 4268254940 7938476219 3156693438 2011999678 8079077790 7455464055 0444746466 1301988550 2436012785 5546317963 3759694299 5698289558 3074076497 9727033633 4277052367 6489473974 8204544549 6648107918 6582882976 1427341743 7959027705 6300218205 8432592488 5897718556 8200346685 0936542103 8827268451 0720152117 2437554698 4189507731 9298985736 5672674253 8645591920 7431093667 0643310356 2921616927 1608139835 7890939671 9753230107 1568859370 4673440661 0772752808 0149490242 8128779910 6622048006 3749076449 2353831604 2920072282 0865039794 0716247043 2880780354 9244062390 1105225761 4482013102 7646405320 5844642984 0456540776 2038870110 3165697682 2651607832 9254321033 0561803875 8290726424 7897549210 2400074755 7647108127 3260735945 0996148933 1429725241 4267299449 3564545298 5462501910 8811646745 6328152752 1207007742 2041611973 0637636164 2441108465 5776235093 7498789478 5434503550 5769401124 5042260443 8817562904 5855910601 2610042849 5115394859 2574244020 3707365156 7146807435 1916656092 5642346935 5501589331 9354160132 0118406859 5453410562 0216188241 1000093449 2921895440 9117567369 0098759507 0262165822 0034331033 0544130621 3543868581 6927070628 6368276976 2991629516 1405518802 1775462551 2844246711 6938265756 9112533161 6284573421 5052573382 6153422110 8319044185 4895393077 3915121597 4218659262 4272648676 9944407975 4316353006 9451921537 6075253708 3961752241 9360235606 8616680925 5920595460 3078266885 6238783939 3616630948 3647231154 6258418672 7458045167 8381469781 5952944079 1290800752 4325416079 0272206597 7584114688 1100983552 5899306939 1106724403 3699910619 8598975916 5203951837 9076209980 9214844542 4803590505 1922444815 5415533785 6908360387 7821316089 1615122039 5905376450 8631108162 4564568759 1533406752 8810961210 8961246167 1776434356 1894761273 2423576019 7040949473 8575788402 5463145201 8824586792 9763130198 0832672792 7219848592 2938309878 3180744608 7509013385 7165600266 5736026621 4001784790 4867249524 6805778644 0291449823 4109065155 9646288630 6806864698 1245059838 2576735108 5399933964 5213539606 6241808563 7963143232 1793547365 8773774172 5330618223 0373289348 7537426256

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square.

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