Théorème de Fermat et applications

Petit théorème de Fermat et applications. Petit théorème de Fermat : Si p est un nombre premier, alors pour tout entier n, on a : [pic]. Démonstration 1:
. Si [pic] : [pic] est le produit de deux entiers consécutifs, donc l'un
des deux est pair, de sorte que [pic]soit encore [pic].
. Si p est impair : on fait une récurrence sur n : > Pour [pic], le résultat est immédiat.
> Pour [pic], on a :
[pic], d'après le binôme de Newton.
Or, pour [pic], [pic] est divisible par p.
En effet, [pic] , donc p divise [pic]. Or p est premier, donc premier avec
k < p , donc p divise [pic] pour [pic] ( théorème de Gauss).
Par hypothèse de récurrence, on a :
[pic], d'autre part : [pic] , donc :
[pic]
En conclusion [pic]. Démonstration 2 :
On procédera comme suit :
a) On montrera que, si n est divisible par p, alors [pic] est divisible par
p.
Si [pic], alors [pic] est un multiple de p.
b) Si n n'est pas divisible par p, on considère les [pic] entiers suivants
:[pic] ainsi que
leurs restes dans la division euclidienne par p, notés : [pic].
On montrera qu'aucun de ces restes n'est nul, (ce sont donc des entiers
compris entre 1 et[pic].) et qu'il n'y a pas deux de ces restes égaux :
. Si n n'est pas divisible par p, p est premier avec n et si un reste de la
division par p de [pic] était nul, d'après le théorème de Gauss, p
devrait diviser k. C'est impossible puisque [pic].
. Si les deux restes de la division par p de [pic] et [pic]étaient égaux,
alors la différence [pic] est divisible par n.
Si n n'est pas divisible par p, p est premier avec n et d'après le
théorème de Gauss, p doit diviser [pic]. Or [pic] et [pic], donc [pic].
On en déduit [pic] ; les nombres qui ont le même reste sont forcément
égaux. En multipliant membre à membre les congruences :
[pic], [pic], [pic], ..., [pic], on montrera que :
[pic], puis à l'aide du théorème de Gauss que [pic], et donc que :
[pic].
. Les restes étant les nombres compris entre 1 et [pic] écrits dans un
certain ordre, leur produit est bien [pic]. L'égalité [pic] signifie
que p divise [pic]. p étant premier avec [pic], le théorème de Gauss
indique que p divise [pic]c'est-à-dire : [pic] et donc aussi [pic].
En conclusion [pic] est divisible par p, que n soit ou non divisible par p. Remarque : il existe plus de 100 démonstrations de ce théorème. Corollaire :
Si p est un nombre premier et si [pic], alors[pic].
Démonstration :
D'après le théorème, [pic]. Or [pic]donc p divise[pic]. Quelques exercices d'arithmétique. Exercice 1 : Pour tout entier naturel n, [pic]. Exercice 2 : Pour tout entier n, 30 /[pic]. Exercice 3 : Montrer que quel que soit s ( ( (, il existe un entier n (n (
( ( ) tel que
[pic]admette au moins s diviseurs premiers distincts. Exercice 4 : résolution d'équation affine modulo p.
Soient a, b et p des entiers. Si p est un nombre premier et si[pic] ,
les solutions à l'équation [pic]sont de la forme [pic]où k ( (.
Réciproque fausse du théorème de Fermat : Nombres de Carmichael. Un entier [pic] est appelé nombre de Carmichael si n n'est pas premier et
si pour tout entier a premier avec n, [pic].
Propriété : Montrer que si [pic] ( où les [pic] sont des nombres premiers
distincts) et si
([pic] - 1) divise (n - 1) pour tout i, alors n est un nombre de
Carmichael. Application : Montrer que 561 est un nombre de Carmichael.
Solution : Soit a premier avec n alors pour tout i, [pic] ne divise pas a
de sorte que pour tout i
[pic]. Or [pic] - 1 divise n -1 donc [pic] soit encore [pic] divise
[pic] pour tout i.
Les nombres [pic] étant premiers entre eux deux à deux, nous
obtenons [pic] divise [pic] soit encore [pic].
561=3.11.17 et 2 divise 560, 10 divise 560, 16 divise 560 donc 561 est
un nombre de Carmichael. Remarque : On montre que la réciproque de cette propriété est vraie et que
tout nombre de Carmichael possède au moins trois facteurs premiers. 561 est
le plus petit nombre de Carmichael, les suivants étant 1105, 1729, 2465.
On sait depuis peu qu'il existe une infinité de nombres de Carmichael
(février 1992). Extension du petit théorème de Fermat. Théorème : Soient p et q deux nombres premiers et n un entier tel que
[pic]alors
[pic].
Démonstration :
[pic]entraîne [pic] et [pic]. En effet soit d un diviseur commun à n et p
alors d divise n et pq donc d divise [pic] donc d = 1. On raisonne de même
pour q.
[pic] et p premier entraîne : [pic] soit : [pic]. De même : [pic].
Ainsi p et q divisent [pic]. p et q étant premiers donc premiers entre eux
le produit pq divise [pic] soit [pic]. Remarque :1) Le cryptage à clef publique-clef privée (cryptage RSA) repose
entièrement sur ce
théorème.
2) Une application directe de ce théorème est la
résolution de l'équation
[pic]où p et q sont deux nombres premiers et [pic].
(Solution :[pic]) Test de Fermat Le petit théorème de Fermat énonce que, si p est premier, et si a n'est pas
un multiple de p :
a p-1 ( 1 [p]
Pour tester si n est premier, on peut donc choisir a < n (a est appelé base
du test), par exemple a = 2, et calculer an-1 [n] ; si le résultat est
différent de 1, n est certainement composite ; par contre, on ne peut rien
conclure de façon sûre si le résultat vaut 1, car la réciproque du petit
théorème de Fermat est fausse : il y a seulement une assez forte
probabilité pour que n soit premier. En recommençant le test pour d'autres
valeurs de la base a on améliore en général fortement la probabilité
d'obtenir une réponse correcte, lorsque n semble premier.
Lorsque a n-1 ( 1 [n], avec n composite, on dit que a est un menteur pour
n, ou que n est pseudo-premier pour la base a. Lorsque n est pseudo premier
pour tout nombre a, n est appelé nombre de Carmichael (voir ci-dessus).
Exemples : Les nombres pseudo-premiers inférieurs à 2000 :
Pour la base 2 : 341, 561, 645, 1105, 1387, 1729, 1905.
Pour la base 3 : il ne reste que 561, 1105, et 1729.
Ces trois derniers nombres sont des nombres de Carmichael et passent
le test de Fermat pour toute base a.
Ainsi il y a 3 chances sur 2000 que le test de Fermat se trompe sur
la primalité d'un nombre inférieur à 2000.
L'algorithme du test de Fermat est très rapide. La plupart des logiciels de
calcul formel utilisent cette méthode probabiliste ( le test de Fermat)
combinée avec d'autres tests probabilistes comme celui de Lucas.