update.txt: Date of last update of the data files. M3status.txt: Data about factorization of M(p) - 2 for prime M(p). Mersenneplustwo: Other web site with data about factors of M(p) + 2. MMPstats.txt: Data about factorization of M(M(p)) for prime M(p). facntD.txt: Factor counts for completely factored M(n) for all n > 1. facntHU.txt: Factor counts for incompletely factored M(n), n > 1. facpriks.txt: List of files with all known factors for M(p) for primes p, M(p) not factored. results.pfk.split.aa.bz2: First file listed in facpriks.txt. Links to rest of the pieces. factoredM.txt: All known factors for M(n) for all M(n) completely factored. mersdata.zip: lowM.txt, DATABASE, DB.nf, primeM.txt, factoredM.txt, etc., zipped mersfmt.txt: Description of data format used in lowM.txt, factoredM.txt, etc. newsletters.html: All of George Woltman's GIMPS newsletters. primeM.txt: List of primes p for which M(p) is known to be prime. querylang.txt: Old draft of Mersenne data query language.
Mersenne Prime Project (GIMPS: George Woltman) Chris Caldwell's Prime numbers pages Chris Caldwell's Mersenne pages Ernst Mayer's programs ECMNET (Paul Zimmermann) ECPP and other info (Francois Morain) in French and in English. Cunningham Project (Paul Leyland) and a mirror. Machine-readable Cunningham Tables by Jeroen Demeyer.Factoring (small site, probably just starting, but has some links to other good sites).
"Mersenne numbers" are, by definition, numbers of the form:
2↑n - 1
That is, they are one less than some positive power of two.
A more common term is "Mersenne primes", which are Mersenne numbers that are also prime. Only 47 such primes are known, the 13 largest having been discovered since Nov. 1996 by:
The Mersenne Prime Project (otherwise known as "GIMPS": the Great Internet Mersenne Prime Search) is dedicated to finding more Mersenne primes. It is managed by George Woltman, who has some very fast software for Intel PCs running MSDOS/Windows, Linux, and several other Intel-based UNIX variants. George's fifteen Mersenne Newsletters, including the announcements of the then-new Mersenne primes and the bug in version 17, are here.
The record before these last discoveries was set using a Cray supercomputer in April 1996; that announcement is also on the web. Before that, the record often stood for a couple of years at a time.
More info on the records and prime numbers and Mersenne numbers in general can be found on Chris Caldwell's Prime numbers and Mersenne numbers web pages.
Ernst Mayer has written programs, available on his ftp site, to do Lucas-Lehmer tests and P-1 factoring; either could be the fastest program available except for George Woltman's hand-tuned Intel assembly code. Note that Ernst has made executables available as well as the source code; some Fortran90 run time libraries needed are also available. I'm told that Peter-Lawrence Montgomery's trial factoring program is also on Ernst's site.
Paul Zimmerman has written an ECM factoring program based on the Free Software Foundation's libgmp.a library; he also started ECMNET in January, 1998 to coordinate its usage and to keep track of new factors of record size discovered by ECM methods.
Francois Morain has developed an Elliptic Curve Primality Prover called ECPP; it and other interesting things are at his web site in French and English.
I maintain the mers package, it's README.html, and the beta version on my personal web pages . This package includes fftlucas, mersenne1, mersenne2, MacLucasUNIX, MacLucasFFTW, mersfacgmp, extract, contract, fftll, ecm3, merspm1, mmtrial, mers3p, and ecmfactor. Improvements are always in progress; new release and other announcements are sent to the Mersenne mailing list. Bug reports, fixes, porting changes, other suggestions, and so on should be emailed to me as noted in the README.html . A brief description of the input and output format that most of the mers package programs use is in mersfmt.txt .
My other primary contribution is keeping track of all factors of Mersenne numbers (for all exponents, composite or prime up to 2↑31 and for larger prime exponents, notably exponents that are themselves Mersenne primes), but note that composite factors and factors of smaller Mersenne numbers are not explicitly listed in the data files uploaded to my web site. As proved below, if a prime number p is a factor of M(n) for any n, then p is also a factor of any M(k*n) for any positive integer k.
The Cunningham Project's ftp site and a mirror at Oxford contains data for exponents, prime and composite, up to 1200. Paul Leyland, who manages the site, has added a file for prime exponent Mersenne numbers with exponents up to 10,000.
Jocelyn Larouche used to have a web page about the factoring status of Fermat numbers, which are of the form 2↑(2↑n) + 1. Note that these are a subset of the Mersenne numbers in a way, since 2↑(2↑(n+1)) - 1, a Mersenne number, is the product of a Fermat number and a Mersenne number by the usual difference of squares factorization.
As of 14 June 2008, M(821) = 2↑821 - 1 remains incompletely factored and M(1061) = 2↑1061 - 1 has no known prime factors. Trial factorization like that of the most of the mers package's factorers is effectively useless for completing such factorizations; much more sophisticated techniques and much more CPU time are required. The mers package's ecm3 factorer uses freeLIP's zfecm() function to try to factor Mersennes using the Elliptic Curve Method, however, and ECM, in ecm3, gmp-ecm, the ECMNET program, and ECM code in George Woltman's Prime95, have recently discovered numerous new prime factors up to 100 digits. P-1 factorers, notably P-1 code in George Woltman's Prime95 and a program of Ernst Mayer's, have also discovered several new factors recently. GMP-ECM, an ECM factorer that uses the GNU Multi-Precision math library, has also found many new factors of Mersenne numbers.
The DATABASE-format files mentioned below were generated by the contract program in the mers package; they include exponents greater than 2↑24 (16777216). The only released programs that can read such large exponents correctly are, I believe, the mers package's extract.c and rw.c.
The data files in the next paragraph are now in the mersdata.zip (a zip archive).
Prime exponent Mersenne numbers for which I have some factoring data but have no factor and no Lucas-Lehmer test are in DATABASE. Prime exponent Mersenne numbers for which at least one LL test has been run and for which I have some factoring data but no factor are in DB.nf. Both DATABASE and DB.nf are in George Woltman's (old!) DATABASE format, using the Lucas-Lehmer tested-once bit as a flag indicating the Mersenne is composite by at least one Lucas-Lehmer test. The exponents of known Mersenne primes are in primeM.txt ; the complete factorizations known to me are in factoredM.txt (the largest prime factor is almost always implied, as some of them are _very_ large), and the roughly 8 MB lowM.txt contains the known information for all other Mersenne numbers with exponents less than 200,000. The status of Mersenne numbers with a Mersenne prime exponent (that is, M(M(p)) where M(p) = 2↑p - 1 is a Mersenne prime) is in MMPstats.txt . The known factors of M(p) - 2, where M(p) is a Mersenne prime, are in M3status.txt . Most of the files mentioned in this paragraph use the same format that is mentioned above or slight variants of it.
Mersenneplustwo The Mersenneplustwo project is trying to factor M(p) + 2; the current data is presently kept at http://bearnol.is-a-geek.com/Mersenneplustwo/Mersenneplustwo.html .
There is a network server for GIMPS; see the Internet PrimeNet Server web pages, which include a FAQ (Frequently Asked Questions) file about IPS and GIMPS in general. Primenet uses HTTP (the primary World-Wide-Web/WWW protocol), which is allowed thru most firewalls, almost certainly including yours if you're reading this in your web browser directly from my site or its mirror here.
All of the factors of incompletely factored prime exponent Mersenne numbers that are known to me are now available in files listed in facpriks.txt . These files are _not_ in the same format to save space. Instead, each line contains p, the exponent (or nothing, if the exponent is the same as for the prior line), a comma, and the factor's k value; i.e., if the factor itself is 2*k*p + 1, then k is in the file rather than the factor. For example, M(641) has four small known prime factors; in the "mersfmt", they are:
M( 641 )C: 35897 M( 641 )C: 49999 M( 641 )C: 1173835097 M( 641 )C: 2401258891949526685926151441In the format used by the files listed in facpriks.txt, they are:
641,28 ,39 ,915628 ,1873056857994950613046920
That is, for example, 35897 = 2*641*28 + 1.
Here are links to the pieces. Combined, they would be over 30MB even squished like this, which is too large for me to upload regularly and too hard for some people to download. To recreate the single file, "bunzip -c results.pfk.split.??.bz2 > results.pfk" should work. If not, "bunzip results.pfk.split.??.bz2; cat results.pfk.split.?? > results.pfk" should, but that will require twice the disk space (since you will effectively have two unsquished copies while running cat).
results.pfk.split.aa.bz2 results.pfk.split.ab.bz2 results.pfk.split.ac.bz2 results.pfk.split.ad.bz2 results.pfk.split.ae.bz2 results.pfk.split.af.bz2 results.pfk.split.ag.bz2 results.pfk.split.ah.bz2 results.pfk.split.ai.bz2 results.pfk.split.aj.bz2 results.pfk.split.ak.bz2 results.pfk.split.al.bz2 results.pfk.split.am.bz2 results.pfk.split.an.bz2 results.pfk.split.ao.bz2 results.pfk.split.ap.bz2 results.pfk.split.aq.bz2 results.pfk.split.ar.bz2 results.pfk.split.as.bz2 results.pfk.split.at.bz2 results.pfk.split.au.bz2 results.pfk.split.av.bz2 results.pfk.split.aw.bz2 results.pfk.split.ax.bz2 results.pfk.split.ay.bz2 results.pfk.split.az.bz2
If the following interests you, then you should also like the Prime numbers and Mersenne numbers web pages maintained by Chris Caldwell.
These are my definitions, but I believe some, if not all, are in common use, at least on the Mersenne mailing list mentioned above.
A "Mersenne number" is one less than some postive integer power of 2. That is, the n'th Mersenne number, M(n), is 2↑n - 1 for all natural numbers n. Thus the first few Mersenne numbers are 1, 3, 7, 15, 31, 63, 127, and 255.
A "Mersenne prime" is a Mersenne number that is also prime. Note that this definition says nothing about the exponent being prime (but see below in the proofs). The first four are 3, 7, 31, and 127.
A "Mersenne composite" is a Mersenne number that has more than one prime factor. The first few are 15, 63, 255, 1023, 2047, and 4095. This says nothing about the exponent being composite.
A "prime-exponent Mersenne number" is a Mersenne number with a prime exponent. Thus, there is one for each prime number.
That is, if n, a prime, divides both M(p) and M(q) where p and q are also prime, then p = q.
First, note that all prime-exponent Mersenne numbers are odd since they are one less than a positive power of two.
Thus, n, a factor of a prime-exponent Mersenne, is also odd; n > 2.
Define s as the smallest natural number such that 2↑s = 1 (mod n).
M(p) = 2↑p - 1 = 0 (mod n).
2↑p = 1 (mod n).
If s > p, then s is not the smallest such natural number.
Thus, 1 <= s <= p.
Pick any natural number, t, larger than s, such that 2↑t = 1 (mod n).
Define u and v such that t = u*s + v and 0 <= v < s.
2↑t = 2↑(u*s + v) (mod n) = (2↑(s*u))*(2↑v) (mod n) = ((2↑s)↑u)*(2↑v) (mod n) = ((1)↑u)*(2↑v) (mod n) = 1*(2↑v) (mod n) 1 = (2↑v) (mod n)
If 1 <= v < s, then s is not the smallest such natural number.
So, v = 0 and t = u*s and t = 0 (mod s) for all natural numbers t such that t is larger than s and 2↑t = 1 (mod n).
If s < p, then p = 0 (mod s), but p is prime.
Thus, s >= p and s <= p, so s = p.
Note that the proof to this point applies equally to q where p is mentioned.
Thus, s = q and p = q.
For all natural numbers p and q: GCD(2↑p - 1, 2↑q - 1) = 2↑GCD(p, q) - 1
where the value of "GCD" is the greatest common divisor of its arguments.
Proof (incomplete only in case F):
Case A. If p = q: GCD(2↑p - 1, 2↑q - 1) = GCD(2↑p - 1, 2↑p - 1) = 2↑p - 1 = 2↑GCD(p, p) - 1 = 2↑GCD(p, q) - 1. Case B. If p != q and p and q are both prime: GCD(2↑p - 1, 2↑q - 1) = 1 (by Lemma 1) = 2↑1 - 1 = 2↑GCD(p, q) - 1. Case C. If GCD(p, q) = 1 and GCD(2↑p - 1, 2↑q - 1) = 1, Q.E.D. Case D. If GCD(p, q) = 1 and GCD(2↑p - 1, 2↑q - 1) > 1, then: 2↑GCD(p, q) - 1 = 1. Define g = GCD(2↑p - 1, 2↑q - 1). 2↑p - 1 = 2↑q - 1 = 0 (mod g). Define s as a prime factor of g. Since g is the GCD() of two odd numbers, s > 2. 2↑p - 1 = 2↑q - 1 = 0 (mod s). Similarly to Lemma 1: Calculate the smallest natural number e such that 2↑e - 1 = 0 (mod s). If e = 1, then 2↑e - 1 = 2↑1 - 1 = 1 (mod s). Thus, e > 1. Since 2↑p - 1 = 2↑q - 1 = 0 (mod s), e <= p and e <= q. 2↑e - 1 = 2↑p - 1 = 2↑q - 1 = 0 (mod s) 2↑e = 2↑p = 2↑q = 1 (mod s) Define p1, p2, q1, q2: p = p1*e + p2, q = q1*e + q2, 0 <= p2, q2 < e. Note that p1 and q1 are both > 0 since e is the smallest such natural. 2↑e = 2↑(e*p1 + p2) = 2↑(e*q1 + q2) = 1 (mod s) 2↑e = ((2↑e)↑p1)*(2↑p2) = ((2↑e)↑q1)*(2↑q2) = 1 (mod s) 2↑e = 2↑p2 = 2↑q2 = 1 (mod s) 2↑e - 1 = 2↑p2 - 1 = 2↑q2 - 1 = 0 (mod s) Since e is the smallest such natural, p2 = q2 = 0. p = p1*e, q = q1*e. GCD(p, q) >= e > 1 (contradiction). Case E. If GCD(p, q) > 1, then: Define e as GCD(p, q). p = q = 0 (mod e) Define pe: p = e*pe. 2↑e - 1 = 0 (mod 2↑e - 1) 2↑e = 1 (mod 2↑e - 1) 2↑p = 2↑(e*pe) (mod 2↑e - 1) = (2↑e)↑pe (mod 2↑e - 1) = 1↑pe (mod 2↑e - 1) = 1 (mod 2↑e - 1) 2↑p - 1 = 0 (mod 2↑e - 1) Similarly, 2↑q - 1 = 0 (mod 2↑e - 1) Therefore, GCD(2↑p - 1, 2↑q - 1) >= 2↑e - 1 = 2↑GCD(p, q) - 1. Further, GCD(2↑p - 1, 2↑q - 1) = 0 (mod 2↑e - 1). Case F. If GCD(2↑p - 1, 2↑q - 1) > 2↑e - 1, then: [only incomplete section, which is not needed to prove Lemma 3 since p = e there] p > e, q > e. Define g: GCD(2↑p - 1, 2↑q - 1) = g*(2↑e - 1). Since 2↑p - 1, 2↑q - 1, and 2↑e - 1 are odd, so is g. Thus, g > 2.
That is, if M(n) = 2↑n - 1 is prime, then n is prime.
Proof: Suppose M(n) is prime for some composite number n. Find a prime factor of n and call it p. By Knuth's GCD Lemma: GCD(2↑p - 1, 2↑n - 1) = 2↑GCD(p, n) - 1. GCD(2↑p - 1, M(n)) = 2↑p - 1. M(n) > 2↑p - 1 since n > p. 2↑p - 1 is a factor of M(n). M(n) is not prime, contradicting part of our assumption. Therefore, either M(n) is not prime or n is not composite or both. If n = 1, then M(n) = 2↑1 - 1 = 1, which is not prime. Therefore, either M(n) is not prime, n is prime, or both. Therefore, if M(n) is prime, then n is prime.
If M(p) = 0 (mod n) for a prime p > 2 and natural n, then: n = 1 (mod 2*p). n = 1 or n = 7 (mod 8). This includes M(p) itself: M(p) = 1 (mod 2*p) M(p) = 7 (mod 8) If M(p) = 0 (mod q) for some prime q, then: Define c: M(p) = c*q Define k: M(p) = 2*p*k + 1 Define h: c = 2*p*h + 1 Define j: q = 2*p*j + 1 M(p) = 2*p*k + 1 = (2*p*h + 1)*(2*p*j + 1) 2*p*k = 4*p↑2*h*j + 2*p*(h + j) k = 2*p*h*j + h + j Case A. q = 1 (mod 8) Define r: q = 8*r + 1 q = 8*r + 1 = 2*p*j + 1 4*r = p*j j = 0 (mod 4) Define s: j = 4*s q = 8*p*s + 1 k = 8*p*h*s + h + 4*s M(p) = c*q 7 = c*1 (mod 8) 2*p*h + 1 = 7 (mod 8) p*h = 3 (mod 4) Case B. p = 1 (mod 4) h = 3 (mod 4) k = 3 (mod 4) Case C. p = 3 (mod 4) h = 1 (mod 4) k = 1 (mod 4) Case D. q = 7 (mod 8) M(p) = c*q 7 = c*7 (mod 8) c = 2*p*h + 1 = 1 (mod 8) h = 0 (mod 4) Define t: h = 4*t c = 8*p*t + 1 k = 2*p*4*t*j + 4*t + j = 8*p*t*j + 4*t + j q = 2*p*j + 1 = 7 (mod 8) p*j = 3 (mod 4) Case E. p = 1 (mod 4) j = 3 (mod 4) k = 3 (mod 4) Case F. p = 3 (mod 4) j = 1 (mod 4) k = 1 (mod 4)
Please email me with other proofs, related URLs, proofs you would like to see, and so on. I do not always have time to reply quickly or add new proofs here, but I will update this and other pages as I have time.
That is, if p is prime, 2↑p - 1 is not a multiple of any square; there exists no prime n such that 2↑p - 1 = 0 (mod n↑2).
Some consider this to be more of an "open question", implying that "we" are unsure of the answer, rather than a "conjecture", which implies "we" cannot prove it but believe it to be true.
Note that for 2↑c - 1 where c is composite, many square factors are known, including 2↑6 - 1 = 63 = 3*3*7.
I have proved that if 2↑p - 1 is divisible by q↑2 for some prime q, then 2↑(q - 1) - 1 is also divisible by q↑2 (the proof uses Knuth's Lemma and a "trick" I first saw on the Mersenne mailing list in a message from Yuri Sorkin attempting to prove this conjecture). I'm informed that only two such primes exist below 4*10↑12 and I have verified that neither divides a Mersenne number with a prime exponent.
On the other hand, I suspect this is a known result, as primes of that form are known as Wieferich primes after someone in the early 1900's.
(incomplete) Proof: For two primes, p and q:
Courtesy of Yuri Sorkin on the Mersenne mailing list: 2↑(q*(q - 1)) - 1 = (2↑(q - 1) - 1)*(1 + 2↑(q - 1) + 2↑(2*(q - 1)) + ... 2↑((q - 1)*(q - 1))). 2↑(q - 1) - 1 = 0 (mod q) by Fermat's Little Theorem. Each term in the second factor is 1 (mod q) by Fermat's Little Theorem and there are q terms. Thus, 2↑(q*(q - 1)) - 1 = 0 (mod q↑2). Suppose 2↑p - 1 = 0 (mod q↑2) (Conjecture A). Then GCD(2↑p - 1, 2↑(q*(q - 1)) - 1) >= q↑2. By Knuth's GCD Lemma: GCD(2↑p - 1, 2↑(q*(q - 1)) - 1) = 2↑GCD(p, q*(q - 1)) - 1. 2↑GCD(p, q*(q - 1)) - 1 >= q↑2. GCD(p, q*(q - 1)) > 1. But p and q are prime, so p = q or q = 1 (mod 2*p). Case A: If p = q, then: By Fermat's Little Theorem, 2↑p - 2 = 0 (mod p). 2↑p - 1 = 1 (mod p). But 2↑p - 1 = 0 (mod q↑2). 2↑p - 1 = 0 (mod p↑2) since p = q. 2↑p - 1 can't be both 0 and 1 (mod p); contradiction. Thus, q = 1 (mod 2*p). GCD(2↑p - 1, 2↑(q - 1) - 1) = 2↑GCD(p, q - 1) - 1 = 2↑p - 1. 2↑(q - 1) - 1 = 0 (mod 2↑p - 1). 2↑(q - 1) - 1 = 0 (mod q↑2). [only two such q's exist below 4*10↑12; neither divides a prime-exponent Mersenne.] New section (2006 April 11): From section just above: q = 1 (mod 2*p) Introduce r such that q = 2*p*r + 1. Introduce u such that 2↑p - 1 = u*q↑2. 2↑p - 1 = u*(2*p*r + 1)↑2. 2↑p - 1 = u*(4*p*p*r*r + 4*p*r + 1). 2↑p - 1 = 4*p*p*r*r*u + 4*p*r*u + u. Since q is a prime factor of M(p), q is either 1 or 7 mod 8. 2*p*r + 1 == 1 or 7 mod 8. (2*p*r + 1)↑2 == 1 mod 8. Since M(p) is 7 mod 8, u is also 7 mod 8. 2*p*r + 1 == 1 or 7 mod 8. 2*p*r == 0 or 6 mod 8. p*r == 0 or 3 mod 4. r == 0 mod 4 or p*r == 3 mod 4. Back to (much) older text: Introduce t such that: 2↑(q - 1) - 1 = t*q↑2. Case B. If 2↑(t - 1) - 1 = 0 (mod t), then: 2↑(q - 1) - 1 = 0 = 2↑(t - 1) - 1 (mod t). By Knuth's GCD Lemma: GCD(2↑(q - 1) - 1, 2↑(t - 1) - 1) = 2↑GCD(q - 1, t - 1) - 1. 2↑GCD(q - 1, t - 1) - 1 >= t. 2↑GCD(q - 1, t - 1) > t. GCD(q - 1, t - 1) > log2(t) = log2((2↑(q - 1) - 1)/q↑2). GCD(q - 1, t - 1) > log2(2↑(q - 1) - 1) - 2*log2(q). GCD(q - 1, t - 1) + 2*log2(q) > log2(2↑(q - 1) - 1). GCD(q - 1, t - 1) + 2*log2(q) > log2(2↑(q - 1)) - 1. GCD(q - 1, t - 1) + 2*log2(q) + 1 > log2(2↑(q - 1)). GCD(q - 1, t - 1) + 2*log2(q) + 1 > q - 1. GCD(q - 1, t - 1) + 2*log2(q) + 2 > q. Case C. If t - 1 = 0 (mod (q - 1)), then: GCD(q - 1, t - 1) = q - 1. q - 1 + 2*log2(q) + 2 > q, obviously satisfied. Introduce s such that: t - 1 = s*(q - 1). t = s*(q - 1) + 1. 2↑(q - 1) - 1 = t*q↑2 = (s*(q - 1) + 1)*q↑2. 2↑(q - 1) - 1 = s*q↑2*(q - 1) + q↑2. 2↑(q - 1) - 1 = s*q↑3 - s*q↑2 + q↑2. 2↑(q - 1) - 2 = s*q↑3 - s*q↑2 + q↑2 - 1. 2↑(q - 1) - 2 = s*q↑2*(q - 1) + (q + 1)*(q - 1). 2↑(q - 1) - 2 = (s*q↑2 + q + 1)*(q - 1). Note that s must be odd (s even quickly leads to a contradiction). [incomplete] [incomplete] [incomplete] I am confident that Case B is impossible, but haven't a clue how to continue after that. Once Case C is proven impossible, I'm pretty sure proving Case B impossible will be easy; log2(4*10↑12) is less than 42.
As far as I know, I was the first to suggest this conjecture, via the Mersenne mailing list soon after it started.
Update (4/26/1997): Jon Grantham Please email me with
comments, questions, answers, ideas, etc., including letting me know
what isn't here, or that a link, more text, or graphics, should be
here. What did you look for and not find? Thanks!
my index page
n|2↑1931-1, and 1931 is prime.
3↑n=3 mod n, so it's a base 3 pseudoprime.
I was thinking of the 3↑(n - 1) == 1 (mod n) test, but that definition
of pseudo-prime also includes 193949641, so ...
Help save the world!
Please email me with comments, questions, answers, ideas, etc., including letting me know what isn't here, or that a link, more text, or graphics, should be here. What did you look for and not find? Thanks!
my index page