Aller au contenu

Nombres de Fermat⚓︎

Définition⚓︎

Les nombres de Fermat1 sont de la forme \(F_n = 2^{2^n} + 1\), pour \(n\) entier.

Exemples⚓︎

\(F_0\) \(F_1\) \(F_2\) \(F_3\) \(F_4\)
\(2^1+1=3\) \(2^2+1=5\) \(2^4+1=17\) \(2^8+1=257\) \(2^{16}+1=65537\)

Information

  • \(F_0\), \(F_1\), \(F_2\), \(F_3\), \(F_4\) sont des nombres premiers.
  • Pierre de Fermat2 a conjecturé en 1640 que tous les nombres \(F_n\) sont premiers.

Exercice faisable avec une calculatrice

  1. Calculer \(F_5\).
  2. Vérifier que le reste dans la division de \(F_5\) par \(641\) est zéro.
  3. Donner le quotient de \(F_5\) par \(641\).
  4. Remarque : En 1732, le jeune Leonhard Euler, à qui Christian Goldbach avait signalé cette conjecture trois ans auparavant, la réfute : \(F_5\) est divisible par \(641\). Il ne dévoile la construction de sa preuve que quinze ans plus tard. Il y utilise une méthode similaire à celle qui avait permis à Fermat de factoriser les nombres de Mersenne \(M_{23}\) et \(M_{37}\).

Python devient très utile !

  1. Calculer \(F_6\), avec la console Basthon ci-dessous.
  2. Vérifier que le reste dans la division de \(F_6\) par \(274\,177\) est zéro.
  3. Donner le quotient de \(F_6\) par \(274\,177\).
  4. Remarque : En 1855, Thomas Clausen3 obtient avec ce quotient le plus grand nombre premier connu à cette époque.

Culture - une réelle difficulté

Au sujet des suivants4, on constate une difficulté très importante pour progresser.

  1. \(F_7\) est divisible par \(59\,649\,589\,127\,497\,217\). Factorisation de \(F_7\) obtenue en 1970.
  2. \(F_8\) à \(F_{11}\) ont pu être entièrement factorisés. Factorisation de \(F_{11}\) obtenue en 1988.
  3. En 2021, \(F_{12}\) n'est toujours pas factorisé entièrement.

Exercice⚓︎

Lien dans une autre page

Solution

Dans le script on complète return 2**(2**n) + 1

On clique sur Exécuter

Dans la console :

>>> F(4)
65537
>>> F(5) % 641
0
>>> F(6) % 274177
0
>>> F(5) // 641
6700417
>>> F(6) // 274177
67280421310721
>>> F(12) % 10**9
154190337

À savoir

  • def permet de déf-inir une fonction, ici avec un paramètre.
  • >>> F(5) est un appel de fonction qui renvoie \(F_5\) à la console, qui l'affiche.
  • Attention, ce n'est pas la fonction qui affiche \(F_5\), la fonction renvoie \(F_5\).
  • C'est la console qui affiche.
  • Nous le reverrons 😉.

Défi 💥

Quel est le 2021e chiffre en partant des unités de \(F_{13}\) ?

Indice 1

Pour enlever les 20 derniers chiffres, on peut faire F(13) // 10**20

Avec ce résultat, comment obtenir le dernier chiffre qui serait le 21e chiffre ?

Et pour le 2021e ?

Solution 1

>>> F(13) // (10**2020) % 10
1
Explication méthode 1 : Si on voulait avoir le 4e chiffre de \(123\,456\,789\) en partant des unités, on diviserait par \(10^3\), on obtiendrait \(123\,456\), puis on prendrait le reste dans la division par \(10\), pour obtenir \(6\).

Indice 2

Pour conserver les 21 derniers chiffres, on peut faire F(13) % 10**21

Enlever les 20 derniers chiffres à ce résultat donne le 21e chiffre de \(F_{13}\).

Et pour le 2021e ?

Solution 2

>>> F(13) % 10**2021 // 10**2020
Explication méthode 2 : Si on voulait avoir le 4e chiffre de \(123\,456\,789\) en partant des unités, on prendrait le modulo par \(10^4\), on obtiendrait \(6789\), puis on diviserait par \(10^3\), pour obtenir \(6\).