Exercice 34 Nombres de Fermat

Raisonnons par l'absurde en supposant que $n$ n'est pas une puissance de $2$. En regroupant les facteurs $2$ de sa décomposition, on écrit $n=2^{\alpha}m$ avec $m$ impair, et $m\neq 1$ puisque $n$ n'est pas une puissance de $2$ : donc $m\geqslant 3$. On pose $k=2^{\alpha}$, de sorte que $n=km$ et : $$2^{n}+1=\left(2^{k}\right)^{m}+1^{m}.$$ Comme $m$ est impair, l'exercice 30 b) montre que $2^{k}+1$ divise $2^{n}+1$. Or $k=\frac{n}{m}<n$, donc $1<2^{k}+1<2^{n}+1$ : l'entier $2^{n}+1$ admet un diviseur autre que $1$ et lui-même, ce qui contredit le fait qu'il soit premier. Ainsi $\boxed{n \text{ est une puissance de } 2}$.

La réciproque est fausse : $F_{0}=3$, $F_{1}=5$, $F_{2}=17$, $F_{3}=257$ et $F_{4}=65\,537$, où $F_{j}=2^{2^{j}}+1$, sont premiers, mais Euler a montré en 1732 que $F_{5}=4\,294\,967\,297=641\times 6\,700\,417$. Le résultat est l'analogue « additif » de celui de l'exercice 25 sur les nombres de Mersenne.