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
- Calculer \(F_5\).
- Vérifier que le reste dans la division de \(F_5\) par \(641\) est zéro.
- Donner le quotient de \(F_5\) par \(641\).
- 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 !
- Calculer \(F_6\), avec la console Basthon ci-dessous.
- Vérifier que le reste dans la division de \(F_6\) par \(274\,177\) est zéro.
- Donner le quotient de \(F_6\) par \(274\,177\).
- 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.
- \(F_7\) est divisible par \(59\,649\,589\,127\,497\,217\). Factorisation de \(F_7\) obtenue en 1970.
- \(F_8\) à \(F_{11}\) ont pu être entièrement factorisés. Factorisation de \(F_{11}\) obtenue en 1988.
- En 2021, \(F_{12}\) n'est toujours pas factorisé entièrement.
Exercice⚓︎
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
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