Primality Certificate for (4733^2897-1)/4732 | ||
| Andy Steward | 10,644 digits | 14 August 2008 |
|---|---|---|
| Originally by A.A.D.Steward 2008 | ||
This certificate uses a theorem of Pocklington and Lehmer to prove an integer N prime by making use of a partial prime factorization of N-1.
As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 50.973937% factorization of N-1:
| From | Factorisation |
|---|---|
| 4733 | 4733 |
| Φ2 | 2 · 3 · 3 · 263 |
| Φ4 | 2 · 5 · 661 · 3389 |
| Φ8 | 2 · 250908874430761 |
| Φ16 | 2 · 17 · 7393 · 36387937 · 27531823604344193 |
| Φ181 | 2897 · 10499 · 464447 · 55086468893 · c638 |
| Φ362 | 1087 · 1356053 · 13217704553 · 48242424191233539851 · c623 |
| Φ724 | c1324 |
| Φ1448 | 198377 · 1245281 · c2635 |
| Φ2896 | 69860209 · 375860257 · p5276 |
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/2 :
| 598839 0972006812 0570958437 1282688496 6346417792 7834122917 9451781061 8212116095 8777141992 3321432482 3343326021 6852261403 5725404865 0371704845 3891759282 6636929852 9322604507 8787607334 5091948181 5656486313 8444918261 2341161890 9088690914 9665772808 5621550768 0521954765 2280603490 7967528454 2688057864 3310719939 8472783077 7559130696 1187557333 8017977213 4458776783 5924634485 2906163172 1131577802 5047363028 2342622453 7397946650 0289201294 1431223388 5462117365 7645767076 9172765241 3034803965 5325981859 9481595672 5437881455 6550906735 8752642008 3993996100 9080985913 4047216772 3168941023 9987694148 2938452738 6665323205 4561755111 6375211149 8308871209 9245551312 3496296860 4510004204 2019038501 8708380822 7839882496 0164891781 8442013914 6271318278 9491202113 6989556718 3185880184 6608917606 2300846320 9644416223 1295882258 7987005409 5280217101 0873473248 2593678710 8894194466 6896026384 1294631072 5457318193 6347133536 8026402482 1703004246 7186788418 4820990389 9634931359 0306409097 2974254124 9123528238 9766149924 4671510560 9263789657 2851505734 5450929658 4908067439 5514781465 5412487299 8793271942 9568903772 0347457289 6723129402 6798935511 6124779532 0756704481 6661178731 5349029221 2116088173 7793983345 9539898712 8299847046 0462112830 8381709116 1380394701 2713176348 5238018048 9681078493 5220297363 6898100439 3199352839 3950425364 3552672623 7361540268 6863620266 8275887843 9638570018 6688632068 6756777467 7751958203 1712242871 0669014827 1351016687 5869093137 4943354757 7542798665 5838243071 6246175712 7545697022 5441048059 5281680681 4486248948 5344198751 4411421630 3822963491 9656383837 5349196272 0089785171 5991302321 8849855584 7557835580 0493550537 1397566936 5472000872 5009520176 4492640992 2853541257 9667121609 7118138603 2888795482 2869161754 6146525707 0751661315 3980624221 7250732891 2029610461 0838780820 5479323881 0222865207 7461702956 3759413033 9373282962 1043441735 5576587275 9359417811 5228793231 3327757592 6870329690 8026981849 5082222367 3108899947 1428716713 9027038095 1386398870 9271126360 9096025498 3999382454 7273736699 2429362278 6627171771 4216311761 6021826073 2113555906 2239865709 1126359891 2769033915 9723252847 0793075388 6672325433 3417399428 6601035698 0946599265 8270830137 1954624778 1507308875 5141017466 8709329718 6716849809 9364354561 5606055395 8004449818 4703086907 6158743284 5007942889 3770053842 5953373516 6902426591 6308566621 1190126814 0266520243 4039688250 9480068104 6905527824 6386356869 6465858158 3167012851 6874646281 8519527541 0490570045 0866403555 1358795328 9233487972 0949630818 5866549901 6172075112 8923382636 8078816040 6081337623 4601614312 9775562816 1933960992 6073438552 7996736819 0734327315 8558931926 6056026649 9696495903 4667516457 6830713397 9880826775 8158893866 3653318157 6842748590 7766822772 4350657885 9184250750 7038608319 0400328769 2493324071 5337731414 3794519926 3250861993 5558531180 6189691434 0640497187 1580311546 6742604547 8715720912 0452980555 0735542291 5963222656 9808628220 0371978140 7834694523 3644243944 9534199259 5794827028 3649321876 9840545872 3093557371 4047522962 8990563445 2808039470 1787663285 3795600858 6012790311 1445730956 1070574624 7678511332 3103992795 1396893143 9125410330 9626256627 6011470136 5995591770 8398896312 5067509520 5880616248 2028388024 6978860322 8984023942 8089922794 9296352044 9846932869 0438605790 7607588331 2885692347 9309911282 3796770099 9281584717 3921923685 4520299359 2646753607 8032807491 2285450424 5322075647 8385675278 9348219828 8788176716 1601534617 2994172037 6700288673 0725833646 0465742919 0792462666 5906550074 2913695987 9278512388 3879400541 6179885478 4227040325 3123634167 6334584409 3943721234 3437246030 0794910384 9597838880 4488078969 9093547943 2798319767 7290181678 6799742427 1122606142 8685052101 9059472607 9438108639 8901944638 0633555288 5329005982 1089364787 7583842471 1203576897 5984181442 3121125022 5047266957 2287987734 3219640905 3067604579 4551659980 8421506717 8121754972 9274379628 0264179199 8500691838 5012444944 4986018787 2515375811 0217294082 0440811778 2784283519 9042300619 7496499957 4862859732 8766401267 6439101057 9689658341 8309347401 0320771957 7017903308 3684676085 5859691285 0747848702 8560378388 6919504223 7582501215 9690641513 2097444379 0035241405 8103429257 8077302153 3101182049 9935587506 5849492784 8759204758 3631236618 0353607800 1303486813 6914953359 7737970698 8713868954 5849129805 5393955891 5638466391 8602261529 9112264490 0934881956 6520420651 3531972930 5569907733 5060980955 2832281021 9125239596 1241532623 2642481860 3176182425 4720518016 1779957669 6999245827 7981398751 1453865188 5456068065 0297717750 5682642669 9758451340 7000492648 4322901991 0988695317 0084258341 4729088631 9426826016 6315196249 5557270043 4371114195 0482126837 3638268676 9691858456 5333378656 6254312766 0699919559 7399800659 9294240498 7869474924 7220338814 6339623615 4335561023 0743597098 3328393196 5907536215 0032987055 0466875300 1634572574 8098859020 3384582290 7920320400 7521189747 1215006901 8681727036 1234539598 1433607030 5451601692 7720862902 6844946990 4664584885 2215888178 8484474931 8050009383 6254456723 0050770620 5785238246 2057464705 3465791040 0595418696 9882233442 1177183623 0734125725 7168228401 3633855835 1914388188 4941616274 9117698153 3911350939 5678479614 3618280598 8478340987 9887511544 3459454685 3731972994 0515258253 2309427986 9438048792 1134290497 9265027098 5338405633 1299786133 0479587276 4856450837 2403852341 3271119521 4711225915 7300036601 9238629430 8761871552 9590985859 6892334817 8279643278 1263619965 7722375656 4043908352 2134814144 4028936698 9519201784 4937063138 2367197911 1458183223 8057633069 2452800425 7123856502 4285287034 4244509722 6791292966 1158798426 5641063287 9193845487 7570924977 |
| 4824242419 1233539851 |
| 2753182 3604344193 |
| 25090 8874430761 |
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) = 50.044182%
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 = 7 suffices.
Pocklington's Theorem states that the above information is sufficient to prove that any factor of N is ≡ 1 (mod F).
If N is composed of two (not necessarily prime) factors, let them be a·F+1 and b·F+1 (with a, b > 0). This would imply that N > a·b·F2 > F2 > N, so N must be prime.