A6 : Petit théorème de Fermat

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)!$

Code de déblocage de la correction :
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}$.
1. Montrer que ces restes sont tous non nuls.
  
  Code de déblocage de la correction :
2. Montrer que ces restes deux à deux distincts.
  
  Code de déblocage de la correction :
En déduire que $a^{p-1}-1$ est divisible par $p$.

Code de déblocage de la correction :

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

Code de déblocage de la correction :
Soit $a$ un nombre premier avec $561$.
1. Montrer que $a^{560} \equiv 1~[3]$
  
  Code de déblocage de la correction :
2. Montrer que $a^{560} \equiv 1~[11]$.
  
  Code de déblocage de la correction :
3. Montrer que $a^{560} \equiv 1~[17]$.
  
  Code de déblocage de la correction :
En déduire que pour tout entier naturel $a$ premier avec $561$, $a^{560} \equiv 1~[561]$.

Code de déblocage de la correction :

Exercices

Dans chaque cas, déterminer le reste de la division euclidienne de $a$ par $b$.

$a=5^{31}$ par $b=7$.

Code de déblocage de la correction :
$a=3^{35}$ par $b=7$.

Code de déblocage de la correction :
$a=96^{97}$ par $b=17$.

Code de déblocage de la correction :
$a=55^{27}$ par $b=23$.

Code de déblocage de la correction :

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.

Code de déblocage de la correction :
Montrer que $n(n^2-1)(n^2+1)$ est divisible par 3.

Code de déblocage de la correction :
En déduire que $n^5-n$ est divisible par 30.

Code de déblocage de la correction :

$n$ est un entier naturel non nul.

Montrer que $n^{13}-n$ est pair.

Code de déblocage de la correction :
Montrer que $n^{13}-n$ est divisible par 13 et 7.

Code de déblocage de la correction :
Montrer que $n^{13}-n$ est divisible par $182$.

Code de déblocage de la correction :

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.

Code de déblocage de la correction :
Montrer que pour tout entier naturel $n$ non nul, $u_n$ est pair.

Code de déblocage de la correction :
Montrer que pour tout entier naturel $n$ pair et non nul pair, $u_n$ est divisible par $4$.

Code de déblocage de la correction :

On note $(E)$ l'ensemble des nombres premiers qui divisent au moins un terme de la suite $(u_n)_n$

Les entiers $2$, $3$, $5$ et $7$ appartiennent-ils à $(E)$ ?

Code de déblocage de la correction :
Soit $p$ un nombre premier strictement supérieur à $3$.
1. Montrer que $6\times 2^{p-2} \equiv 3~[p]$ et $6\times 3^{p-2} \equiv 2~[p]$
  
  Code de déblocage de la correction :
2. En déduire que que $6\times u^{p-2} \equiv 0~[p]$
  
  Code de déblocage de la correction :
3. Le nombre $p$ appatient-il à l'ensemble $(E)$ ?
  
  Code de déblocage de la correction :

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]$

Code de déblocage de la correction :
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]$.

Code de déblocage de la correction :
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]$.

Code de déblocage de la correction :

Partie B : Détrmination de l'entier $d$

Justifier que l'équation $(E)$ : $cx-ny = 1$ admet des solutions.

Code de déblocage de la correction :
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.

Code de déblocage de la correction :
En déduire qu'il existe un unique entier naturel $d$ tel que $cd \equiv 1~[n]$.

Code de déblocage de la correction :

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

▲