Exercise 1.3.42 (Fermat primes)

Question

If $2^n + 1$ is an odd prime for some integer $n$, prove that $n$ is a power of $2$.

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}}

\begin{proof} We prove the contraposition: if $n \geq 1$ is not a power of $2$, then $N = 2^n + 1$ is composite.

If $n\geq 1$ is not a power of $2$ (then $n 
e 2^0 = 1$, so $n>1$), it's decomposition in prime factors shows that $n$ is a product of a power of $2$ by an odd integer greater than $1$:
$$n = 2^l (2 k+1), \qquad l\geq 0,\ k \geq 1.$$
Then 
\begin{align*}
 N &= 2^n + 1\
 &= 2^{2^l (2k+1)} + 1\
 &= x^{2k+1} + 1
 \end{align*}
 where $x = 2^{2^l}$ is an integer.
 
 But
 $$x^{2k+1} + 1 = (x + 1)(x^{2k}  - x^{2k-1} + \cdots + (-1)^i x^{i} + \cdots + 1) = (x+1) \sum_{i=0}^{2k} (-1)^i x^{i}.$$
Write $q = \sum_{i=0}^{2k} (-1)^i x^{i} = \frac{x^{2k+1} + 1}{x+1} \in \N^*$. Then
$$N = (x+1) q,$$
Using $k\geq 1$, 
$$1< x +1=2^{2^l}  + 1 < 2^{2^l(2k+1)} + 1 = N,$$
so $1 < x+1 < N$. Therefore $N$ is composite.

If $2^n + 1$ is an odd prime for some integer $n$, then $n = 2^l$ is a power of $2$
\end{proof}

Exercise 1.3.42 (Fermat primes)

Answers

Comments

Exercise 1.3.42 (Fermat primes)

Answers

Comments

Add answer