mersenneforum.org Largest nonmersenne prime
 Register FAQ Search Today's Posts Mark Forums Read

2020-08-25, 16:04   #34
chris2be8

Sep 2009

1,913 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 172A16 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 16A016 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 2×3×5×7×17 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

593010 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

DF216 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post sudaprime Miscellaneous Math 11 2018-02-05 08:10 dabaichi News 561 2013-03-29 16:55 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 03:39.

Sat Oct 24 03:39:56 UTC 2020 up 44 days, 50 mins, 1 user, load averages: 1.28, 1.40, 1.39