 mersenneforum.org Largest nonmersenne prime
 Register FAQ Search Today's Posts Mark Forums Read  2020-08-25, 16:04   #34
chris2be8

Sep 2009

35748 Posts Quote:
 Originally Posted by Unregistered Actually, is there a proof that there are infinite non-Mersenne primes?
Here's another proof:

There are infinitely many primes of form 3n+2, none of which are Mersenne primes.

Lemma 1: No Mersenne numbers are of form 3n+2.

2^n is never divisible by 3 so 2^n mod 3 is 1 or 2 (1 if n is even, 2 if n is odd).

Hence 2^n-1 mod 3 is 0 or 1.

Lemma 2: There are infinitely many primes of form 3n+2.

Proof by contradiction. Assume there are a finite number, p1, p2, ... pn.

Contruct M = 3*p1*p2*...*pn-1.

M is not divisible by any of p1, p2, ... pn because of the -1 and M mod 3 will be 2.

The product of 2 numbers of the form 3n+1 will also be of form 3n+1 so any number of form 3n+2 must have at least 1 prime factor of form 3n+2 (possibly itself).

So M must have a prime factor of form 3n+2 that is not in p1, p2, ... pn. Hence there are an infinite number of such primes, none being Mersenne primes.

Chris   2020-08-25, 17:04 #35 CRGreathouse   Aug 2006 17·349 Posts Another different proof (a 'sledgehammer proof'): There are x/log x + O(x/log^2 x) primes up to x by the Prime Number Theorem. There are log(x)/log(2) + O(1) Mersenne numbers up to x, and hence O(log x) Mersenne primes up to x. Hence there are x/log x + O(x/log^2 x) non-Mersenne primes up to x.   2020-08-26, 08:08 #36 retina Undefined   "The unspeakable one" Jun 2006 My evil lair 16BF16 Posts Another proof. Yitang Zhang showed that there are an infinite number of primes separated by less than 10,000,000. The current best known proven bound has been improved to 246. So If we choose any pair of two large primes separated by 246, if one of them is a Mersenne number, then the other one won't be a Mersenne number. Last fiddled with by retina on 2020-08-26 at 08:23   2020-09-07, 00:53 #37 Dr Sardonicus   Feb 2017 Nowhere 3×5×239 Posts Adding to xilman's note that the Fermat numbers are pairwise relatively prime, I note that Lucas proved that for k > 1, every prime factor of the Fermat number Fk = 2^(2k) + 1 is congruent to 1 modulo 2k+2. Taking k = Mp - 2 for p > 2, we have that the smallest prime factor of FM_p - 2 is greater than Mp (and, being congruent to 1 (mod 4), is not a Mersenne number). We can thus (in theory, if not in practice) easily specify, for each Mp, p > 2, a non-Mersenne prime greater than Mp, and these primes will be different for different p. For example, the smallest prime factor of FM_82589933 - 2 is a non-Mersenne prime which is greater than M82589933.   2020-09-07, 02:44   #38
CRGreathouse

Aug 2006

17·349 Posts Quote:
 Originally Posted by Dr Sardonicus Adding to xilman's note that the Fermat numbers are pairwise relatively prime, I note that Lucas proved that for k > 1, every prime factor of the Fermat number Fk = 2^(2k) + 1 is congruent to 1 modulo 2k+2. Taking k = Mp - 2 for p > 2, we have that the smallest prime factor of FM_p - 2 is greater than Mp (and, being congruent to 1 (mod 4), is not a Mersenne number). We can thus (in theory, if not in practice) easily specify, for each Mp, p > 2, a non-Mersenne prime greater than Mp, and these primes will be different for different p. For example, the smallest prime factor of FM_82589933 - 2 is a non-Mersenne prime which is greater than M82589933.
Alternate construction: by Bertrand's postulate (proven by Chebyshev, re-proven by Ramanujan and many others), there is a prime between every two Mersenne numbers.   2020-09-07, 12:45   #39
Dr Sardonicus

Feb 2017
Nowhere

3·5·239 Posts Quote:
 Originally Posted by CRGreathouse Alternate construction: by Bertrand's postulate (proven by Chebyshev, re-proven by Ramanujan and many others), there is a prime between every two Mersenne numbers.
So "the next prime after Mp" specifies a non-Mersenne prime greater than Mp, uniquely determined by p.

OK, Pari-GP, give me nextprime(2^82589933 - 1). Huh, I've never seen an error message like that before:  Being prone to mentally transposing things inadvertently, I realized that you can also ask about the "largest Mersenne non-prime," i.e. the largest Mp with prime exponent for which a proper factor is known.

The largest "Mersenne non-prime" I know of for sure is with p = 2618163402417 · 2^1290000 - 1, the largest known Sophie Germain prime. Since p is congruent to 3 (mod 4), q = 2*p + 1 is a prime congruent to 7 (mod 8), whence 2(q-1)/2 == 1 (mod q), i.e. q divides Mp.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 sudaprime Miscellaneous Math 11 2018-02-05 08:10 Unregistered Information & Answers 24 2008-12-13 08:13 amcfarlane Math 6 2004-12-26 23:15 wfgarnett3 Lounge 7 2002-11-25 06:34

All times are UTC. The time now is 07:21.

Sat Oct 31 07:21:25 UTC 2020 up 51 days, 4:32, 2 users, load averages: 1.82, 1.76, 1.68