Mersenne Numbers
What Are Mersenne Numbers?
A Mersenne number is a number of the form $$ M_k=2^k-1 $$ where k is an integer greater than 1.
These numbers are denoted as Mk and are named after the 17th-century mathematician Marin Mersenne, who studied them extensively.
Some Mersenne numbers are prime, while others are composite.
A Practical Example
$$ M_2 = 2^2 - 1 = 3 \\ M_3 = 2^3 - 1 = 7 \\ M_4 = 2^4 - 1 = 15 \\ M_5 = 2^5 - 1 = 31 \\ M_6 = 2^6 - 1 = 63 \\ \vdots $$
A Mersenne number that is also prime is called a "Mersenne prime."
In general, if Mk is prime, then k must also be prime. This means that when searching for Mersenne primes, we only need to consider cases where k itself is a prime number.
$$ M_2 = 2^2 - 1 = 3 \\ M_3 = 2^3 - 1 = 7 \\ M_5 = 2^5 - 1 = 31 \\ M_{7} = 2^7 -1 = 127 \\ \vdots $$
For this reason, special attention is given to Mersenne numbers where the exponent $ k $ is prime.
However, the reverse is not necessarily true. Just because $ k $ is prime doesn’t mean that $ M_k $ is also prime.
For example, $ M_{11} = 2^{11}-1 = 2047 $, which is composite since $ 2047 = 23 \times 89 $.
To determine whether a Mersenne number with a prime exponent $ k $ is itself prime, we can use the Lucas-Lehmer test.
Note. Mersenne primes play a crucial role in the search for large prime numbers. In fact, many of the largest known prime numbers are Mersenne primes. For example, one of the largest primes ever discovered, $ 2^{82,589,933} -1 $, found in 2018, is a Mersenne prime. These numbers are also important in number theory and have applications in fields such as cryptography.
Mersenne Primes
If Mk is prime, then k must also be prime: $$ M_k \in P \rightarrow k \in P $$
Example
The number M2 = 3 is prime.
Since k = 2 is also prime, this confirms the rule.
Note. However, the converse is not always true: if k is prime, it does not necessarily mean that Mk is also prime. For instance, M11 is not a prime number, even though k = 11 is prime. $$ M_k=2^{11}-1=2047=23 \cdot 89 $$
Proof
Let’s prove that if k is not prime, then Mk is also not prime.
By definition, k can be expressed as the product of two integers a and b:
$$ k = ab $$
Thus,
$$ 2^k-1= 2^{ab}-1 = 2^a \cdot 2^b - 1 $$
This can be rewritten as the product of two factors:
$$ (2^a-1) \cdot (1+2^a+2^{2a}+...+2^{(b-1)a} ) $$
Since this is a nontrivial factorization, it follows that Mk is not prime whenever k is composite.
Example. The number k=4 is not prime. The corresponding Mersenne number is $$ M_4 = 2^4-1= 15 $$ Using the previous identity with a=2 and b=2 (where k=ab), we can rewrite M4 as: $$ M_4 = (2^2 -1) \cdot (1+2^2) = 3 \cdot 5 = 15 $$ This confirms that 15 is not a prime number.
Lucas' Theorem
A Mersenne number Mp with a prime exponent p (greater than 2) is prime if and only if Mp divides Lp-1.
Here, Lp is a recursive sequence defined by Lucas, starting with L1=4:
$$ L_{n+1} = L_n^2 - 2 $$
Below is an example of the Lucas sequence:
$$ L_1 = 4 \\ L_2 = (4)^2-2 =14 \\ L_3 = (14)^2-2 =194 \\ L_4 = (194)^2-2 =37634 \\ L_5 = (37634)^2-2 =1416317954 $$
Example 1
The Mersenne number M3 is equal to 7:
$$ M_3 = 2^3 -1 = 7 $$
According to Lucas’ theorem, M3 is prime if it divides L2.
$$ L_2 = 14 $$
Indeed, M3=7 divides L2=14 exactly.
Therefore, M3 is a prime number.
