Primality Certificate for (2^4423-1)/1
Chris Nash
Marcel Martin
Primality Certificate for (2^4423-1)/1 | ||
| Andy Steward | 1,332 digits | 03 April 2000 |
|---|---|---|
| Originally by Hurwitz 1961 | ||
| Thanks to: Chris Nash |
Thanks to: Marcel Martin | |
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 60.644917% factorization of N-1:
| From | Factorisation |
|---|---|
| 2 | 2 |
| Φ2 | 3 |
| Φ3 | 7 |
| Φ6 | 3 |
| Φ11 | 23 · 89 |
| Φ22 | 683 |
| Φ33 | 599479 |
| Φ66 | 67 · 20857 |
| Φ67 | 193707721 · 761838257287 |
| Φ134 | 7327657 · 6713103182899 |
| Φ201 | 1609 · 22111 · p32 |
| Φ402 | 2011 · 9649 · 6324667 · 59151549118532676874448563 |
| Φ737 | 4423 · 12148690313 · 5157050159173695487 · 17904041241938148871927 · 1963672214729590922916323781834466879 · p108 |
| Φ1474 | 3556355492892313 · c184 |
| Φ2211 | 39799 · 12371522263 · p383 |
| Φ4422 | 67 · 13267 · 283009 · 361859649163 · 224134035919267 · 17153597302151518561 · c341 |
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 :
| 813 0643412643 5390369376 3080174268 1646733858 9074376606 9534508877 3865994912 2190481971 2929603010 0112862826 9985908910 2507335714 8438092768 2097166969 4836366984 0186470539 3738719321 4155259088 7137583064 3489767976 9841335382 7425700619 7857712319 1036292062 4590749660 1803359738 4789942417 3151999769 5185318284 0512546560 0803304801 5655006605 2032585973 6591957971 2675545019 3666989236 9742943909 5730189943 |
| 24564698 1125691497 6733246682 6553633404 4341262452 1776978646 9523368617 3498977525 8775403622 9884961406 8695233671 |
| 1963672 2147295909 2291632378 1834466879 |
| 87 4494233974 2585794267 8833145441 |
| 591515 4911853267 6874448563 |
| 179 0404124193 8148871927 |
| 1715359730 2151518561 |
| 515705015 9173695487 |
| 355635 5492892313 |
| 22413 4035919267 |
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.651964%
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.