ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Nombres pseudo-premiers              Programme JavaScript

Selon le petit théorème de Fermat, on sait que si p est un entier premier, alors pour tout entier naturel a, ap a même reste que a dans la division par p. En d'autres termes :

si p est premier, alors ap ≡ a [p]   (ou bien ap-1 ≡ 1  [p] )          Gauss

Ainsi :

si ap a [p], alors p est composé (c.à.d. non premier).

 Le petit théorème de Fermat peut servir de test de primarité (certains disent primalité), mais ce n'est pas un critère. Il n'est qu'une condition nécessaire pour tout candidat au statut de nombre premier.

Exemple bien connu :      

2341 ≡ 2  [341] et cependant 341 = 11 x 31

En effet : 341 = 11 x 31. Or 211 = 2048 ≡ 2  [341] puisque 2048 = 6 x 341 + 2

Ainsi :

2341 = (211)31 = (2048)31 ≡ 231  [341]

Or :

231 = 211 x 211 x 29 2 x 2 x 29 = 211 ≡ 2  [341]

On dit que 341 est un entier naturel pseudo-premier de base 2.

  Nombres de Poulet

D'une façon générale, on appelle nombre pseudo-premier de base a, tout entier composé p tel que  ap ≡ a.

Le statut de nombre pseudo-premier n'est pas bien défini :    

Certains mathématiciens y incluent les nombres premiers. D'autres exigent qu'ils soient impairs. D'autres ajoutent la condition pgcd(a,p) = 1, c'est à dire a et p premiers entre eux, dans la relation ap ≡ a [p]. Sous cette condition pour la base a, on obtiendrait :

On note que les nombres 561, 1105, 1729, marqués en rouge, sont pseudo-premiers pour les bases 2, 3 et 4. On est alors amené à considérer une condition plus forte mais encore insuffisante, à savoir les entiers naturels p vérifiant, pour toute base a < p, la relation ap ≡ a [p] :

Nombres de Poulet :                      Nombres de Carmichael :

Pour en savoir plus :

Programme pseudo-premiers en JavaScript

La recherche d'un nombre pseudo-premier est difficile et fastidieuse sans le recours à l'ordinateur et l'absence d'une telle machine à la disposition des grands mathématiciens qui se sont penchés sur les problèmes d'arithmétique depuis la nuit des temps, inspire le plus grand respect.

Le programme ci-dessous vous demandera la base a (entrer 2 pour un nombre de Poulet) et recherchera les nombres pseudo-premiers p impairs et composés (non premiers) de base a inférieurs à 10000. On commence à p = 9 car, en deçà, p serait soit pair, soit premier. La condition pgcd(a,p) = 1 est intégrée. On pourra la retirer en modifiant le test :

par simplement :



 La fonction prem() est identique à celle étudiée dans la recherche de primarité d'un nombre donné. La fonction pgcd() est identique à celle étudiée dans la recherche du pgcd par l'algorithme d'Euclide.

 Attention au temps de calcul pour n > 10000. Le programme recherche les nombres pseudo-premiers impairs à partir de n = 9.

<SCRIPT LANGUAGE=JavaScript>
var t
d=0;t=0;
function pseudo()
{
a$=2
a$=prompt("Donnez la base : ",a$)
if (a$==null || isNaN(a$)) {return} else {a=eval(a$)}if (a< 2 || a != Math.floor(a)) {return}
for (n=9;n<=10000;n=n+2)
{
t=prem();d=pgcd(n,a)
if (t==0 && d==1)
{
r1=a%n;rn=r1
for (i=2;i<=n;i++) {rn=(rn*r1)%n}
if (rn%n==r1) {if (!confirm(n+" est pseudo-premier de base "+a)) return}}
}
alert("terminé !")
}
 

function pgcd()
{
aa=a
bb=n
while (bb > 0)
{
r = aa % bb
aa = bb
bb = r
}
return aa
}

function prem()
{
d=0;k=1;t=1
if(n%2==0 || n%3==0) {t=0};while (d*d<=n && t==1)
{
d1=6*k-1;d2=6*k+1
if(n%d1==0 || n%d2==0) {t=0}
k++
d=d2
}
return t
}
</SCRIPT>

 

Nombres premiers jumeaux :
© Serge Mehl - www.chronomath.com