Primality Certificate for (9199^2267-1)/9198 | ||
| Andy Steward | 8,982 digits | 13 August 2009 |
|---|---|---|
| Originally by A.A.D.Steward 2009 | ||
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.531456% factorization of N-1:
| From | Factorisation |
|---|---|
| 9199 | 9199 |
| Φ2 | 2 · 2 · 2 · 2 · 5 · 5 · 23 |
| Φ11 | 89 · 2496026522394332951 · 19535035274655779759 |
| Φ22 | 3719 · 3917 · 255663060137 · 1164960626643332520761 |
| Φ103 | c405 |
| Φ206 | 2473 · 5563 · 97086383957 · p387 |
| Φ1133 | 2267 · p4040 |
| Φ2266 | 13597 · c4039 |
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 :
| 4570171537 9817419456 3416797434 6520381982 5781435731 6960133760 5055108088 9110861981 1599163832 4068697079 7540017590 9099065641 9873268337 9555819363 9994709868 0344255673 4004457838 7884234236 8044010134 3778498083 5719715402 0717212260 3826851442 0345072352 7535006495 2759992812 8290272481 6047064952 2678162589 0683360430 8432043488 5544550523 0175270790 1762760759 3540128475 9570758996 8075796320 6442368312 4969104914 4654067718 2145690954 7510724801 6076328319 9779976333 1131850252 0903729887 3035226922 0844012721 4852396977 3441368005 6053737052 6264630789 5349345368 3398713248 8413656670 9058505099 2656540245 5573253193 8516551536 1576822200 3430675160 4449887487 0511937520 2541343025 5048963647 8497888071 3857040865 7425785045 5058579958 3940756824 0866378680 4391432864 1289289418 9204305500 8916036848 5679372262 5510128913 7164524326 7719461952 7617590852 3538724763 6157863959 5738328744 1975618432 4822037531 2028349881 8277345340 2138687944 6200399923 6984892551 8368519353 5125901688 7732691961 0686459633 7241583304 4812768999 2003185626 4723747523 4021026451 4044231862 4515711443 1933130040 6178127806 8588637552 1935596600 3139214342 2498938980 7517779864 8317097539 4961187060 7127903429 0538617783 3111137671 1226230913 2015049436 8233461761 9808622730 2172683181 4071872968 9013363846 6064302791 7342185175 4270321598 5431590282 5386198188 4001334676 6916038606 5622560786 0747997595 5922368451 1187163901 1146247352 6441695275 8428825573 9505707964 8660274040 8400172438 7440048726 7559758009 8147976387 7233140085 4544452791 4824260506 5729323198 5420133547 4535381422 4072198536 1975608438 5640981842 6831236963 1391166398 9924711184 5611491155 7267967903 5327509139 2218901658 2502658099 4318518635 4488596514 0086268824 6037637222 7354193339 4338927253 3370310482 5520469726 2552785956 7563308256 1981642358 4777475898 2455308808 5988716376 1918223942 4391448615 1677666383 4972735035 4870772078 7083996908 0093451021 5576957458 3362775233 2662131076 5711522734 1174338666 2471340386 7324588007 0009349995 0353113215 2544159715 0760421696 3189117608 1611236744 6658715547 5476543412 3722246994 8527275874 2476916704 0382512654 4931010760 4225903553 4851502751 2316934089 1839236197 1505236462 7278711150 9821762792 1214317101 5958276180 7553197323 3306086319 4929017322 0630389878 2142704486 7393750439 2912770653 0805440419 6305968710 2973296062 3449095486 8405530748 2447876146 0834170677 4075341701 0362961042 0558317392 4817813583 7631456325 1003464127 9413353240 4968706671 4882089186 1269844529 4824128928 9696502048 3389698412 5393136230 1255884239 4406600794 4629218540 9176793320 7320563531 0095370705 9415631272 5534896521 9539343020 9223854410 6620729563 6191842708 1617813917 7691361695 6431729039 1515091039 3035507395 1861710361 8605779117 8278456504 6085759772 7702108969 2884763440 4467664736 7025017856 4148200434 7775226538 5572104744 7687747741 9375889548 9963487186 4752078805 2456742385 3472244984 8877689453 0439124493 6212469462 5455792611 8935358715 7890392485 7196247834 8152998235 1183252908 1326297666 2789407841 4481646875 7707413262 0900990069 6925459981 5835898538 3953639800 4122038055 0961719260 5655647866 3403485895 6552248663 5332588479 6975866667 9382432632 2405069304 9277135026 3119962897 7572454125 3028546696 7483756114 7178177364 2053734329 3838311920 5626151863 1931611900 8670573350 5744628012 6234211404 5995362485 5771475102 1633765678 2023578367 1510832720 3272783733 5509283538 3128628456 6657796707 0374379795 1354161378 1740955162 5088907158 0877696370 2293496001 4852458824 0551989945 8696757260 3202463343 3774275438 9556573087 1470826058 4589024943 2095296573 6625140890 4293918995 0501158338 2589306279 7217661039 8706446429 0836270719 0998076908 2581793155 1124713001 7014304408 2367249601 7376413187 6455108205 7788326635 9542584664 6249520189 7800717097 6384601774 9723477337 4693432325 9493176234 5546746662 3241086995 6651272019 0026427405 0358926080 5004642897 6890638250 7167767828 0533975130 6808808120 3577523100 6409938561 1599687772 7806341557 3242274191 5841879603 7776365298 4331534742 7099667977 8011501562 9145085777 2983087841 2303011048 3046089276 7780437756 2263381056 8956740266 0974264409 3637996835 2579974797 4436771949 1907208910 2840745733 2693100672 5907336205 0003576372 1383360341 5507024986 1695171852 6170486072 6281151162 1641214423 5240932808 1218634960 3810319714 6839553064 0693265821 7525857246 2072331070 9362223603 |
| 1499009 5955699481 9123246339 4165448118 1280001066 7541334535 3370613917 8996239672 3214610329 6734110093 3992827780 4066803710 6221776874 2154357172 3232041840 3668607787 5431852271 5422122905 0829254933 9794547793 2509295087 7552961057 7901348487 9622392339 4376739326 8853129330 0295454099 3961851363 6074970031 7367993486 7272773964 3707870797 0616090774 0285473542 2348363058 3936400843 6601398369 0036215734 2717622521 |
| 11 6496062664 3332520761 |
| 1953503527 4655779759 |
| 249602652 2394332951 |
| 25 5663060137 |
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.056555%
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 = 3 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.