mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2020-08-25, 16:04   #34
chris2be8
 
chris2be8's Avatar
 
Sep 2009

1,913 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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
chris2be8 is offline   Reply With Quote
Old 2020-08-25, 17:04   #35
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

172A16 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2020-08-26, 08:08   #36
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

16A016 Posts
Default

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
retina is online now   Reply With Quote
Old 2020-09-07, 00:53   #37
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×5×7×17 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-09-07, 02:44   #38
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

593010 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2020-09-07, 12:45   #39
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

DF216 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
probable largest prime. sudaprime Miscellaneous Math 11 2018-02-05 08:10
NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 561 2013-03-29 16:55
Largest known prime Unregistered Information & Answers 24 2008-12-13 08:13
Largest 64 bit prime? amcfarlane Math 6 2004-12-26 23:15
need Pentium 4s for 5th largest prime search (largest proth) 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.