Mathematical Analysis - Exercise 1.3

Problem:

Solution:

Suppose $n = ab$ is not prime, then we can write $2^{ab} = (2^{a})^b$. Applying the identity we just proved in the previous problem, we have:

$2^{ab} - 1 =  (2^{a})^b - 1 =  (2^{a})^b - 1^b = (2^a - 1)(\cdots)$.

Therefore if $a \ne 1$, we have a non-trivial factor for $2^{ab} - 1$.

The contradiction show $n$ has to be prime.