## A beautiful proof about Mersenne primes

Theorem: 2^{n} - 1 cannot be prime if *n* is composite.

Lemma: c^{n} - 1 can be written as (c - 1)(c^{n-1} + … + c^{1} + 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^{n} - 1 is a prime, then c = 2 and n is a prime.

See this handout for this and other proofs.

## 0 comments:

## Post a Comment