Nombre de Fermat

• ${\displaystyle F_{n}\ =\ (F_{n-1}-1)^{2}+1\quad {\rm {ou}}\quad F_{n}=F_{n-1}^{2}-2(F_{n-2}-\ 1)^{2}.}$

En effet :

${\displaystyle F_{n}\ =\ 2^{2^{n}}+1\ =\ (2^{2^{n-1}})^{2}+1\ =\ (F_{n-1}\ -\ 1)^{2}+1\ =\ F_{n-1}^{2}-2F_{n-1}+2\ =\ F_{n-1}^{2}-2(F_{n-2}\ -\ 1)^{2}.}$

• ${\displaystyle F_{n}\ =\ \prod _{i=0}^{n-1}F_{i}\ +\ 2\quad {\rm {ou}}\quad F_{n}=F_{n-1}+2^{2^{n-1}}\prod _{i=0}^{n-2}F_{i}.}$

Une récurrence et l'égalité suivante permet de calculer le premier produit :

${\displaystyle F_{n}-2=(F_{n-1}\ -1)^{2}-1\ =\ F_{n-1}(F_{n-1}-2).}$

La seconde égalité s'en déduit :

${\displaystyle F_{n}=2^{2^{n}}+1\ =\ 2^{2^{n-1}}+1+2^{2^{n-1}}(2^{2^{n-1}}-1)\ =\ F_{n-1}+2^{2^{n-1}}(F_{n-1}-2)=F_{n-1}\ +\ 2^{2^{n-1}}\prod _{i=0}^{n-2}F_{i}.}$

• Deux nombres de Fermat distincts sont premiers entre eux.

Soit n et m deux entiers positifs tels que n est strictement plus grand que m. Montrons que le seul facteur commun à F_n et F_m est 1. Un calcul précédent montre que

${\displaystyle F_{n}=qF_{m}+2\quad {\rm {si}}\quad q=\left(\prod _{i=0}^{m-1}F_{i}\right)\left(\prod _{i=m+1}^{n-1}F_{i}\right)}$

donc un diviseur commun à F_n et F_m est aussi un diviseur de 2. Or 2 ne divise pas F_n. Ces trois entiers sont donc premiers entre eux deux à deux.

• ${\displaystyle D(n,b)=\left\lfloor \log _{b}\left(2^{2^{n}}+1\right)+1\right\rfloor \approx \left\lfloor 2^{n}\,\log _{b}2+1\right\rfloor .}$

Il suffit de remarquer que le nombre de chiffres nécessaire pour écrire un entier a en base b est égal à la partie entière de log_b(a).

Il existe deux entiers a impair et b tels que k = a 2^b. En posant c = 2^(2b), on dispose alors des égalités suivantes :

${\displaystyle 2^{k}+1=c^{a}+1=(c+1)\sum _{i=0}^{a-1}(-1)^{i}c^{i},}$

qui montrent que c + 1 est un diviseur du nombre premier 2^k + 1 et donc lui est égal, si bien que k = 2^b.

• Tout facteur premier p d'un nombre de Fermat F_n est de la forme k.2ⁿ⁺¹ + 1, où k est un entier.
  Modulo p, F_n est congru à 0 donc 2²ⁿ est congru à –1, si bien que l'ordre multiplicatif de 2 dans l'anneau ℤ/pℤ est égal à 2ⁿ⁺¹. Or cet ordre multiplicatif est un diviseur de p – 1, ce qui termine la démonstration.
• ${\displaystyle F_{5}=641\times 6~700~417.}$
  On peut le vérifier par un simple calcul, mais expliquons comment Euler découvrit le diviseur 641. On cherche un entier k tel que le nombre p = 64k + 1 soit à la fois premier et diviseur strict de F₅. Les premières valeurs de k ne conviennent pas, mais dès k = 10, on constate que p = 641 est premier et que modulo p,
  ${\displaystyle -~2^{4}\equiv 5^{4}}$ donc ${\displaystyle -2^{32}\equiv 5^{4}\times 2^{28}=(5\times 2^{7})^{4}=640^{4}\equiv (-1)^{4}=1}$ et ${\displaystyle F_{5}\equiv 0}$.
• Tout facteur premier p de F_n pour n > 1 peut s'écrire sous la forme s.2ⁿ⁺² + 1, où s est un entier.
  D'après la démonstration précédente, p est de la forme k.2ⁿ⁺¹ + 1. Édouard Lucas est allé plus loin :
  Comme n > 1, p est congru à 1 modulo 8. D'après la deuxième loi complémentaire de la loi de réciprocité quadratique, 2 est donc un résidu quadratique modulo p, c'est-à-dire qu'il existe un entier a tel que ${\displaystyle a^{2}\equiv 2{\pmod {p}}}$.
  Il est également possible de remarquer directement que 2 est un résidu quadratique modulo p, car

${\displaystyle \left(2^{2^{n-1}}+1\right)^{2}\equiv 2^{2^{n}}+1+2^{2^{n-1}+1}\equiv F_{n}+2^{2^{n-1}+1}\equiv 2^{2^{n-1}+1}{\pmod {p}}.}$
Comme une puissance impaire de 2 est un résidu quadratique modulo p, 2 lui-même en est un aussi.
On a alors ${\displaystyle a^{2^{n+1}}\equiv \ (a^{2})^{2^{n}}\equiv \ 2^{2^{n}}\equiv \ -1}$, et ${\displaystyle a^{2^{n+2}}\equiv \ 2^{2^{n+1}}\equiv \ 1{\pmod {p}}}$.
Ainsi l'ordre de a modulo p est égal à ${\displaystyle 2^{n+2}}$, et d'après le petit théorème de Fermat, p − 1 est donc divisible par ${\displaystyle 2^{n+2}}$ ; p peut alors s'écrire sous la forme ${\displaystyle s2^{n+2}+1}$.