mathschallenge.net

Problem

Given that $n \ge 2$ and $a^n - 1$ is prime, prove that $a = 2$, and $n$ must be prime.

Solution

First we note that $a^n - 1 = (a - 1)(a^{n-1} + a^{n-2} + ... + a^2 + a + 1)$.

As $n \ge 2$, the second bracket on the RHS (right hand side) will be greater than or equal to $a + 1 \ge 2$.

If the LHS is prime then the first bracket on the RHS, $a - 1$, must equal 1, in which case $a = 2$.

Let $n = xy$.

$\therefore 2^{xy} - 1 = (2^x - 1)(2^{(x-1)y} + 2^{(x-2)y} + ... + 2^{2y} + 2^y + 1)$

That is, $2^n - 1$ is divisible by $2^x - 1$, where $x$ is a factor of $n$.

But as $2^n - 1$ is prime then $2^x - 1 = 1 \implies x = 1$.

Similarly if $y$ had factors $x'$ and $y'$ we could show that $x' = 1$, and so on ad infinitum. In other words, $y = n$, which must be prime. Q.E.D.

Does it follow that $2^n - 1$ is prime if $n$ is prime?