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 | nombres premiers

» Liens analogiques : nombres de Fermat , nombres de Mersenne , nombres de Carmichael , nombres puissants et nombres de Wieferich

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

Autrement dit : a^p - a est divisible par p. Ainsi :

s'il existe a entier tel que a^p ≡ 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 de nos jours primalité, le franglais ça fait tendance...), 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 :      

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

Ainsi :

Or :

On dit que 341 est un entier naturel pseudo-premier de base 2. Les chinois de l'antiquité se sont intéressés à ces nombres, raison pour laquelle on les appelle parfois nombres chinois. Ils furent étudiés au 20è siècle par Paul Poulet et Robert D. Carmichael.

 ➔   D'une façon générale, on appelle nombre pseudo-premier de base a, tout entier composé p tel que  a^p ≡ a [p]. Le statut de ces nombres 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 a^p ≡ a [p]. Sous cette dernière condition on obtiendrait :

• en base 2 : 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, ...  (nombres chinois ou  nombres de Poulet)
  » le plus petit nombre pair pseudo-premier de base 2 est 161038, découvert en 1950.
• en base 3 : 91, 121, 671, 703, 949, 1105, 1541, 1729, ...
• en base 4 : 15, 85, 91, 341, 435, 561, 645, 703, 1105, 1247, ..., 1729, 1891,...
• ...

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 a^p ≡ a [p] :

 ➔   Pour en savoir plus :

• Sur le site de Gérard Villemain : http://villemin.gerard.free.fr/ThNbDemo/PseudPre.htm
• Voir aussi : http://www.multimania.com/villemingerard/Premier/curiosit.htm

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 :

• if (t= =0 && d= =1) : si p est non premier et pgcd(a,p)=1

par simplement :

• if (t= =0) : si p est non premier

 ➔   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.