# Help in understanding the proof of Mersenne Prime

Problem: $$\text{ If } 2^{n} - 1 \text{ is prime then n is prime}$$

Proof 1: $$\text{If } n = kl \text{ with } 2 \leq k, l < n \text{ then } (2^{k} - 1)|(2^{n} - 1). \text{ Hence if } 2^{n} - 1 \text{ is prime, n must be prime }$$

Proof 2: Using the identity: $$2^{n} - 1 = ( 2 - 1 )( 2^{k-1} + 2^{k-2} + ... + 1 )$$

$$\text{ Let }n = rs, \text{ then } 2^{n} - 1 = ( 2^{r} - 1 )( 2^{r(s-1)} + 2^{r(s-2)} + ... + 1 )$$ $$\text{ However each factor on the right exceeds 1 contradicting with the fact that } 2^{n} - 1 \text{ is prime }$$ Hence, n is prime.

Proof 1: I have no idea what the author's purpose.

Proof 2: I understood a little bit. Can anyone help me explain why n must be prime? I am totally lost with the above proofs. If we let $n = rs$, then what can we say about $n$ with $2^{n} - 1$ is prime?

-

Both the proofs are the same. This is an example of a proof by transposition or proof by contrapositive where you prove the contrapositive.

The statement $A \Rightarrow B$ is equivalent to the statement $\neg B \Rightarrow \neg A$.

Hence, proving $A \Rightarrow B$ is equivalent to proving $\neg B \Rightarrow \neg A$.

The statement $A$ in your problem is "$2^n - 1$ is a prime" and the statement $B$ in your problem is "$n$ is a prime".

In this context, we have "If $2^n - 1$ is a prime, then $n$ is a prime".

The contrapositive is "If $n$ is not a prime then $2^n - 1$ is not a prime".

The author now proves the contrapositive statement. Hence, the author takes $n$ to be not a prime i.e. he takes $n$ to be a composite number.

Since $n$ is a composite number, $n$ can be written as $n = kl$, where $2 \leq k,l < n$.

So $2^n - 1 = 2^{kl} - 1 = (2^k)^l-1$.

Now observe that $(a-1)|(a^l - 1)$, $\forall l \in \mathbb{N}$.

This can be seen from the remainder theorem or by factorizing $(a^l - 1) = (a-1) (a^{l-1} + a^{l-2} + \cdots + a + 1)$.

Note that $2 < 2^k-1 < 2^n-1$ since $2 \leq k<n$ and plug in $a=2^k$, we get $((2^k)^l - 1) = ((2^k)-1) ((2^k)^{l-1} + (2^k)^{l-2} + \cdots + (2^k) + 1)$. Hence, we have $(2^k - 1)|(2^n-1)$, which implies $2^n-1$ is a composite number.

Hence, we have "If $n$ is not a prime then $2^n - 1$ is not a prime" which implies the contrapositive i.e. "If $2^n - 1$ is a prime, then $n$ is a prime".

Note

Say, we denote the original statement by $A$.

Let $A$ be the statement "If $2^n - 1$ is a prime, then $n$ is a prime"

Let $B$ be the statement "If $n$ is not a prime, then $2^n-1$ is not a prime"

Let $C$ be the statement "If $2^n-1$ is not a prime, then $n$ is not a prime"

Let $D$ be the statement "If $n$ is a prime, then $2^n - 1$ is a prime"

Statements $A$ and $B$ are contrapositives of each other. So if $A$ is true then so is $B$ and if $B$ is true then so is $A$.

Similarly, Statements $C$ and $D$ are contrapositives of each other. So if $C$ is true then so is $D$ and if $D$ is true then so is $C$.

Statements $C$(equivalently statement $D$) and $A$(equivalently statement $B$) are converses of each other. In general, we cannot conclude that if a statement is true then its converse is true and we cannot conclude that if a converse is true then the statement is true.

In this example, statement $A$(equivalently statement $B$) is true.

However, statements $C$(equivalently statement $D$) which is the converse of statement $A$(equivalently statement $B$) is false.

An example is $2^{11} - 1 = 2047 = 23 × 89$ is not a prime but $11$ is a prime. So $C$(equivalently statement $D$) is false.

-
Very good and detailed answer, +1. – Eric Naslund Feb 12 '11 at 3:27
Ambikasaran: Many thanks for your great effort ;) ! I feel less dumb now. – Chan Feb 12 '11 at 4:51
@Chan: The reason why I explained the question in depth, is that I usually like to play with people's reasoning in day to day conversations using this seemingly simple statement, $A \Rightarrow B$ is equivalent to $\neg B \Rightarrow \neg A$. You will be surprised to hear so many people getting confused on this fact and drawing illogical conclusions :). It is actually fun to have them think about this. – user17762 Feb 12 '11 at 19:42

The essence of the matter is the following: $\rm\ f\:(gcd(n,m))\ =\ gcd(f(n),f(m))\$ for $\rm\ f(n)\ =\ 2^n-1\:$. Because the map $\rm\:f\:$ preserves gcds it must preserve many multiplicative properties (e.g. primes). You can find further discussion and proofs in my posts here. If you go on to study divisor theory then these properties will become crystal clear.

-
That is a different way of writing it. I like it! – Eric Naslund Feb 12 '11 at 3:28
@Eric: We have Kronecker to thank for the beautiful theory of divisors. It deserves to be much better known. – Bill Dubuque Feb 12 '11 at 3:33