Primality Certificate for (4447^2347-1)/4446

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 37.920000% 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.568608%

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₁= 262 0307120422 7818356769 3166645716 6394989238 0079169715 5354804908 3002137419 3144596402 8367719697 4256352518 6251579553 4115744936 2428756874 8583031967 2638558079 7010667209 6659364985 4798167551 8461908866 6326870090 8631527041 6315788444 8533457824 0497335943 2716447341 7596026762 4642412614 5732460940 9395134939 1326720549 8605455112 4605759381 4225574583 2842640487 6358712866 0849472902 6206238687 6845690101 4552464042 7756125690 8808618917 3801799171 0466517642 8042154931 7280309774 0714391877 9520540265 1946849311 8743402166 9553905463 5719429821 0518596061 0436330992 8916767667 0254237938 3243898986 3765481090 7383586193 5143525004 4098858590 0832248318 9764252780 2760202083 0430047576 5236613052 3060855649 0441448557 6307631375 2926968154 5432828997 3604971974 9508334069 8835358437 9395142658 5050922899 3711943449 1882470108 1551793529 9834635351 0401678306 6880894004 2302862337 2516533032 8083002044 3575666502 7674433860 6400389801 7294634962 4388000773 9537327499 4940927774 0178638298 3893243648 0612367860 8021831467 8586581888 2646777771 4511931826 6530197311 6685863297 0866079391 9079231314 2462515211 3636997132 6527623986 5530750673 3310436364 2915355856 0030873614 9695707708 8813030752 8196652451 9300744578 0580580032 1477716136 5133530236 5574493076 4753213729 5804773745 6254764714 6788095182 5067959756 6395654977 4943968311 6027955156 3434479323 6846216254 2645473247 6559553140 8715235248 5446398038 4901317960 3741141530 7516389340 0088385535 9720531379 0633169863 4742042814 9021568664 8047353596 9818263285 7169492717 7790068680 9140206223 8923132753 6589515844 5552969107 9007565167 8769870311 5249131624 8593253058 6453847368 2133193030 9575865246 8076772194 2401315191 3230644041 2189920035 8194618213 8073679963 1641210595 0797099635 8620149790 7972451242 6322404502 6602294470 4916070532 3715012052 6570460838 0442855599 5508652337 2478343676 7532499269 7979055912 0573409350 6056297223 8844938384 9635436437 9240468763 3802314518 1375305979 6869946333 0912142841 3045357635 2228937262 6736118168 9799625996 1725094134 6000232190 0352174672 8948484666 7503575609 3947760169 6208667792 7085146706 9785248658 1052473629 2525798483 4250340002 0745533329 4638096586 1781529822 8507262649 5150035019 0283303069 0356017444 6307015200 8603134059 7086225182 1126663956 2609539627 2245036944 1117616439 2774799116 8219916902 0681188750 6485168436 0952381296 5991768995 1320546018 0514348331 7442973696 7116024759 7512786903 3037450716 8690325018 9478586230 4567450366 5752850557 1323604635 0938205439 1056224581 5072777698 4434869674 3725987449 2733873278 9529714423 5837728916 6343828698 0932493647 8579634870 3962737033 3625047589 3491820997 4170169053 6753449230 1387241220 6550767821 3181273852 0129599687 1898086779 3457341711 0554294279 7457215382 2276969785 6537957266 7563845783 1518318809 2743179969 9251234951 9942773824 4953452135 8163011294 1064578436 2899293003 7392032234 6815566632 9535946047 0971202829 3963267574 9662931177 8938574411 7198423367 2118733740 4685881608 6216146365 5392341615 6454074576 7550890801 8767938104 2310815784 1074795417 9527782578 8449197927 8248442035 3241804367 7265376352
• c₂= 328 9741084147 5020497417 0320329990 8015400379 2859703655 6402304057 7486241332 5223975241 3734858363 1942946443 7282506345 9544401441 9227862539 9984107781 0325486585 7436673377 3054121186 2259089365 9746483277 5723234555 5843094289 7277467878 9201483851 2690517165 1828573752 6001669422 9727505931 6201736386 2417930858 7434593153 0656029964 9183818898 5604333156 7809893785 5920077789 3318896875 2341990063 9858609599 9383048819 7939648070 3197502844 8090056080 6932049271 1328862129 3667833896 2619499076 2348581163 1510796171 0977728176 1168523163 9130761890 5461724464 3292491176 9669168544 0349090513 1387514139 7429671176 4333980477 2239305751 7426756342 8652048332 8917104743 3773601028 0178036084 3111723070 0547061612 9205882605 3355672048 0396920011 5813829561 7752658408 5665567563 7643196997 8872284508 9965475167 5800599395 7063551655 7071384780 9912689053 3127596375 6088289396 2522512930 7829516511 9619469350 6185117905 6624730020 2648207088 8471500062 7184665722 4755391510 6651269969 2748866426 3100684899 3610823940 8352977738 6325543628 9667648974 1544810417 2872948371 8869991423 8049791147 3821054973 4352795802 2594773761 1708970084 4694673414 4811442699 8957071457 6145375004 6719656198 0763827664 7521565116 8042529989 4753496901 4598076032 5287599516 6273706926 1637226809 2272990542 7723552867 4978200216 2844154418 7374931992 7302014151 4028018267 9112457039 4583308482 3023686079 5338306607 4690116341 8264380499 1639907427 2044705186 5110739528 2748869116 2579015956 7518535204 9587630497 0335656928 0084090872 4027663789 6721614189 7640040229 5128033602 0622844254 2268225758 9672503780 3387007505 7823738738 3279417174 8255543980 3963176919 2858323211 9088193054 7623493689 7595889712 3478416960 3479009148 2269727388 1019536135 1439375998 3567896406 1339867253 7625837232 6545266795 7710810540 3126593544 3868584082 2565096296 0571534861 1888716954 1338874271 4495251165 7989571212 2973172776 7164593757 4294596454 0570949461 7293042006 1915293763 3096715560 9227057050 9329199576 6758200350 4377748442 8591308891 1575982648 4806467106 1998633313 5437994679 4757719452 6039471359 0296939158 8697451976 8610620431 5538586134 9536820489 8579516589 9972843337 9121353395 7611245833 1567162898 4801772453 9841209775 2043804060 9857348269 1996743187 8398271077 9721839443 2170613394 1295538216 5858091103 5252556391 6746278794 4457883124 4718387192 9612376809 0126489222 7513633572 5464104452 8901625124 0651864999 7609890383 1348304948 6795557013 4255478440 7875271034 3202516903 6538926777 6634470396 4897423173 4231074533 3217740003 8772604102 5121145484 2148088636 3490209436 6339319701 2712944303 1801878562 7905066932 6472610920 3324690443 6476680744 1776864937 5183625250 7817921774 5714116039 8686163739 9312030366 1578785501 0954561128 8958055987 9784161277 3741296744 6182364441 1246547083 4140359045 3209353400 4513739959 9188163769 1735036003 0874433520 3037920022 5948503070 8530204823 3968216832 8788454591 5253280612 7293661194 0355463444 1250598891 0044645258 4977560591 3408317752 9506367576 8344145733 8912277699 2283120258 4084054810 6078865728

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