Nombres de Fermat (2ème partie): comment montrer que F7 n’est pas premier ?

Conseil au lecteur avisé: il est recommandé d’avoir lu la première partie de cet article avant de se lancer dans celui-ci. Et puisque je me soucie sincèrement du bien-être de mes lecteurs, j’en profite aussi pour vous dire qu’il est recommandé de manger F_1 = 2^{2^1}+1 fruits et légumes par jour.

Dans la première partie de cet article, nous avions vu comment Euler avait réussi à montrer que le nombre de Fermat F_5=2^{2^5}+1 n’est pas premier, en déterminant une factorisation explicite de ce  nombre. Nous avions aussi vu que, malheureusement, cette méthode se révélait inefficace en pratique pour montrer que le nombre F_7=2^{2^7}+1 n’est pas premier. Mais, rassurez-vous, nous allons tout de même réussir à montrer que F_7 n’est pas premier, sans même avoir besoin de trouver sa factorisation !

Houston, on a un Pépin !

Il existe un test qui permet de prouver plutôt rapidement qu’un nombre de Fermat est ou n’est pas premier, qui s’appelle le test de Pépin, en l’honneur du mathématicien français Théophile Pépin (1826-1904). Ce test a permis de prouver que F_7 n’est pas premier pour la première fois en 1905 (par un certain J. C. Morehead), alors qu’un facteur explicite de ce nombre  n’a été trouvé que 65 ans plus tard ! Allez, sans plus attendre, voici le test de Pépin:

Soit F_n=2^{2^n}+1 pour n>0. Le nombre F_n est premier si, et seulement si,

3^{\frac{F_n-1}{2}} \equiv -1 \mod [F_n]

 

Là, vous êtes censés me dire « Mais d’où sort ce 3 ? » et moi je suis censé vous dire que cette question est légitime et qu’originellement, Pépin avait utilisé 5 à la place de 3. Et là, vous allez répondre: « Bon, on a toujours pas compris pourquoi ce 3, et en plus, d’où vient cet exposant au-dessus du 3 ? ». Et je vous répondrais d’être un peu patients, car on a tout l’article pour voir d’où tout cela vient, mais s’il y a une chose à retenir, c’est que ce test est basé sur le fait que 3 est (ou n’est pas) un carré modulo F_n, et est donc intimement lié à loi de réciprocité quadratique.

Avant de poursuivre, j’aimerais juste faire remarquer que 3 est toujours premier avec F_n lorsque n > 0. Cela provient d’une propriété dont on avait déjà parlé dans l’article précédent: deux nombres de Fermat (et 3 est un nombre de Fermat !) sont toujours premiers entre eux.

Condition suffisante

Commençons par montrer le sens le moins difficile du théorème de Pépin, à savoir: si 3^{\frac{F_n-1}{2}} \equiv -1 \mod [F_n] alors le nombre de Fermat F_n est premier. En prenant cette congruence au carré, on a:

\left(3^{\frac{F_n-1}{2}}\right)^2 \equiv (-1)^2 \mod [F_n]

ce qui donne 3^{F_n-1} \equiv 1 \mod [F_n]. Autrement dit, l’ordre de 3 modulo F_n divise F_n - 1 = 2^{2^n} donc est de la forme 2^k avec 0 \leqslant k \leqslant 2^n. Mais si on avait k < 2^n alors en prenant la relation 3^{2^k} \equiv 1 \mod [F_n] au carré autant de fois qu’il le faut (c’est-à-dire 2^n -1 - k fois), on trouverait

3^{2^{2^n - 1}} \equiv 1 \mod [F_n]

ce qui voudrait dire que 3^{\frac{F_n-1}{2}} \equiv 1 \mod [F_n] et donc cela contredirait notre hypothèse de départ. On a donc k=2^n, ce qui signifie que l’ordre de 3 est 2^{2^n} = F_n - 1. Autrement dit, quand on regarde modulo F_n les puissances:

3^0, 3^1, 3^2, \cdots, 3^{F_n - 2}

on obtient tous les nombres 1, 2, 3, \cdots, F_n-1 (pas forcément dans cet ordre, mais on les obtient tous. C’est bien ce que veut dire que l’ordre de 3 est F_n-1). Puisque chaque puissance 3^k est première avec F_n (car 3 est premier avec F_n), on en déduit que F_n est premier avec tous les nombres 1, 2, 3, \cdots, F_n-1. En particulier, F_n n’est divisible par aucun nombre strictement inférieur  à lui-même; c’est donc qu’il est premier !

Nous venons donc de montrer que le test de Pépin est suffisant pour prouver que F_n est premier; il nous reste à voir qu’il est aussi nécessaire. Mais avant cela, comme nous avons déjà beaucoup réfléchi et que la suite s’annonce un peu plus difficile, je vous propose de vous détendre un peu l’esprit en regardant cette petite vidéo d’un phoque qui tourne sur lui-même.

Interlude: le critère d’Euler et la loi de réciprocité quadratique

Avant de se lancer dans la condition nécessaire, il va nous falloir faire quelques rappels. Comme dit plus haut, le test de Pépin est fortement lié au fait que 3 est, ou n’est pas, un carré modulo F_n et, il se trouve qu’il existe un critère assez simple pour savoir si c’est le cas ou non: il s’agit du critère d’Euler (dont nous avions déjà parlé dans la première partie de l’article… vous comprenez pourquoi je vous ai demandé de lire cette première partie ? Si ce n’est pas encore fait, allez-y ! Et attention, je vous surveille…) Dans le cas qui nous intéresse ici, si on suppose que F_n est premier, le critère d’Euler s’énonce ainsi:

  • 3 est un carré modulo F_n si, et seulement si, 3^{\frac{F_n - 1}{2}} \equiv 1 \mod [F_n]
  • 3 n’est pas un carré modulo F_n si, et seulement si, 3^{\frac{F_n - 1}{2}} \equiv -1 \mod [F_n]

Pour énoncer ce critère plus simplement, on définit le symbole de Legendre \left( \dfrac{3}{F_n} \right) de la façon suivante:

\left( \dfrac{3}{F_n} \right) = \begin{cases} +1 \text{ si 3 est un carr\'e modulo } F_n \\ -1 \text{ si 3 n'est pas un carr\'e modulo } F_n \end{cases}

Le critère d’Euler s’écrit alors comme suit:

3^{\frac{F_n - 1}{2}} \equiv \left( \dfrac{3}{F_n} \right) \mod [F_n]

Ce qui va nous intéresser dans la suite va être de savoir pourquoi ce fameux symbole de Legendre vaut ici forcément -1. Et pour cela, nous aurons besoin de la belle loi de réciprocité quadratique…

Condition nécessaire

Montrons l’autre sens du théorème de Pépin: si on suppose que F_n est un nombre premier alors la loi de réciprocité quadratique nous dit que

\left( \dfrac{3}{F_n} \right) \times \left( \dfrac{F_n}{3} \right) = (-1)^{\frac{(3-1)(F_n -1)}{4}}

Autrement dit,

\left( \dfrac{3}{F_n} \right) \times \left( \dfrac{F_n}{3} \right) = (-1)^{\frac{2\times 2^{2^n}}{4}} = (-1)^{\frac{2^{2^n}}{2}}

Comme n>0, le nombre \frac{2^{2^n}}{2} est pair, ce qui donne \left( \frac{3}{F_n} \right) \times \left( \frac{F_n}{3} \right)=1. Ainsi, pour savoir si \left( \frac{3}{F_n} \right) vaut 1 ou -1, il suffit de déterminer le nombre \left( \frac{F_n}{3} \right), ce qui revient à savoir si F_n est un carré modulo 3 ou non. Comme 2 \equiv -1 \mod [3], pour tout entier n>0,

2^{2^n} \equiv (-1)^{2^n}=1 \mod [3]

ce qui signifie que F_n - 1 \equiv 1 \mod [3]. Ainsi, F_n \equiv 2 \mod [3]. Mais on sait que 2 n’est pas un carré modulo 3, car il n’apparait pas dans la deuxième ligne du le tableau suivant:

n \mod [3] 0 1 2
n^2 \mod [3] 0 1 1

 

Donc, F_n n’est pas non plus un carré modulo 3, c’est-à-dire \left( \frac{F_n}{3}\right) = - 1. Ainsi, en reprenant la relation que nous avait donnée la loi de réciprocité quadratique, on trouve que:

\left( \dfrac{3}{F_n} \right) \times (-1) = 1

et donc \left( \dfrac{3}{F_n} \right) = - 1. Le critère d’Euler nous dit alors que:

3^{\frac{F_n - 1}{2}} \equiv \left( \dfrac{3}{F_n} \right) = - 1 \mod[F_n]

ce qui montre bien que cette condition est nécessaire. Ouf, on y est arrivé ! Y avait quand même pas mal de bouleau… un vrai travail de pépiniériste ! (oui, je sais, cette expression n’existe pas. Et c’est bien dommage.)

Comment implémenter ce test en pratique ?

La théorie c’est bien beau, mais la pratique, c’est autre chose. Un des problèmes que l’on peut rencontrer pour appliquer ce test, est le fait qu’il faille calculer une très grande puissance de 3. Par exemple, si on souhaite appliquer le test de Pépin au cas du nombre de Fermat F_7, on sera amené à calculer:

3^{\frac{F_7-1}{2}} = 3^{2^{2^7-1}}=3^{2^{127}}

qui est un nombre absolument GIGANTESQUE (de l’ordre de 10^{10^{37}}). Il est évident que nous n’allons pas faire bêtement le produit 3 \times 3 \times \cdots \times 3 (où le nombre 3 apparaît 2^{127} fois !). Nous allons plutôt remarquer que:

3^{2^{127}} = (\cdots (3^2)^2)^2 \cdots )^2

où il y a 127 mises au carré (ce qui fait donc 127 multiplications… c’est qui est quand même  beaucoup plus raisonnable. Pour information, cela s’appelle la méthode d’exponentiation (MEGA-)rapide et l’idée est, comme vous le voyez, de réutiliser astucieusement les produits déjà effectués.)

Vous allez peut-être me dire que, peu importe le nombre de produits effectués, le résultat est toujours un nombre gigantesque. Ce à quoi je répondrai qu’il ne faut pas oublier que la seule chose qui nous intéresse dans le test de Pépin, c’est le reste modulo F_7 de ce nombre. Donc, à chaque étape, après avoir calculé le carré, on réduit le résultat obtenu modulo F_7 avant de reprendre à nouveau le carré du nombre obtenu. Voici une implémentation en Python de cet algorithme:

Test de Pépin

et voici ce que l’on obtient pour le nombre F_7:

test_de_Pepin_F7_pas_premierComme on le voit, il ne nous a fallu que quelques centièmes de secondes pour montrer que F_7 n’est pas premier ! Il n’y a bien entendu aucune raison de s’arrêter à n=7 alors voici ce que le test donne pour les nombres de Fermat qui suivent:

n F_n premier ? Durée du test (en s)
2 oui 0,008
3 oui 0,008
4 oui 0,008
5 non 0,008
6 non 0,008
7 non 0,008
8 non 0,008
9 non 0,017
10 non 0,045
11 non 0,269
12 non 1,881
13 non 13,591
14 non 104,444
15 non 817,277

 

Au-delà de F_{15}, mon pauvre petit PC commençait à mettre un peu trop de temps pour réaliser le test… mais ce n’est pas grave, nous voyons déjà qu’après F_4, les 11 nombres de Fermat qui suivent ne sont pas premiers. Et ça, c’est chouette ! Bon, c’est vrai qu’on le savait déjà pour F_5, F_6, F_9, F_{10}, F_{11} et F_{12} après la première partie de cet article (puisqu’on en avait trouvé des facteurs explicites), mais là nous l’avons prouvé pour F_{7}, F_8, F_{13}, F_{14} et F_{15}. Et tout cela, plutôt rapidement… c’est pourquoi je propose d’appeler cela le test de Pépin le Bref, et c’est sur cette blague hilarante que je vous laisse !

Notes:

✓ Vous pouvez voir sur la page Wikipédia anglaise l’historique des test de Pépin.
✓ Vous pouvez aussi consulter l’article original de J. C. Morehead (1905), où il explique qu’il a appliqué le test de Pépin au nombre F_7  et qu’il a trouvé (à la main !) que:

\begin{array}{cl} 3^{\frac{F_7 - 1}{2}} \equiv & \text{ 11078095439554051657911156260048860 \ } \mod F_7 \end{array}

qui est donc bien différent de -1 modulo F_7, comme on le voit (ou pas !). On ne blaguait pas avec les calculs à l’époque !

Advertisements
Cet article, publié dans Arithmétique, Nombres, est tagué , , , , , , . Ajoutez ce permalien à vos favoris.

3 commentaires pour Nombres de Fermat (2ème partie): comment montrer que F7 n’est pas premier ?

  1. Ping : Nombres de Fermat (1ère partie): Comment Euler a factorisé F5 ? | Blogdemaths

  2. microalg dit :

    Merci pour cet article.

    Petite coquille: «c’est sûr cette blague» -> «sur».
    «Aller» -> «Allez» (je crois).

    J’ai aussi des suggestions pour le code Python:
    1. Les premiers commentaires peuvent se faire sous la forme de docstring.
    2. https://docs.python.org/3/library/timeit.html
    3. Étrange cette fonction/procédure qui retourne et affiche à la fois. Surtout qu’ici, on ne se sert pas de la valeur de retour.

    Malheureusement pour moi, MicroAlg en version web n’utilise pas d’entiers arbitrairement grands, donc pas de Pépin pour le moment!

    Bonne continuation.

    • blogdemaths dit :

      Voilà, j’ai corrigé les coquilles !
      Ensuite, je dois signaler que je suis très loin d’être un spécialiste du Python. Les fonctions que j’écris sont plus pensées d’un point de vue mathématique que d’un point de vue programmation. Concernant cette fonction/procédure, il fallait en plus lui faire afficher quelque chose, pour des raisons pratiques liées à l’article (dire seulement que la fonction renvoie True est moins parlant et concret pour le lecteur !). Donc effectivement, j’aurais pu me passer de la valeur de retour.

      En tout cas, merci pour ces remarques constructives !

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s