Petit théorème de Fermat

Nous avons mis au point sur le modèle du crible d'Eratosthène une méthode permettant de tester si un entier est premier ou non. Cela marche assez bien pour des petits nombres, mais cette méthode devient impraticable s'il s'agit de tester un entier d'une centaine de chiffres. Nous allons nous occuper dans cette section de deux problèmes imbriqués : d'une part trouver des méthodes permettant de vérifier rapidement si un nombre est premier et d'autre part réfléchir à d'éventuelles méthodes permettant de « fabriquer » des nombres premiers aussi grands que l'on veut.

« A thing of beauty is a joy for ever. Its loveliness increases; it will never Pass into nothingness » écrivait John Keats 217 ans après la naissance de Pierre de Fermat, dont le Petit Théorème demeure un joyau de la théorie des nombres, malgré les innombrables découvertes effectuées depuis dans ce domaine. S'il est qualifié de petit, c'est qu'une conjecture célèbre du même Fermat, restée indémontrée pendant des siècles, s'est accaparée le titre de Grand Théorème de Fermat.

$$x^n+y^n=z^n$$   n'a pas de solution dans $$\mathbb{N}^3$$   pour $$n>2$$

Dans la marge d'un manuscrit, Fermat prétendait en avoir trouvé la démonstration mais manquer de place pour l'écrire. Il a pourtant fallu attendre 1995 pour qu'Andrew Wiles le démontre en utilisant des outils surpuissants : l'entêtement d'une multitude de chercheurs a abouti à la démonstration de ce théorème, mais surtout a permis de développer d'importants outils en théorie des nombres. Quant à lui trouver des applications, le problème reste ouvert.

Au contraire, notre petit théorème, bien moins « médiatique » et à la démonstration abordable, a eu de très nombreuses et importantes conséquences : nous allons en étudier quelques-unes.

Mais tout d'abord, comment l'idée de son théorème est venu à l'esprit de l'ami Pierre ?

Au cours de ses nombreuses recherches, Fermat s'est intéressé aux nombres de Mersenne² qui sont les nombres de la forme $M_n=2^n-1$, avec $n$ un entier premier. On savait déjà que $M_{11}$ était composé

$$2^{11}-1=2047=23\times89 (i)$$

Mais c'est Fermat qui remarqua que

$$2^{23}-1=8388607=47\times178841 (ii)$$

Il sauta aux yeux de Fermat qui vivait parmi les entiers, que $47=2\times23+1$ en observant $(ii)$ ce qui lui mit la puce à l'oreille pour observer que $23=2\times11+1$ dans $(i)$. Qu'en dire ? Que le plus petit diviseur premier d'un nombre composé $2^p+1$ est de la forme $2p+1$ ?

Le problème, c'est que $2^{29}-1=536870911=233\times1103\times2089$, et donc, ça ne marche pas. D'ailleurs, ce n'est pas ce qui attira l'attention de Fermat. Il remarqua en effet que dans $(i)$, non seulement $23=2\times11+1$ mais aussi $89=8\times11+1$. De même dans $(ii)$, $47=2\times23+1$ et $178 481=7 760\times23+1$. Il conjectura donc que tout diviseur premier de $2^p-1$ est congru à 1 modulo $p$.

Mais l'ami Pierre ne s'arrêta pas là. On a $2^{11}\equiv 1[23]$, mais on a le même résultat avec $2^{22}$, $2^{33}$, etc. De même, $2^{11}$, $2^{22}$,...,$2^{88}$, etc. sont tous congrus à 1 modulo 89. Et puis $2^{23}$, $2^{46}$, etc. sont congrus à 1 modulo 47 et enfin $2^{23}$,..., $2^{178 480}$, etc. sont aussi tous congrus à 1 modulo $178 481$.

Oui, et alors. Et bien, pour ces quatre nombres premiers, on a $2^m\equiv 1[p]$, mais surtout, dans chaque cas, l'un de ces $m$ est $p-1$.

En bref, pour les nombres premiers 23, 89, 47 et 178481, on a $2^{p-1}\equiv 1[p]$. Est-ce vrai pour $tous$ les entiers ? Nous qui avons un bel ordinateur, menons une petite enquête :

$»$ fer:=proc(a,n) local k;

$»$ begin

$»$ for k from 1 to n do

$»$ [ithprime(k),pmod(a,ithprime(k)-1,ithprime(k))]; # ithprime(k) donne le kème nb premier

$»$ end_for; end_proc:

$»$ fer(3,15);

[[2, 1], [3, 0], [5, 1], [7, 1], [11, 1], [13, 1], [17, 1], [19, 1],

[23, 1], [29, 1], [31, 1], [37, 1], [41, 1], [43, 1], [47, 1]]

Occupons nous maintenant du théorème lui-même, énoncé pour la première fois par Fermat en 1640 dans une lettre adressée au fameux Frère Marin Mersenne.

Comme d'habitude, Fermat affirma avoir la démonstration mais ne pas avoir la place de l'écrire à son correspondant³

Il existe de très nombreuses démonstrations de ce théorème. Nous en verrons trois, une maintenant, une à titre d'exercice et une comme cas particulier d'un théorème plus général, le théorème d'Euler.

La plus rapide consiste à montrer que $a^{p-1}(p-1)!=a\times 2a\times 3a\times\cdots\times (p-1)a$ est congru à $(p-1)!$ modulo $p$ puis d'en déduire le résultat. Nous aurons besoin d'établir deux petites propriétés⁴.

Considérons donc les multiples successifs de $a$ jusqu'à $(p-1)a$ et appelons $r_k$ le reste de la division de $ka$ par $p$.

Et maintenant...une petite illustration MuPAD, évidemment...

On utilisera la fonction n mod d qui renvoie le reste de la division de n par d.

$»$ 2^(97-1) mod 97;

1

Choisissons maintenant un nombre premier quelconque grâce à la fonction nextprime

$»$ p:=nextprime(10^20);

100000000000000000039

puis un nombre entier quelconque inférieur à $10^{12}$

$»$ random();

321110693270

calculons $a^{p-1}$ modulo $p$

$»$ a^(p-1) mod p;

Error: Overflow/underflow in arithmetical operation

C'est trop gros : serions-nous donc encore une fois condamnés aux petits nombres ? Eh bien non, il est temps d'utiliser notre cerveau ! Et aussi l'algorithme d'exponentiation rapide vu précédemment.

$»$ pmod:=proc(a,n,p) local B,A;

$»$ begin

$»$ A:=a mod p: B:=1; # Pour simplifier car on travail modulo p

$»$ while n<>0 do

$»$ if n mod 2=0 then A:=(A*A mod p); n:=n/2 # si n pair, on élève au carré et on divise la puissance par 2

$»$ else B:=(B*A mod p); n:=n-1 # sinon, on enlève une puissance pour obtenir une puissance paire

$»$ end_if end_while;

$»$ B

$»$ end_proc:

Cette fois-ci on a la réponse, et en plus, instantanément !

$»$ pmod(321110693270,100000000000000000039-1,100000000000000000039);

1

Comme quoi, quand on arrive aux limites des possibilités calculatoires d'un ordinateur, rien ne vaut un bon cerveau.

C'est bien joli tout ça, amis à quoi ça peut servir ?

Prenons un grand nombre, assez compliqué pour avoir l'air premier, par exemple

$»$ n:=10^100*random()^3+32!+32*random()+13;

n:=17416995007052249019952126647441817600000000000000000000000000000000000000 0000000000000000000000000
0263130836933693530167241908282577229

Est-ce que ce nombre de 136 chiffres est premier ? Si tel est le cas, alors $2^{p-1}\equiv1 [p]$⁵

Jetons donc un coup d'œil

$»$ pmod(2,n-1,n);

10929185996403668155132301645171677938973308556359031603915090554003250963 7112385597262131870063544874
4642860847610628382268616793816279

Ouh la la, ça ne fait pas 1 ! Donc $n$ n'est pas premier, et la réponse a été donnée immédiatement, en quelques mili-secondes ! C'est quand même assez fort : on arrive, grâce au petit théorème de Fermat, à montrer qu'un entier de 136 chiffres pris au hasard n'est pas premier⁶.

Maintenant, que se passe-t-il si le résultat est effectivement 1 ? Cela fait-il de $n$ un nombre premier ?

Par exemple, vérifiez que $2^{341-1}\equiv 1 [341]$, et pourtant $341=11\times 31$. On dit que 341 est $pseudopremier$.

Voici un petit programme pour trouver les premiers nombres pseudo premiers :

$»$ pseudo:=proc(a,n) local i,L;

$»$ begin

$»$ L:=[];

$»$ for i from 3 to n step 2 do if not(isprime(i)) and pmod(a,i-1, i)=1 then L:=L.[i];

$»$ end_if; end_for:

$»$ L;

$»$ end_proc:

$»$ pseudo(2,2000);

[341, 561, 645, 1105, 1387, 1729, 1905]

$»$ pseudo(3,3000);

[91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821]

Pour des nombres plus grands, il n'est pas facile de savoir s'ils sont réellement premiers. Puisqu'on ne sait pas a priori s'ils le sont, on les appelle des nombres probablement premiers de base $a$. Certains sont PP d'une seule base. Par exemple

$»$ pmod(2,340,341)

1

$»$ pmod(3,340,341);

56

Ainsi, nous pouvons multiplier les bases pour éliminer les candidats. Malheureusement, il existe encore une infinité de nombres qui sont PP dans toutes les bases ,tout en étant composés :

Pour se donner un ordre de grandeur, il y a un peu plus d'un million de nombres premiers inférieurs à 25 milliards, mais seulement $21 853$ pseudo premiers et parmi eux $2 163$ nombres de Carmichael. C'est peu, mais c'est toujours trop !

Malheureusement, les choses se compliquent un peu par la suite et nous devons jeter l'éponge à notre niveau faute d'outils algébriques.

Nous pouvons seulement démontrer quelques lemmes menant à des tests fort puissants mais pour l'instant hors d'atteinte.