Nombres et supernombres de Poulet
Un article de Wikipédia, l'encyclopédie libre.
Un test de primalité courant pour un nombre impair n consiste à tester si n divise 2 n - 2 : dans le cas contraire, en vertu du petit théorème de Fermat, on conclut que n n'est pas premier. Cependant il existe des nombres composés qui passent ce test avec succès : on les appelle nombres pseudopremiers en base 2, ou encore nombres de Poulet, ou, également, nombres de Sarrus.
- Un nombre composé n est donc un nombre de Poulet si n divise 2 n - 2.
- Un supernombre de Poulet est un nombre dont chaque diviseur composé est un nombre de Poulet.
Un nombre composé n est donc un nombre de Poulet si tout diviseur d de n divise 2 d - 2. Si un tel diviseur d est composé, d est lui-même un supernombre de Poulet.
Sommaire |
[modifier] Exemples
Par exemple, 341 est un supernombre de Poulet : ses diviseurs positifs sont {1, 11, 31, 341} et on a :
Il est trivial que tous les nombres de Poulet n'ayant que deux facteurs premiers sont des supernombres de Poulet; c'est le cas de 341.
[modifier] Premiers nombres et supernombres de Poulet
Les premiers nombres et supernombres de Poulet et leur décomposition sont présentés dans les tables qui suivent :
|
|
|
Notez que les supernombres de Poulet présentés ici sont tous des nombres de Poulet à deux facteurs premiers.
[modifier] Nombres de Poulet à deux facteurs premiers
On l'a vu, les nombres de Poulet à deux facteurs premiers sont des supernombres de Poulet.
On peut également les caractériser comme suit : Soient p et q deux nombres premiers ; leur produit pq est un nombre de Poulet si, et seulement si, q divide 2p - 2 et p divise 2q - 2.
Reformulons le résultat avec le formalisme de l'arithmétique modulaire :
Rappelons que le petit théorème de Fermat assure que
On a donc
D'autre part, p et q étant premiers, par une application simple du théorème des restes chinois, on a l'équivalence suivante :
La conclusion est maintenant immédiate.
[modifier] Supernombres de Poulet à plus de deux facteurs premiers
On peut construire des supernombres de Poulet à trois facteurs premiers de la façon suivante :
- si p1 , p2 , p3 sont trois nombres premiers distincts tels que p1 p2 , p1 p3 , et p2 p3 sont des supernombres de Poulet, alors p1 p2 p3 est un supernombre de Poulet.
Par exemple, il est facile de lire dans le tableau ci-dessus que les nombres premiers 37, 73 et 109 conviennent. Leur produit : 294409 = 37×73×109 est un supernombre de Poulet.
On a également la généralisation suivante :
- Si p1 , p2 ,..., pn sont n nombres premiers distincts tels que tous les produits pi pj (avec i différent de j) sont des supernombres de Poulet, alors le produit p1 p2 ... pn est un supernombre de Poulet.
D'après la caractérisation donnée plus haut pour les nombres de Poulet à deux facteurs premiers, l'hypothèse peut se reformuler ainsi :
(pour i = j, c'est le petit théorème de Fermat.)
La preuve est par récurrence sur n.
Commençons par le cas n = 3. Les diviseurs composés stricts de sont des nombres de Poulet par hypothèse. Il reste à montrer que également.
On a
Les pi jouant un rôle symmétrique, on a de la même façon
Les pi étant des nombres premiers distincts, on en conclut que
Ceci conclut le cas n = 3.
Passons au cas général. L'hypothèse de récurrence entraîne de façon immédiate que tous les diviseurs composés stricts de sont des nombres de Poulet. Il reste à vérifier que est lui-même un nombre de Poulet. La preuve faite dans le cas n = 3 est facilement généralisable.
[modifier] Sept, huit facteurs premiers, et plus encore
Les familles de nombres premiers qui suivent permettent d'obtenir des nombres de Poulet avec jusqu'à sept facteurs premiers distints :
- 103, 307, 2143, 2857, 6529, 11119, 131071
- 709, 2833, 3541, 12037, 31153, 174877, 184081
- 1861, 5581, 11161, 26041, 37201, 87421, 102301 (*)
- 6421, 12841, 51361, 57781, 115561, 192601, 205441
Ces familles ci permettent d'aller jusqu'à huit facteurs premiers distincts :
- 1861, 5581, 11161, 26041, 37201, 87421, 102301, 316201 (*)
- 2383, 6353, 13499, 50023, 53993, 202471, 321571, 476401
- 2053, 8209, 16417, 57457, 246241, 262657, 279073, 525313
- 1801, 8101, 54001, 63901, 100801, 115201, 617401, 695701
Notez la parenté entre les deux lignes marquées (*) ci-dessus ! Cette liste de nombres premiers peut en fait être poursuivie jusqu'à vingt-deux nombres premiers disctincts :
- 1861, 5581, 11161, 26041, 37201, 87421, 102301, 316201, 4242661, 52597081, 364831561, 2903110321, 8973817381, 11292210661, 76712902561, 103410510721501, 29126056043168521, 3843336736934094661, 24865899693834809641, 57805828745692758010628581, 9767813704995838737083111101, 934679543354395459765322784642019625339542212601
[modifier] Facteurs carrés
Il existe aussi des supernombres de Poulet qui ont des facteurs carrés : en particulier, les carrés des nombres de Wieferich. On peut définir les nombres de Wieferich comme des nombres premiers p tels que p2 est un supernombre de Poulet ; on n'en connait que deux, p = 1093 et p = 3511. Ainsi, 10932 , 35112 sont des supernombres de Poulet, mais aussi 10932 × 4733, et d'autres.
[modifier] Nombres de Poulet pairs
On connait des nombres de Poulet pairs ; le plus petit d'entre eux, 161038 = 2 × 73 × 1103, a été découvert par Derrick Lehmer en 1950.
Il est par ailleurs assez facile de démontrer qu'il n'y a pas de supernombres de Poulet pairs. En effet, un tel nombre admettrait un diviseur composé de la forme 2p avec p premier, qui serait un nombre de Poulet. Or
Si c'est un nombre de Poulet, il est divisible par 2p: on en déduit que
p divise (2p − 2)(2p − 1 + 1) + 1.
Or, d'après le petit théorème de Fermat, p divise (2p − 2). On a alors p divise 1, ce qui est absurde. Il n'existe donc pas de nombre de Poulet de la forme 2p avec p premier, et a fortiori pas de supernombre de Poulet pair.
[modifier] Liens externes et sources
Sur l'encyclopédie électronique des suites entières de Sloane on trouve :
- La suite A001567 des nombres de Poulet
- La suite A050217 des supernombres de Poulet
- La suite A006935 des nombres de Poulet pairs
Cette page (en anglais) donne beaucoup d'informations sur les nombres et supernombres de Poulet :