Mersenne primes Lemma

Question

How does one show that if $2^n-1$ is a prime, then $n$ is a prime?

Answer 1

Prove the contrapositive.

If $n$ is not prime, then it has a factor $d$ between $1$ and $n.$

Therefore $2^d-1$ is a factor of $2^n-1$ between $1$ and $2^n-1$, so $2^n-1$ is not prime.

---

Proof that $2^d-1\mid 2^n-1:\; $ if $n=kd$ then $2^n-1=(2^d)^k-1\equiv1^k-1=0\pmod{2^d-1}$.

Answer 2

Look at $\ 2^n-1,\ $ it's like this

$$ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 $$

in base $\ 2.\ $This was an illustration for $\ 2^{15}-1.\ $ Now, when $\ n=k\cdot m\ $ is composed, where both natural numbers $\ k\ m>1\ $ are greater than $\ 1,\ $ then you get two ways to decompose $n\ $ (when $\ k=m\ $ then these two ways are one and the same). For instance, for $\ n=15=3\cdot 5\ $ we get that $\ 2^{15}-1\ $ is like this:

$$ 1 1 1 1 1\,\ 1 1 1 1 1\,\ 1 1 1 1 1 $$

or like this:

$$ 1 1 1\,\ 1 1 1\,\ 1 1 1\,\ 1 1 1\,\ 1 1 1 $$

i.e.

$$ 2^{15}-1\ =\\ \ \\ (2^5-1)\cdot(1+2^5+2^{10})\quad = \quad(2^3-1)\cdot(1+2^3+2^6+2^9+2^{12}) $$

In general,

$$ 2^n\,\ =\,\ (2^k-1)\cdot\sum_{t=0}^{m-1} 2^{k\cdot t} \,\ =\,\ (2^m-1)\cdot\sum_{t=0}^{k-1} 2^{m\cdot t} $$

Thus we get not just one but even two decompositions on $\ n\ $ unless $\ k=m\ $ (then we get just one decomposition so far, but even one is good enough). Of course, when there are more different decompositions of $\ n\ $ then we get more different decompositions of $\ 2^n-1.\ $

Answer 3

Given $2^p-1$ is prime. Assume $p$ is not prime. Then $∃a,b∈\mathbb{Z}∋a,b>1$ and $p=ab$. $$2^p-1=2^{ab}-1=(2^a )^b-1=(2^a-1)\frac{(2^a )^b-1}{(2^a-1)}$$ Since $\frac{(2^a )^b-1}{(2^a-1)}$ is the solution to a geometric series, $$(2^a-1)\frac{(2^a )^b-1}{(2^a-1)}=(2^a-1) \sum_{k=0}^{b-1}(2^a )^k =2^p-1.$$ Thus, $2^a-1$ is a divisor of $2^p-1$ implies $2^p-1$ is not prime, which is a contradiction. Therefore, $p$ is prime if $2^p-1$ is prime.

Answer 4

Note that $2^n-1$ is the number of sequences that can result from flipping a two-sided coin ($H$ and $T$ for “heads” and “tails”) $n$ times in a row, where the result is not $n$ consecutive heads, that is, where there is at least one $T$ (for tails) in the sequence.

Now suppose $n$ factors into positive integers as $n=ab$.

Every length-$n$ sequence of flips can be represented uniquely as an $a\times b$ array ($a$ rows of $b$ columns) of flips. We will calculate the cardinality of the set $A$ of these arrays that contain at least one $T$ (which cardinality we know is $2^n-1$) as follows.

Let $A_i$ be the subset of $A$ containing those arrays where the first $T$ appears in row $i$. In any such array, the first $i-1$ rows contain all $H$s, so there is only one distinct pattern for each of those rows. There are $2^a-1$ different patterns possible for the $a$ flips in the $i$-th row (because that row contains a $T$), and any pattern (there are $2^a$) is possible in each of the remaining $b-i$ rows.

The number of arrays in $A_i$ is therefore $1^{i-1}\cdot(2^a-1)^1\cdot(2^a)^{b-i}$.

The sets $A_i$ are disjoint and have union $A$, so the sum of the $|A_i|$ equals $|A|=2^n-1$. For each $i$, the cardinality of $A_i$ is divisible by $2^a-1$, so $2^a-1$ divides $\sum A_i$, which is $2^n-1$. If $2^n-1$ is prime, then $2^a-1$ must be either $1$ or $2^n-1$; that is, $a$ is either $1$ or $n$. This shows that if $2^n-1$ is prime, then the only factorization of $n$ into positive integers $n=ab$ is $n=1\cdot n$ or $n=n\cdot 1$, and therefore $n$ is prime.