Exercice 30 Nombres de Fermat

1. (a) On développe le produit du membre de droite. En notant $S=x^{2k}-x^{2k-1}+\cdots+x^{2}-x+1$, la somme alternée des puissances de $x$ de $0$ à $2k$ : $$(x+1)S=\underbrace{\left(x^{2k+1}-x^{2k}+\cdots+x^{3}-x^{2}+x\right)}_{x\times S} +\underbrace{\left(x^{2k}-x^{2k-1}+\cdots+x^{2}-x+1\right)}_{S}$$ Tous les termes intermédiaires s'éliminent deux à deux, car ils apparaissent une fois avec chaque signe. Il ne reste que le premier terme de la première somme et le dernier de la seconde : $$\boxed{x^{2k+1}+1=(x+1)\left(x^{2k}-x^{2k-1}+\cdots+x^{2}-x+1\right)}$$ C'est le télescopage classique de la somme géométrique de raison $-x$.

(b) Soit $m$ un entier impair, $m\geqslant 3$. On écrit $m=2k+1$ avec $k\geqslant 1$, et l'on applique l'égalité précédente à $x=2$ : $$2^{m}+1=(2+1)\times S=3S$$ Le nombre $2^{m}+1$ est donc divisible par $3$. Comme $m\geqslant 3$, on a $2^{m}+1\geqslant 9>3$ : $$\boxed{2^{m}+1 \text{ n'est pas premier}}$$ Le cas $m=1$ est à écarter : $2^{1}+1=3$ est bien premier.

(c) Supposons que $m$ possède un diviseur strict impair $d>1$, et écrivons $m=dq$ avec $q\geqslant 1$. En posant $x=2^{q}$ et $d=2k+1$, l'égalité de la question a) donne : $$2^{m}+1=\left(2^{q}\right)^{d}+1=x^{d}+1=(x+1)\times S=\left(2^{q}+1\right)\times S$$ Le nombre $2^{q}+1$ est donc un diviseur de $2^{m}+1$. Il est strictement supérieur à $1$ puisque $q\geqslant 1$, et strictement inférieur à $2^{m}+1$ puisque $q<m$ (car $d>1$). $$\boxed{2^{m}+1 \text{ n'est pas premier}}$$

(d) Soit $m\geqslant 1$ tel que $2^{m}+1$ soit premier. D'après la question c), $m$ ne possède aucun diviseur impair strictement supérieur à $1$. Or tout entier s'écrit comme un produit de nombres premiers : si l'un d'eux était impair, il fournirait un tel diviseur. Tous les facteurs premiers de $m$ valent donc $2$ : $$\boxed{m \text{ est une puissance de } 2, \text{ donc } 2^{m}+1=2^{2^{n}}+1}$$

2. (a) $$F_{0}=2^{1}+1=\boxed{3} \quad ; \quad F_{1}=2^{2}+1=\boxed{5} \quad ; \quad F_{2}=2^{4}+1=\boxed{17}$$

$$F_{3}=2^{8}+1=\boxed{257} \quad ; \quad F_{4}=2^{16}+1=\boxed{65\,537}$$ Les nombres $3$, $5$, $17$ et $257$ se testent rapidement. Pour $65\,537$, il suffit de tester les diviseurs premiers jusqu'à $\sqrt{65\,537}\approx 256$ : $$\boxed{F_{0},\;F_{1},\;F_{2},\;F_{3} \text{ et } F_{4} \text{ sont tous premiers}}$$

(b) $$F_{5}=2^{32}+1=4\,294\,967\,297$$ Un test de primalité montre que ce nombre n'est pas premier : $$\boxed{F_{5}=641\times 6\,700\,417}$$ La conjecture de Fermat est donc fausse. C'est Euler qui trouva cette factorisation en $1732$, près d'un siècle après Fermat. On ne connaît d'ailleurs aujourd'hui aucun nombre de Fermat premier au-delà de $F_{4}$.

(c) Par définition, $F_{n}-1=2^{2^{n}}$, donc : $$(F_{n}-1)^{2}+1=\left(2^{2^{n}}\right)^{2}+1=2^{2\times 2^{n}}+1=2^{2^{n+1}}+1=F_{n+1}$$

$$\boxed{F_{n+1}=(F_{n}-1)^{2}+1}$$ En développant, $F_{n+1}=F_{n}^{2}-2F_{n}+2$, donc : $$F_{n+1}\equiv 2\;[F_{n}]$$ Ainsi $\mathrm{PGCD}(F_{n},F_{n+1})=\mathrm{PGCD}(F_{n},2)$. Or $F_{n}=2^{2^{n}}+1$ est impair : $$\boxed{\mathrm{PGCD}(F_{n},F_{n+1})=1}$$ Deux nombres de Fermat consécutifs sont donc toujours premiers entre eux.

3. Démontrons par récurrence la propriété $\mathcal{P}(n)$ : « $F_{n}$ se termine par le chiffre $7$ », pour $n\geqslant 2$.

Initialisation : $F_{2}=17$ se termine bien par $7$, donc $\mathcal{P}(2)$ est vraie.

Hérédité : Supposons $\mathcal{P}(n)$ vraie pour un entier $n\geqslant 2$, c'est-à-dire $F_{n}\equiv 7\;[10]$. Alors $F_{n}-1\equiv 6\;[10]$, et d'après la question 2c : $$F_{n+1}=(F_{n}-1)^{2}+1\equiv 6^{2}+1=37\equiv 7\;[10]$$ Donc $\mathcal{P}(n+1)$ est vraie.

Conclusion : La propriété est vraie au rang $2$ et héréditaire : $$\boxed{\text{Pour tout } n\geqslant 2, \; F_{n} \text{ se termine par le chiffre } 7}$$ On le vérifie : $F_{2}=17$, $F_{3}=257$, $F_{4}=65\,537$, $F_{5}=4\,294\,967\,297$.