# Fermat Numbers Proof [duplicate]

Fermat numbers are shown by: $F_m = 2^{2^m} + 1$.

How can I prove that for any $m ≠ n$, I can have $(F_m, F_n) = 1$?

## marked as duplicate by lab bhattacharjee, Emily, David Peterson, Sujaan Kunalan, Mark FantiniJan 17 '15 at 18:17

• See here (ProofWiki). – user26486 Jan 17 '15 at 15:59
• @mathh How is that a duplicate? – Alexis Dailey Jan 17 '15 at 16:06
• See here for a very simple proof that works more generally. – Bill Dubuque Jan 27 '15 at 0:09

Full credit goes to ProofWiki.

Let $F_{n+k}-1=2^{2^{n+k}}, F_n-1=2^{2^n}$. Then

$F_{n+k}-1=\left( 2^{2^{n}}\right)^{2^k}=(F_n-1)^{2^k}$

$$\begin{cases}p\mid F_{n+k}\\ p\mid F_n\end{cases}\iff \begin{cases}F_{n+k}-1\equiv -1\pmod p\\F_n\equiv 0\pmod p\end{cases}\iff \begin{cases}(F_n-1)^{2^k}\equiv -1\pmod p\\F_n\equiv 0\pmod p\end{cases}$$

$$\implies (-1)^{2^k}\equiv -1\pmod p\iff 1\equiv -1\pmod p\iff p\mid 2\iff p=2$$

But $F_{n+k}, F_n$ are both odd. Therefore, a prime $p$ dividing both $F_{n+k}, F_n$ does not exist.

Show by induction that $2^{2^n}-1$ is a multiple of $2^{2^m}+1$.
Hint: $2^{2^{m+1}}=2^{2^m.2}=(2^{2^m})^2$