Primality Certificate for (2389^3769-1)/2388

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 35.061957% 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.383752%

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 = 31 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₁= 60073997 9500135639 9893905590 5212505557 5170342658 9229279368 9243472685 1333864527 7330826389 9879822470 5966153559 6357006588 5257593489 5851474298 3783089481 8391844896 9348944175 9516888047 9317173763 7654397223 3067802697 7066937618 1775218822 1770166560 0417176653 7191328270 4613066586 9385160468 7317460568 7787910059 3777731295 3206516734 8237524464 9476509941 4934861229 1584354091 0412082559 1847913354 6076703886 3157722696 4318818091 6891857030 6464962214 8165974761 8509811127 8653084139 9535976586 2196427890 6540823968 9763690830 9243522580 1486293905 7018399889 5949610836 0069181483 8625206075 2742044667 3528160134 8072844956 1057130612 5061948369 9576414977 8873807184 2911727690 9453500175 5778378623 0314190767 7277031848 5024339243 5041243479 9938504348 7392957608 6812722930 8594743682 7049727682 2603188995 1794041572 4269015753 3229397983 7780169307 0125466841 5464673293 0986170170 5070316282 0649857699 3096765171 5308817948 5550087699 6855068299 1829656096 6504325274 0404909604 4365250588 6515841977 4850148122 3105679137 2959832598 6532739490 8885318347 1378617076 2753222464 8441642153 1194573120 9877937796 9508520991 6198937539 9012413497 4386751065 0292718736 2877377940 3128823709 4788815324 9473307338 9332146782 4838119695 7329572926 9759658071 4745739735 7421401451 3268373242 1573349043 0245939149 2374377070 4940907395 0550072594 5207426725 5611412554 7093673963 3646212838 8306272697 2414459142 5884549371 7708290728 6213006586 7387303468 1160800925 6410540600 0609377023 5316774807 0054749788 6851194210 3298042039 0703855855 1498312036 1798940822 3924119234 1237285756 9195048947 0520314315 2703788496 5099581902 9189412244 7147799723 1975632270 9603124410 6471510540 6426719601 6355651018 3959147838 8303915563 4469750054 1318361263 8363864493 4362634761 1996406415 7696608736 7469413055 2446022017 4888911852 4165220960 4424418239 0409553641 5389687170 9419576938 1851702450 8062555189 6036936723 4825934016 5788147842 6147484539 0951861070 8303601598 7391200646 0656140173 1503233418 1729139727 5662701684 0441580518 1751506075 9351466812 5132059690 9157991664 2390833860 7349050784 7533458993 4205250569 0120413289 3448134652 9074024025 9461949492 9750268602 2511787771 2941670475 1574897597 3619318326 2120524543 7414829965 8355580798 2342910583 7210287102 3563329819 9685744293 7625020122 7321225247 1007117335 5928185464 5603155986 0030167241 9524894611 7906639247 5839851224 3000088496 6680093289 9867595410 5641723899 9714669433 2101557769 2950663558 1149006618 9945453745 0581508849 3035577344 8807664418 7349452143 5634542931 0152564933 0628771598 1711064352 7235647990 9162420616 0894111390 9783309809 5177376979 4599325083 5399438098 7309930733 1911065858 9567039431 4755605732 5230287751 6482670288 6257712059 9170731726 1106705542 3596168547 9917751756 7005821604 6830642319 0858407707 2839828881 6043485038 0227578989 1738876018 0740913398 2176541690 2242279383 0897085973 4132809891 3894766561 4718269497 8054352251 6204612942 2898076050 8318258008 5391930878 9844598949 2913433556 8134866853 0454642341 7435758562 1338453893 4247602737 5840870366 0091250207 6649209149 1167113557 5912330254 2200509582 5037690732 3908373036 6429448310 0665538756 0332816641 9717012263 7008621910 5879971813 2687273079 8313059802 9995181664 1728555086 0291119843 5234735355 8548776379 9905737820 7226019302 3645804440 1708418705 5624062254 8866390880 6647153846 5889667101 2564211746 9140429866 7988709299 8124047958 1689493641 8929256006 0664056464 2599755623 0543985855 6431692340 9435449412 2418327564 2433763772 6870639073 3199419532 4939181501 5454500313 4385369057 0315023607 3221936950 2501096180 1939641613 5333499393 4281658517 2006566705 8304435693 2864708115 4665991503 1641777795 2530729451 4874864542 7349190508 7643261482 9439343936 1412169183 7976964387 8104740906 8046378825 9862952513 1097969109 5727474592 7331728220 2679567418 9666924976 6221103908 8390092508 7971370208 9410915072 6173854727 4535324919 8940432870 3231555927 9277264183 8821287937 8586706407 7976649744 6756918467 4746017802 4213262088 9433135439 0318099946 6731704134 0922059106 6883112764 6479082461 8066615538 3698135685 0729643882 8090598225 2939520614 9664518328 3000221868 0871835553 0024758996 5139958153 0279163288 4991432320 4198811827 2607608932 4057466390 2229388174 5956387568 7718883196 7863826739 8592159340 4853986597 3982460822 7959739779 5633798874 0956559706 7961976189 5845631910 8645490071 1220071787 7163234954 9604160356 8959672017 2425552409 7506391403 5933753780 9978527487 8315509405 3046518587 7020494231 6277466742 7990911156 5989571485 5521096750 1770977914 5799037410 2098164977 5775559649 2381078467 0327417426
• c₂= 1 5988003623 6542313164 4791013801 8477352814 5579779342 8138329968 7471729810 7843639631 6690281325 0165056928 8964276726 4950550075 5001326632 2062018018 9274203821 3183760974 3922102449 7700065478 3970958004 8755731598 2671084999 5460238711 8486923850 2012506114 5447904057 3502664569 4764828856 9329828937 0299819597 2292799021 8018336412 8396097350 1833026809 3147899847 9638741332 2918520662 5647380304 7637943233 1797012455 1100123244 5169218602 9715754287 3254682480 9624964227 4842713763 1111530418 4953156124 3126499798 8710856227 6440803001 5488475120 5097879403 5891825480 9340991831 2517103895 0171821049 5401442098 6404558462 4003376029 3459667343 3960011416 7709032744 6891735650 9432073931 8333809668 6811895864 1302568304 3890022123 5434516065 1496397454 0265382676 0228247595 4310840758 3264582377 9483921783 9900817819 6593741364 2654032064 8191557211 6418978977 9386858777 4183781109 5467388772 2952936060 5302085391 9186432965 2609717778 0710022785 1005620844 7995634016 3063953180 1078762862 8552732423 1140732298 9878978704 5377336215 1628467792 0620409393 5384959595 3888818722 0326267838 3497242451 4668857653 3892735288 4327917342 6741222437 8448584480 8223816401 0040789016 5637815982 4176235588 3590545957 7393655739 0413933122 0380401429 7834865378 1164078584 4800145186 9634368535 0281517687 1704882551 8173412124 3315425094 7920533858 1384692995 0695455533 9742850379 9966669609 0277133057 1563219744 2796490963 8578902548 0447116732 7007642423 3701051023 2081726610 3457371291 1239362657 8793728490 7693153423 5862855420 4462672758 0963112421 0632273383 2455344025 0862882032 9920704718 6317100660 3721730210 5244360848 8543437185 0977630944 3593515848 2411395101 1936054807 4432017488 3293566178 1528530459 2127300872 4622964923 8025239621 7218332808 4818890993 9812091463 2253989879 2617828345 3270081660 0661794333 6612681079 4459796933 3016974887 7070112532 4749908053 8824148519 2721203223 3565435115 4830581469 2469027171 1454616417 2760380575 1067790738 8361755495 9460729928 2099446225 8486847719 4505670867 1267941802 1415161314 7612842711 7770336053 3486128198 3531776118 0441835857 9139965065 4511998354 8683037041 5710423701 3856382085 8918488282 8246409720 6563790182 5882315238 1399448632 1934251052 9765031953 5182429487 4881197502 9830271323 9776492445 2353093026 2469394109 9577245463 2788437145 2746762480 5048419915 8945570673 3685985981 8326642094 1206133140 2608217050 1310316134 1438342562 3499570100 2440795615 4757873318 1817592017 1895516889 6278797624 6886030132 7353403394 9867390667 8955624728 5475443065 4867207936 8520362308 6524726134 5495205490 3602031240 1364027117 0079711857 0118411323 7078849730 7491184987 6582659263 8770514952 1314113415 5445478852 3754513302 1698213947 7370693837 6936853036 5563395937 3902465360 5742262689 1894461671 6787822706 6024985351 4152888548 0359880582 3698770947 2718290622 7131240572 2690453929 5972635234 8094360643 5327939497 5071684814 1501648261 8085939664 8858381237 1018102851 1223928467 9074597009 3364299455 2205550189 0229503212 8276660462 3406332973 2896846857 9518569623 6296898907 2618067403 0360772578 9312526554 3190191146 8754152333 4647724256 1403456788 6703809934 6760130059 2191494162 0360389049 8490122028 6258873211 2972699542 3962933629 4510627002 8296778107 0151132516 9397084596 4696843193 5692834366 8829324048 8215585342 7491789008 4520368792 4715103599 4631051034 1261044394 3498441720 9847197566 7368083577 4214616275 4054913213 2082610209 1300418958 9487398894 2135680220 1081416532 9954748144 2365956512 8697948638 6891972150 1963244501 9419624881 5241522518 2602108479 7993951873 9277013288 1904780820 2397285477 0294495787 8761441093 9330318852 0660613426 9973019438 3797829513 1279621219 3183127079 6284705292 3886470293 4265089229 0475367483 9165020553 9224129643 7570558788 0889884385 4667907613 3091225182 8558151927 3029709260 9387680785 6775797094 2819191647 5087993073 5422635398 7801769000 1518373533 9237810862 5625236897 9448689372 6125721648 9457792086 7177760236 9488589465 2470255524 5356462227 0219411234 2368208385 9557112830 1010250054 0980634375 2928575928 6425590195 8259017160 2196170627 2823775084 9023371120 0835849430 5565941358 8266340141 4185499859 4706910275 6634695321 5826379484 3092689310 7206703662 4928792215 0044186060 4272148746 3991075975 3806329198 1186774261 4543407574 0467113381 1766792623 1301181244 9882914500 4088997815 1242470487 6877682795 8483485661 7763180017 5177455717 0011831824 2629344048 2420837341 8027436699 7959441925 3177649730 5714782595 1255587544 1620248998 8438607233 7486095645 1326394890 4891853925 2566552934 2564665812 8539448704 1195140291 2606638251 8366295046

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