A beautiful proof about Mersenne primes

A beautiful proof about Mersenne primes

Theorem: 2ⁿ - 1 cannot be prime if n is composite.

Lemma: cⁿ - 1 can be written as (c - 1)(c^n-1 + … + c¹ + 1).

The proof for the lemma is simple. You end up subtracting

   c^n + c^{n-1} + ... + c
-        c^{n-1} + ... + c + 1
------------------------------------
   c^n - 1

So if n can be written as ab where both a > 1 and b > 1, then

   2^{ab} - 1 
= (2^a)^b - 1
= (2^a - 1)((2^a)^{b-1} + (2^a)^{b-2} + ... + 1)

So we have (2^a - 1) as a divisor.

A stronger theorem is: Suppose c > 1 and n > 1, and cⁿ - 1 is a prime, then c = 2 and n is a prime.

See this handout for this and other proofs.