Pierre Fermat (1607-1665) est un mathématicien particulier, il est devenu célèbre par l’annotation : «J’en ai découvert une démonstration véritablement merveilleuse que la marge est trop petite pour la contenir », placée en marge de l’énoncé d’un résultat que l’on appelle le Grand théorème de Fermat, rédigé par Fermat dans une édition de son époque des arithmétiques de Diophante :
« Diviser un cube en deux cubes, une puissance quatrième en deux puissances quatrièmes ou une puissance quelconque en deux puissances de même dénomination est impossible », c’est-à-dire en termes mathématiques actuels, « Pour tous entiers naturels $n > 2$, il est impossible de trouver un triplet $(x~;~y~;~z)$ d’entiers positifs non nuls tels que $x^n + y^n = z^n$», Fermat a démontré ce théorème uniquement dans le cas $n = 4$.
Il fallait attendre plus de trois siècles pour que le mathématicien britannique Andrew Wiles le démontre en 1994 dans le cas général.
Parmi les contributions les plus importantes de Fermat, compte surtout le petit théorème de Fermat qu'il le cite en 1640 dans l'une de ses lettres mais ne le démontre pas, ce théorème est l’objectif de ce chapitre.
Le petit théorème de Fermat est utilisé historiquement pour analyser la décomposition en produit de facteurs premiers pour certains entiers mais on trouve d’autres utilisations du petit théorème de Fermat en théorie algébrique des nombres, comme le théorème de Herbrand-Ribet, en utilisation pour l'étude les points fixes de l'endomorphisme de Frobenius par exemple, le test de primalité de Fermat et en la cryptographie voir le dernier exercice de ce chapitre.
Petit théorème de Fermat
Soient $p$ et $a$ deux entiers naturels tels que $a$ ne soit pas divisible par $p$.
Si $p$ est premier alors $a^{p-1}-1$ est divisible par $p$, c'est-à-dire que $a^{p-1} \equiv 1~[p]$.
Soient $p$ un entier naturel premier et $a$ un entier naturel tel que $a$ ne soit pas divisible par $p$.
-
Montrer que $p$ premier avec $(p-1)!$
On considère les $p-1$ premiers multiples de $a$ : $a,~2a,~3a,~...,~(p-1)a$.
On considère les restes de la division euclidienne de ces multiples de $a$ par $p$ : $r_1,~r_2,~r_3,~...,~r_{p-1}$.
-
Montrer que ces restes sont tous non nuls.
-
Montrer que ces restes deux à deux distincts.
-
-
En déduire que $a^{p-1}-1$ est divisible par $p$.
Le petit théorème de Fermat donne une condition nécessaire pour que $p$ soit premier. On dit qu'il constitue un test de primalité.
En effet, d'après le théorème de Fermat, pour tout entier naturel $n$ tel que $1\le n \le p-1$, si $p$ est premier alors $n^{p-1} \equiv 1~[p]$.
donc si pour un entier naturel $n$ inférieur à $p$, $n^{p-1}$ n'est pas congru à $1$ modulo $p$ alors $p$ n'est pas premier.
Mais ce test n'est pas efficace pour les grandes valeurs de $p$.
Le reste de la division euclidienne de $55^{44}$ par $23$ est $1$.
En effet, $23$ est premier et ne divise pas $55$.
D'après le petit théorème de Fermat,
$55^{22} \equiv 1~[23]$ ; dès lors, $(55^{22})^2 \equiv 1^2~[23]$
soit $55^{44} \equiv 1~[23]$.
Ainsi le reste de la division euclidienne de $55^{44}$ par $23$ est $1$.
Soient $p$ un entier naturel premier et $a$ un entier naturel quelconque.
Alors $a^{p} - a$ est divisible par $p$, c'est-à-dire que $a^{p} \equiv a~[p]$.
Cette propriété est une conséquence directe du petit théorème de Fermat.
Démontrer cette propriété.
Le reste dans la division euclidienne de $97^{33}$ par $11$ est 9, c'est-à-dire que $97^{33} \equiv 5~[11]$.
En effet, $11$ est premier, donc,
d'après la conséquence du petit théorème de Fermat,
$97^{11} \equiv 97~[11]$, soit $97^{11} \equiv 9~[11]$ car $97=8\times 11+9$.
Ainsi, $(97^{11})^3 \equiv 9^3~[11]$ soit $97^{33} \equiv 27~[11]$.
Comme $27 \equiv 5~[11]$, le reste de la division euclidienne de
$97^{33}$ par $11$ est $5$.
Un nombre de Carmichael est un nombre premier (composé) $n$ ($n>1$) tel que pour tout entier naturel $a$ premier avec $n$, $a^{n-1} \equiv 1~[n]$.
Ces nombres sont aussi appelés "menteurs de Fermat".
L'objectif de cet exercice est de démontrer que $561$ est un nombre de Carmichael.
-
Décomposer $561$ en produit de facteurs premiers
- Soit $a$ un nombre premier avec $561$.
-
Montrer que $a^{560} \equiv 1~[3]$
-
Montrer que $a^{560} \equiv 1~[11]$.
-
Montrer que $a^{560} \equiv 1~[17]$.
-
-
En déduire que pour tout entier naturel $a$ premier avec $561$, $a^{560} \equiv 1~[561]$.
Exercices
Dans chaque cas, déterminer le reste de la division euclidienne de $a$ par $b$.
-
$a=5^{31}$ par $b=7$.
-
$a=3^{35}$ par $b=7$.
-
$a=96^{97}$ par $b=17$.
-
$a=55^{27}$ par $b=23$.
Déterminer l\'entier naturel $k$, $0 \le k \le 6$ tel que : $2^{20} + 3^{30} + 4^{40} + 5^{50}+6^{60}\equiv k~[7]$.
Démontrer que pour tout entier naturel $n$, $n^{7}-n$ est divisible par $21$.
Démontrer que pour tout entier naturel $n$, $n^{21} \equiv n~[11]$.
$n$ est un entier naturel non nul.
-
Montrer que $n^5-n$ est divisible par 5.
-
Montrer que $n(n^2-1)(n^2+1)$ est divisible par 3.
-
En déduire que $n^5-n$ est divisible par 30.
$n$ est un entier naturel non nul.
-
Montrer que $n^{13}-n$ est pair.
-
Montrer que $n^{13}-n$ est divisible par 13 et 7.
-
Montrer que $n^{13}-n$ est divisible par $182$.
Démontrer que pour tous entiers naturels $a$ et $b$ et tout entier premier $p$, on a : $(a+b)^p \equiv a^p+b^p~[p]$.
On considère la suite $(u_n)_n$ définie pour tout entier naturel $n$ non nul par : $u_n = 2^n+3^n+6^n-1$.
-
Donner les quatre premiers termes de la suite.
-
Montrer que pour tout entier naturel $n$ non nul, $u_n$ est pair.
-
Montrer que pour tout entier naturel $n$ pair et non nul pair, $u_n$ est divisible par $4$.
-
Les entiers $2$, $3$, $5$ et $7$ appartiennent-ils à $(E)$ ?
Soit $p$ un nombre premier strictement supérieur à $3$.
-
Montrer que $6\times 2^{p-2} \equiv 3~[p]$ et $6\times 3^{p-2} \equiv 2~[p]$
-
En déduire que que $6\times u^{p-2} \equiv 0~[p]$
-
Le nombre $p$ appatient-il à l'ensemble $(E)$ ?
-
On note $(E)$ l'ensemble des nombres premiers qui divisent au moins un terme de la suite $(u_n)_n$
On considère la fonction Python suivante dont le paramètre $n$ est un entier naturel.
def carmichael(n):
c=0
d=0
for a in range(1, n) :
if gcd(n, a) == 1 :
c = c+1
p = 1
for k in range(1, n) :
p = (p*a) % n
if p == 1 :
d = d+1
return c == d -
Interpréter le résultat de la console suivante :
>>> carmichael(1105) True -
Démontrer ce résultat.
Cryptage RSA
Le système RSA est un système de cryptage pour échanger des messages codés. Il est constitué d'une clé publique pour coder et d'une clé privée pour décoder.
Notations. $p$ et $q$ sont deux nombres premiers. On pose $N=pq$ et $n = (p-1)(q-1)$ et on considère l'entier naturel $c$ premier avec $n$ et strictement inférieur à $n$.
Principe du RSA :
Un message $a$ doit être envoyé par Alice à Bob.
$c$ est la clé publique. Alice doit calculer $b$ tel que $a^{c} \equiv b~[N]$. $b$ est transmis à Bob.
Bob doit calculer $b^{d} \equiv a~[N]$ où $d$ est la clé privée. Donc Bob retrouve le message envoyé.
Partie A : utilisation du petit théorème de Fermat
-
Soit $a$ un entier naturel premier avec $p$ et $q$. Montrer , à l'aide du petit théorème de Fermat, que $a^{(p-1)(q-1)} \equiv 1~[p]$ et $a^{(p-1)(q-1)} \equiv 1~[q]$
-
Il existe donc un entier naturel $k$ et un entier naturel $k'$ tels que : $a^{(p-1)(q-1)} = 1+pk = 1+ pk'$. Montrer que $k$ est un multiple de $q$ et que $a^{(p-1)(q-1)} \equiv 1~[N]$.
-
Démontrer que, pour tout entier naturel a, si k est un entier naturel tel que $k \equiv 1~[n]$ alors $a^{k} \equiv a~[N]$.
Partie B : Détrmination de l'entier $d$
-
Justifier que l'équation $(E)$ : $cx-ny = 1$ admet des solutions.
-
Soit $(x_0~;~y_0)$ une solution particulière de $(E)$. Montrer que $(x~;~y)$ est solution de $(E)$ si, et seulement si $x=x_0+kn$ et $y=y_0+kc$ où $k$ est un entier naturel.
-
En déduire qu'il existe un unique entier naturel $d$ tel que $cd \equiv 1~[n]$.
Partie C : Conclusion
Déduire des parties A et B que, quels que soient les entiers naturels $a$ et $b$, $b \equiv a^c~[N]$ $\Rightarrow$ $a \equiv b^d~[N]$.
Demander le programme !
- une division euclidienne
- l'usage des propriétés opératoires des congruences
- La démonstration que deux entiers sont congrus modulo un entier
- Étudier des problèmes de chiffrement.
- Le petit théorème de Fermat.
- La conséquence du petit théorème de Fermat.
- La démonstration du petit théorème de Fermat.
- La démonstration de la conséquence du petit théorème de Fermat.
Les différents
auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative
Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0
International