# Primes of form Power plus One

## Theorem

Let $q, n \in \Z_{>0}$ such that $q > 1$.

Then $q^n + 1$ is prime only if:

$(1): \quad q$ is even

and

$(2): \quad n$ is of the form $2^m$ for some positive integer $m$.

## Proof

Note that if $q = 1$ then $q^n + 1 = 2$ which is prime.

Hence the condition on $q$ in the statement of the theorem.

So by hypothesis $q > 1$.

Let $q$ be odd.

Then by Two divides Power Plus One iff Odd, $q^n + 1$ is not prime.

Let $q$ be even.

Let $n$ be expressed in the form $r 2^m$ where $r$ is odd.

Then $q^n + 1$ can be expressed in the form:

$q^{r 2^m} + 1 = \left({q^{2^m}}\right)^r + 1$

By Number Plus One divides Power Plus One iff Odd, $q^{2^m} + 1$ is a divisor of $\left({q^{2^m}}\right)^r + 1$.

So for all $r > 1$ it follows that $\left({q^{2^m}}\right)^r + 1$ is composite.

Hence the result.

$\blacksquare$

## Examples

The sequence of primes of the form $q^2 + 1$ begins:

 $\displaystyle 1^2 + 1$ $=$ $\displaystyle 1 + 1 = 2$ is prime $\displaystyle 2^2 + 1$ $=$ $\displaystyle 4 + 1 = 5$ is prime $\displaystyle 4^2 + 1$ $=$ $\displaystyle 16 + 1 = 17$ is prime $\displaystyle 6^2 + 1$ $=$ $\displaystyle 36 + 1 = 37$ is prime $\displaystyle 10^2 + 1$ $=$ $\displaystyle 100 + 1 = 101$ is prime

The sequence of primes of the form $q^4 + 1$ begins:

 $\displaystyle 1^4 + 1$ $=$ $\displaystyle 1 + 1 = 2$ is prime $\displaystyle 2^4 + 1$ $=$ $\displaystyle 16 + 1 = 17$ is prime $\displaystyle 4^4 + 1$ $=$ $\displaystyle 256 + 1 = 257$ is prime $\displaystyle 6^4 + 1$ $=$ $\displaystyle 1296 + 1 = 1297$ is prime $\displaystyle 16^4 + 1$ $=$ $\displaystyle 65\,536 + 1 = 65\,537$ is prime