# Primes of form Power of Two plus One

## Theorem

Let $n \in \N$ be a natural number.

Let $2^n + 1$ be prime.

Then $n = 2^k$ for some natural number $k$.

## Proof 1

Suppose $n$ has an odd divisor apart from $1$.

Then $n$ can be expressed as $n = \left({2 r + 1}\right) s$.

So:

\(\displaystyle 2^n + 1\) | \(=\) | \(\displaystyle 2^{\left({2 r + 1}\right) s} + 1\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \left({2^s}\right)^{\left({2 r + 1}\right)} + 1^{\left({2 r + 1}\right)}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \left({2^s + 1}\right) \left({2^{2rs} - 2^{\left({2r-1}\right) s} + 2^{\left({2r-2}\right) s} - \cdots - 2^s + 1}\right)\) | Sum of Odd Positive Powers |

and so $2^n + 1$ is not prime.

Hence $2^n + 1$ can be prime only if $n$ has only even divisors.

That is, if $n = 2^k$ for some natural number $k$.

$\blacksquare$

## Proof 2

A specific instance of Primes of form Power plus One:

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

- $(1): \quad q$ is even

and

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

As $2$ is even, the result applies.

$\blacksquare$

## Also see

- Definition:Fermat Prime: a prime of the form $2^{\left({2^k}\right)} + 1$.

## Historical Note

In $1640$, Pierre de Fermat wrote to Pierre de Fermat wrote to Bernard Frénicle de Bessy announcing this result.

From the fact that all integers of the form $2^n + 1$ such that $n = 2^k$ that he tested were prime, he went on to make his famous Fermat Prime Conjecture: that they are all prime.

This was refuted by Leonhard Paul Euler, who discovered that $2^{2^5}$ is composite in $1732$.