Nombres de Fermat, de Mersenne et d'Euclide
-
Nombres de Mersenne
Montrons la propriété par contraposée : supposons que $ n $ est composé, soit $ n = ab $ avec $ a > 1 $ et $ b > 1 $.
On factorise $ 2^n - 1 $ de la manière suivante : \[ 2^n - 1 = 2^{ab} - 1 = (2^a)^b - 1 = (2^a - 1) \sum_{k=0}^{b-1} 2^{ak} \] Puisque $ a > 1 $, on a $ 2^a - 1 > 1 $. De plus, $ b > 1 \implies \sum_{k=0}^{b-1} 2^{ak} > 1 $.
Le nombre $ 2^n - 1 $ admet donc des diviseurs stricts, il n'est pas premier. Ainsi, par contraposée, si $ 2^n - 1 $ est premier, $ n $ l'est nécessairement.
En base 2 : La somme géométrique donne $ 2^n - 1 = \sum_{k=0}^{n-1} 2^k $. Sa particularité est de s'écrire exclusivement avec une suite de $ n $ chiffres "1" (c'est-à-dire $ 111 \dots 11_2 $). -
Nombres d'Euclide
Soit $ m < n $. Par définition de la suite, $ e_n = e_1 e_2 \cdots e_m \cdots e_{n-1} + 1 $.
On peut réécrire cette relation sous la forme explicite de la division euclidienne de $ e_n $ par $ e_m $ : \[ e_n = q \cdot e_m + 1 \quad \text{avec} \quad q = \prod_{i=1, i \neq m}^{n-1} e_i \] L'algorithme d'Euclide donne immédiatement un reste égal à $ 1 $. Il se termine donc en une seule étape.
Si un entier $ d $ divise à la fois $ e_m $ et $ e_n $, il divise nécessairement leur combinaison linéaire $ e_n - q \cdot e_m = 1 $. Donc $ d = 1 $. Les nombres $ e_m $ et $ e_n $ sont bien premiers entre eux.
Déduction : Chaque nombre d'Euclide $ e_k $ admet au moins un diviseur premier $ p_k $. Puisque les nombres d'Euclide sont deux à deux premiers entre eux, tous les $ p_k $ sont distincts. La suite $ (e_k) $ étant infinie, il existe une infinité de nombres premiers. -
Nombres de Fermat
Raisonnons par l'absurde en supposant que $ n $ possède un diviseur impair $ b > 1 $. On pose $ n = ab $ avec $ a \geqslant 1 $.
On factorise $ 2^n + 1 $ en utilisant l'identité algébrique $ x^b + 1 = (x + 1) \sum_{k=0}^{b-1} (-1)^k x^k $ (qui est valable car $ b $ est impair) : \[ 2^n + 1 = (2^a)^b + 1 = (2^a + 1) \sum_{k=0}^{b-1} (-1)^k 2^{ak} \] Puisque $ a \geqslant 1 $, on a $ 2^a + 1 \geqslant 3 $. Le nombre $ 2^n + 1 $ est donc composé, ce qui contredit l'hypothèse. $ n $ n'admet aucun diviseur impair strictement supérieur à 1, c'est donc nécessairement une puissance de 2.
Primalité entre nombres de Fermat distincts :
Démontrons d'abord la relation $ \prod_{i=0}^{n-1} F_i = F_n - 2 $ par produit télescopique.
Pour tout $ k \geqslant 1 $, on peut écrire : \[ F_k - 2 = (2^{2^k} + 1) - 2 = 2^{2^k} - 1 \] En faisant apparaître une différence de carrés, on obtient : \[ F_k - 2 = (2^{2^{k-1}})^2 - 1^2 = (2^{2^{k-1}} - 1)(2^{2^{k-1}} + 1) \] On reconnaît immédiatement les termes de rang précédent : \[ F_k - 2 = (F_{k-1} - 2) F_{k-1} \implies \frac{F_k - 2}{F_{k-1} - 2} = F_{k-1} \] On effectue maintenant le produit pour $ k $ allant de $ 1 $ à $ n $ : \[ \prod_{k=1}^n F_{k-1} = \prod_{k=1}^n \frac{F_k - 2}{F_{k-1} - 2} \] Par simplifications successives (principe télescopique), le membre de droite devient $ \frac{F_n - 2}{F_0 - 2} $.
Sachant que $ F_0 = 2^{2^0} + 1 = 3 $, on a $ F_0 - 2 = 1 $. Sur le membre de gauche, un changement d'indice donne directement : \[ \prod_{i=0}^{n-1} F_i = F_n - 2 \] Soit $ m < n $. On déduit de cette relation que $ F_n = q \cdot F_m + 2 $ (en posant $ q = \prod_{i=0, i \neq m}^{n-1} F_i $).
Si un entier $ d $ divise $ F_n $ et $ F_m $, alors $ d $ divise la différence $ F_n - q \cdot F_m = 2 $. Or, tous les nombres de Fermat sont impairs, donc $ 2 $ ne divise pas $ F_m $. Par conséquent, la seule issue est $ d = 1 $. Deux nombres de Fermat distincts sont premiers entre eux.