Nombres premiers

Eric Wegrzynowski

(d'après Cours d'algèbre, M. Demazure, ed. Cassini, chap 2)

Introduction

Il existe une infinité de nombres premiers. Ce fait est bien connu depuis longtemps, puisqu'on en trouve la démonstration dans les éléments d'Euclide. Le plus grand nombre premier connu ce jour (10 XI 98) est le nombre

nombre gigantesque, puisqu'il s'écrit avec près d'un million de chiffres décimaux.

Parmi les plus grands nombres premiers connus, on en trouve plusieurs de la forme

Les nombres de cette forme sont connus sous le nom de nombres de Mersenne , en hommage à Marin Mersenne (1588-1648). Pour qu'un nombre de Mersenne soit premier, il faut que l'exposant le soit aussi. La réciproque n'est malheureusement pas vraie comme le montre l'exemple :

Une particularité de ces nombres est que leur écriture en base 2 est très simple : elle ne comprend que des 1, et il y en a . Nous allons nous intéresser aux nombres dont l'écriture en base 10 est identique.

Le problème

Il s'agit de rechercher quels sont les nombres premiers qui ne s'écrivent qu'avec des 1 en base 10. Par exemple, 1 n'est pas premier, 11 l'est, 111=3x37 ne l'est pas, 1111=11x101 ne l'est pas, 11111=41x271 ne l'est pas.

Nous notons un nombre qui s'écrit avec fois le chiffre 1 en base 10. Il est alors clair que l'on a

Cette égalité nous fournit une procédure pour générer de tels nombres :

> un := n -> (10^n - 1)/9;

> seq(un(k),k=1..10);

Remarques :

1) Il est clair que si on s'intéresse aux nombres de la forme avec un chiffre non nul autre que 1, aucun d'entre eux n'est premier si

2) La remarque précédente est vraie dans n'importe quelle base et on a

et dans le cas où , on retrouve les nombres de Mersenne.

3) Les seuls entiers n inférieurs à 9973 pour lesquels est premier sont : 2, 19, 23, 317, 1031.

Un premier critère

Hormis le cas où , aucun des nombres n'est premier si est pair. En effet, lorsque , est divisible par 11, le quotient s'écrivant avec fois le chiffre 1, en alternance avec des zéros .

Plus généralement si est un multiple de , avec , est divisible par .

Nous obtenons donc un premier critère :

Une condition nécessaire pour que soit un nombre premier est que soit premier .

Cette condition n'est pas suffisante puisque 111=3x37.

Dans la suite nous testerons la primalité des nombres lorsque est un nombre premier inférieur à 100.

> premiers := [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];

La recherche commence

Nous définissons une procédure de test de primalité qui teste la divisibilité de l'entier par tous les entiers successifs de 1 à . La procédure renvoie le plus petit diviseur autre que 1 de (cette procédure ne convient pas pour ).

> premier1 := proc(n)

> local k;

> k := 2;

> while n mod k<>0 and k*k<=n do k:=k+1; od;

> if n mod k = 0 then k else n fi;

> end:

> seq(premier1(k),k=1..20);

Retrouvons des résultats déjà établis :

> seq(premier1(un(k)),k=2..10);

Cherchons maintenant les nombres premiers lorsque est premier inférieur à 100.

> n:=7:f:=premier1(un(n));q:=un(n)/f; q*f;

n'est pas premier.

n'est pas premier.

> n:=11:f:=premier1(un(n));q:=un(n)/f; q*f;

> n:=13:f:=premier1(un(n));q:=un(n)/f; q*f;

> un(13)/53;

n'est pas premier

> n:=17:debut:=time():f:=premier1(un(n));tps_de_calcul:=time()-debut;q:=un(n)/f; q*f;

n'est pas premier. Le temps de calcul est long (près de 4 minutes sur un Pentium 166Mhz), cela provient de la taille du plus petit diviseur.

Ce temps de calcul aurait été encore plus long si ce nombre avait été premier. Il devient donc important de rechercher d'autres méthodes de test de primalité.

Une stratégie élaborée, mais ...

Un théorème dû à Legendre affirme que si et sont deux nombres premiers entre eux, et si est un facteur premier de qui ne divise aucun des lorsque divise et est distinct de , alors divise si est impair.

Ce théorème s'applique parfaitement à notre problème puisque on cherche à tester la primalité de

lorsque est premier impair. On a alors et , les facteurs premiers autres que 3 de sont de la forme , étant un entier positif. Ainsi, si est un nombre premier supérieur à 3, il faut chercher les facteurs premiers de parmi les nombres de la forme . D'où la procédure suivante (qui ne s'applique que pour de tels nombres) :

> premier2 := proc(n) #n est le nombre de 1 du nombre à tester

> local p,U;

> U := un(n);

> p := 2*n+1;

> while U mod p <> 0 and p*p<=U do p := p+2*n; od;

> if U mod p = 0 then p else U fi;

> end:

> premier2(5);premier2(7);premier2(11);premier2(13);

> debut:=time():premier2(17);tps_de_calcul:=time()-debut;

La réponse est obtenue beaucoup plus rapidement qu'avec la procédure premier1. On peut envisager de tester avec .

> n:=19:debut:=time():premier2(n);tps_de_calcul:=time()-debut;

Le nombre est premier ! Il aura fallu plus de 2h de calcul ! Si on veut tester le nombre , et si celui-ci est premier, il faudra approximativement 100 fois plus longtemps pour le déterminer. Cela provient du fait qu'en rajoutant 4 chiffres 1, on multiplie le nombre par environ 10000, et sa racine carrée par 100.

Cette méthode élaborée à partir du théorème de Legendre ne nous sera d'aucun secours dès que atteindra la trentaine. Il nous faut trouver d'autres stratégies.

Fermat intervient

Le petit théorème de Fermat stipule que si est un nombre premier, alors pour tout entier on a (modulo )

Appliqué à notre problème, cela donne : si est premier, alors pour tout entier on a (modulo )

En résumé, si est premier, alors pour tout entier on a modulo . Cependant la réciproque n'est pas vraie en général. Le théorème de Fermat nous permet donc de tester la non primalité d'un nombre.

La procédure qui suit nous permet de tester la non primalité des nombres , étant passé en paramètre, en prenant . Elle ne convient que pour car alors modulo .

> premier3 := proc(a,n)

> local a10n, k, U;

> U := un(n);

> a10n := a;

> for k from 1 to n do

> a10n := a10n^10 mod U;

> od;

> evalb(a10n=a^10 mod U);

> end:

Vérification des résultats déjà établis :

> premier3(2,5);premier3(2,7);premier3(2,11);premier3(2,13);premier3(2,17);premier3(2,19);

OK ! Passons aux nombres suivants :

> for k from 9 to nops(premiers) do

> if premier3(2,premiers[k]) then

> print(1&^[premiers[k]],` est peut-être premier`);

> else

> print(1&^[premiers[k]],` n'est pas premier`);

> fi;

> od;

Un temps de calcul tout à fait acceptable !

Hormis pour , aucun des nombres , premier inférieur à 100, n'est premier. De plus nous n'avons aucune certitude sur la primalité de .

Nous pouvons effectuer d'autres vérifications pour le cas , en prenant d'autres valeurs pour .

> for a from 3 to 10 do premier3(a,23) od;

Ce nombre semble bien résister au critère de Fermat. Cependant, nous ne pouvons pas conclure avec certitude qu'il est premier, car il est connu que certains nombres composés contredisent systématiquement ce critère : ces nombres sont nommés nombres de Carmichael . Les nombres de Carmichael sont les nombres composés , tels que, pour tout entier , on a (modulo )

Le plus petit d'entre eux est 561. Le calcul qui suit prouve qu'il s'agit bien d'un nombre de Carmichael.

> s:=0:for k from 2 to 560 do s:=s+((k^561 mod 561) -k)^2 od:s;

Conclusion : nous ne savons toujours pas si est premier ou non. En revanche, nous savons avec certitude qu'il n'existe que 2 ou 3 nombres premiers lorsque est inférieur à 100.

Probablement premier

Lorsque est un nombre premier, l'égalité stipulée par le théorème de Fermat, pour tout entier ,

peut encore s'écrire

En appliquant cette dernière égalité à , lorsque ce nombre est premier, on obtient

où .

Par conséquent si est premier, et si n'est pas un multiple de , on doit avoir ou .

On peut donc construire une procédure de test de primalité qui recherche l'existence d'un entier tel que et . Si la procédure trouve un tel entier, alors n'est pas premier, et cet entier est un témoin de la non primalité de .

Que dire si elle n'en trouve pas ? Un théorème, dû à Rabin, affirme que si est un nombre composé impair supérieur à 9, et si avec impair, alors il y a au plus entiers compris entre 1 et qui satisfont à la condition ou à l'une des conditions , avec , ( désignant le nombre d'entiers inférieurs à premiers avec ).

On en déduit qu'au moins des entiers compris entre 1 et témoignent de la non primalité de .

De ce résultat, on peut concevoir une procédure qui choisit au hasard un entier compris entre 2 et , et qui calcule . Si ce nombre est différent de 1 et -1, n'est pas premier. Sinon, il est premier avec une probabilité au moins égale à . Dans ce dernier cas, il suffit de recommencer l'opération pour soit trouver un témoin de la non primalité de , soit conclure qu'il est premier avec une probabilité au moins égale à . En recommençant éventuellement fois cette opération lorsqu'on ne trouve pas de témoin de non primalité, on pourra en conclure avec une probabilité au moins égale à que est premier.

> premier4 := proc(k,n)

> local alea,i,a,U,t,at;

> U := un(n);

> t := 5*un(n-1);

> alea := rand(2..U-1);

> i := 1;

> a := alea();

> at := a &^t mod U;

> while (i<k) and ((at=1) or (at=U-1)) do

> i := i+1;

> a := alea();

> at := a&^t mod U;

> od;

> if (at=1 or at=U-1) then

> print(` `.U.` est probablement premier`);

> else

> print(` `.U.` n'est pas premier. Témoin `=a);

> fi;

> end:

> premier4(10,17);premier4(10,19);

> premier4(50,23);

Conclusion : le nombre est premier avec une probabilité d'erreur inférieure à , c'est à dire inférieure à une chance sur mille milliards de milliards de milliards. L'usage d'une telle procédure fait apparaître une nouvelle catégorie de nombres : celles des nombres probablement premiers , ou encore, en reprenant la terminologie de M. Demazure, nombres premiers à usage commercial .

Autres premiers

> premier4(50,317);

>

>

>

>