Prove that if $n > 1$ is not a power of 2 then $2^n + 1$ is a composite integer.
Note that if $n$ is a power of 2 then $2^n + 1$ is a Fermat number.
Hint: If $n$ is odd then we have the following result:
$$ x^n + 1 = (x + 1) (x^{n-1} - x^{n-2} + x^{n-3} - x^{n-4} + \ldots - x + 1)$$
Let's write $n=ab$ where $a=2^k$ are any prime factors 2 with multiplicity $k$, and $b$ is the remaining odd factor.
If $b=1$ then $n$ is a power of 2, a case which is excluded. Since $b$ is odd, we have $b \ge 3$.
Using the hint, since $b$ is odd, we have
$$ \begin{align} 2^n + 1 & = 2^{ab} + 1 \\ \\ & = (2^a)^b + 1 \\ \\ & = (2^a+1) \biggl ( (2^a)^{b-1} - (2^a)^{b-2} + (2^a)^{b-3} - \ldots - (2^a) +1 \biggr ) \end{align}$$
We need to show these factors are non-trivial, that is greater than 1, and less than $n$:
- Since $k \ge 0 \implies a \ge 1$, we have $(2^a +1) \ge 3 > 1$.
- Since $b \ge 3$, we have $n = 2^{ab}+1 \ge 2^{3a}+1 > (2^a + 1)$.
Given the conditions $n>1$ and is not a power of 2, we have found a non-trivial factor of $2^n+1$. This means $2^n+1$ must be a composite integer.