Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
3  
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.