# Mersenne Primes: Identifying & Eliminating Non-Prime Numbers

• arydberg
In summary, Mersenne numbers are generated with the formula x = 2^n - 1, where n is a natural number. Some of these numbers are prime while others are not. A sieve can be used to eliminate many non-prime Mersenne numbers, but it does not work for all numbers. The next prime Mersenne number after 11 is 2047. However, there is a theorem that states if 2^n - 1 is a prime, then n must also be a prime. This means that the sieve method can only eliminate Mersenne numbers with a composite n. Additionally, it can be proven that x^(2*n) - 1 has a factor of x-1 for any
arydberg
Following is a list of 39 Mersenne numbers. Some are prime and some are not. These are generated with x =( 2^n) -1. Many of the largest primes known are Mersenne primes.

I would like to point out that a sieve may be used to block out many non prime Mersenne numbers.

For example for n = 2 x = 3 but on closer inspection every even value of n other than n = 2 is non prime furthermore they are all divisible by 3, Thus we can cross out n=4, n=6, … up to n=38.

Also starting at n=3 and x = 7 we find that every third number larger than 3 is divisible by 7 so we could cross out n = 6, n=9, n=12 … up to n = 39.

Now let's move to n=5 or x = 31. now we can cross out every fifth number larger than n=5 as they are all divisible by 31

if we move to n=7 and x = 127 we find that every 7th number larger than 7 is divisible by 127 and can be crossed out.

11 should be crossed off as 2047 is not prime

My question is does this go on forever and can we use it to delete many Mersenne numbers as non primes.

The next prime is 11
n 2^n - 1
n = 1 x = 1
n = 2 x = 3
n = 3 x = 7
n = 4 x = 15
n = 5 x = 31
n = 6 x = 63
n = 7 x = 127
n = 8 x = 255
n = 9 x = 511
n = 10 x = 1023
n = 11 x = 2047
n = 12 x = 4095
n = 13 x = 8191
n = 14 x = 16383
n = 15 x = 32767
n = 16 x = 65535
n = 17 x = 131071
n = 18 x = 262143
n = 19 x = 524287
n = 20 x = 1048575
n = 21 x = 2097151
n = 22 x = 4194303
n = 23 x = 8388607
n = 24 x = 16777215
n = 25 x = 33554431
n = 26 x = 67108863
n = 27 x = 134217727
n = 28 x = 268435455
n = 29 x = 536870911
n = 30 x = 1073741823
n = 31 x = 2147483647
n = 32 x = 4294967295
n = 33 x = 8589934591
n = 34 x = 17179869183
n = 35 x = 34359738367
n = 36 x = 68719476735
n = 37 x = 137438953471
n = 38 x = 274877906943
n = 39 x = 549755813887

As a consequence of Theorem 18 from Hardy-Wright, we have the following

Corollary: For two natural numbers 1 < a and b: a${^b}$ - 1 is composite if a > 2 (because (a - 1) divides a$^{b}$ - 1);
or in the case a = 2: if b = s * t (because 2$^{s}$ - 1 divides 2$^{s*t}$ - 1

Last edited:
yes but consider the number 11 which is a prime while 2^11 -1 is not a prime.

yes but this does not help

I think, my Corollary helps to delete all 2${^b}$ - 1 with a composite b; but unfortunately, there is no help for sieving the Mersenne primes:

Theorem 18 by HW says (in short): 'If 2${^b} - 1$ is a prime, then b is a prime'; and the 'other way round' is not valid

Last edited:
To show that (X^(2*n) ) - 1 has a factor of x-1 for any n. Consider x^2 - 1 = (x-1) * (x+1 )

so if x^2 -1 is a factor of a function then x-1 is a factor.

Consider x^4 - 1 = ( x^2 -1 ) * ( x^2 + 1 )

so x-1 is a factor of x^4 -1

consider x^6 - 1 = (x^2 -1 ) * ( x^4 + x^2 + 1 )

so x-1 is a factor of x^6 -1

consider x^8-1 = ( x^2 -1 ) * ( x^6 + x^ 4 + x^ 2 + 1 )

so x-1 is a factor of x^8 -1
etc

So it seems to me…

x^(2*n) - 1 = (x^2 -1 ) * ( x^(2*(n-1)) + x^(2 * (n-2)) + ……. + 1 )

## 1. What are Mersenne Primes?

Mersenne primes are prime numbers that can be expressed in the form of 2^n-1, where n is also a prime number.

## 2. How are Mersenne Primes identified?

Mersenne primes are identified by using the Lucas-Lehmer test, which involves performing a series of calculations using the number 2 and checking for a specific pattern.

## 3. Why are Mersenne Primes important?

Mersenne primes have been studied for centuries and are of interest to mathematicians because they have unique properties and can be used in various mathematical equations and formulas.

## 4. Can non-prime numbers also be expressed in the form of 2^n-1?

Yes, non-prime numbers can also be expressed in the form of 2^n-1, but they will not satisfy the conditions for being a Mersenne prime.

## 5. How are non-prime numbers eliminated during the process of identifying Mersenne Primes?

Non-prime numbers are eliminated by using various techniques, such as the Lucas-Lehmer test and other algorithms, to check for specific patterns and properties that are unique to Mersenne primes.

• General Math
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
32
Views
3K
• Calculus
Replies
24
Views
3K
• Linear and Abstract Algebra
Replies
3
Views
1K
• General Math
Replies
24
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Linear and Abstract Algebra
Replies
8
Views
2K
• Linear and Abstract Algebra
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
23
Views
1K
• Engineering and Comp Sci Homework Help
Replies
33
Views
3K