Nombre et supernombre de Poulet

En arithmétique, un test de primalité courant pour un nombre impair $n$ consiste à tester si $n$ divise 2ⁿ – 2 : dans le cas contraire, en vertu de la contraposée 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 de Poulet, en l'honneur de Paul Poulet qui en a listé en 1926, ou nombres de Sarrus^{[réf. nécessaire]}, car F. Sarrus découvrit certains de ces nombres (comme 341) en 1819.

• Un nombre composé n est donc un nombre de Poulet si n divise 2ⁿ – 2, autrement dit si c'est un nombre faiblement pseudo-premier en base 2.
• Un supernombre de Poulet est un nombre composé dont tous les diviseurs composés sont des nombres de Poulet (ces diviseurs sont alors aussi des supernombres de Poulet), ou encore : un nombre composé dont chaque diviseur d divise 2^d – 2.

Exemples

L'entier 341 est un supernombre de Poulet car 2¹⁰ – 1 divisible par 341 = 11 × 31 donc 2^10k – 1 l'est aussi (pour tout entier positif k) et 2^10k+1 – 2 = 2 × (2^10k – 1) l'est également, en particulier :

• 2¹¹ – 2 est divisible par 11 ;
• 2³¹ – 2 est divisible par 31 ;
• 2³⁴¹ – 2 est divisible par 341.

Les nombres de Poulet semi-premiers étant des supernombres de Poulet, il suffisait en fait de vérifier le troisième point.

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 :

Nombres de Poulet Nombre Décomposition 341 11 × 31 561 3 × 11 × 17 645 3 × 5 × 43 1105 5 × 13 × 17 1387 19 × 73 1729 7 × 13 × 19 1905 3 × 5 × 127 2047 23 × 89 2465 5 × 17 × 29 2701 37 × 73 2821 7 × 13 × 31

Supernombres de Poulet Nombre Décomposition 341 11 × 31 1387 19 × 73 2047 23 × 89 2701 37 × 73 3277 29 × 113 4033 37 × 109 4369 17 × 257 4681 31 × 151 5461 43 × 127 7957 73 × 109 8321 53 × 157

Nombres de Poulet pairs Nombre Décomposition 161038 2 × 73 × 1103 215326 2 × 23 × 31 × 151 2568226 2 × 23 × 31 × 1801 3020626 2 × 7 × 359 × 601 7866046 2 × 23 × 271 × 631 9115426 2 × 31 × 233 × 631 49699666 2 × 311 × 79903 143742226 2 × 23 × 31 × 100801 161292286 2 × 127 × 199 × 3191 196116194 2 × 127 × 599 × 1289  209665666  2 × 7 × 89 × 197 × 881

On peut remarquer que les supernombres de Poulet présentés ici sont tous semi-premiers.

Nombres de Poulet semi-premiers

Tout nombre de Poulet semi-premier pq (où p et q sont deux nombres premiers, non nécessairement distincts) est un supernombre de Poulet. En effet, d'après le petit théorème de Fermat, les conditions supplémentaires 2^p ≡ 2 mod p et 2^q ≡ 2 mod q sont automatiquement satisfaites.

Par ailleurs, si p et q sont deux nombres premiers distincts, pq est un (super)nombre de Poulet si et seulement si p divise 2^q – 2 et q divise 2^p – 2.

Démonstration

D'après le petit théorème de Fermat, 2^pq = (2^q)^p ≡ 2^q mod p et de même, 2^pq ≡ 2^p mod q. La condition « 2^q ≡ 2 mod p et 2^p ≡ 2 mod q » est donc équivalente à « 2^pq ≡ 2 mod p et 2^pq ≡ 2 mod q ». Par conséquent, elle est impliquée par la condition « 2^pq ≡ 2 mod pq », et elle lui est même équivalente si p et q sont distincts, d'après le théorème des restes chinois.

Un nombre semi-premier de la forme p² est un (super)nombre de Poulet si et seulement si p est un nombre premier de Wieferich (on n'en connaît que deux : p = 1 093 et p = 3 511).

Démonstration

Si 2^p2 ≡ 2 mod p² alors p ≠ 2 donc (mod p²) 2 est inversible et son ordre multiplicatif est un diviseur de p² – 1. Or (théorème d'Euler) c'est aussi un diviseur de p² – p. C'est donc un diviseur de p – 1.

Réciproquement, si 2^p–1 ≡ 1 mod p² alors (mod p²) 2^p2 = 2^{1+(p–1)(p+1)} ≡ 2 × 1^p+1 = 2.

(Super)nombres de Poulet à plus de deux facteurs premiers

On peut construire des nombres et des supernombres de Poulet à plus de deux facteurs premiers de la façon suivante :

Soient n₁, n₂, … , n_k premiers entre eux, avec k ≥ 3. Si tous les n_i et tous les n_in_j pour i ≠ j sont des nombres de Poulet ou premiers, alors n₁n₂…n_k est un nombre de Poulet (donc de même en remplaçant « nombre(s) de Poulet » par « supernombre(s) de Poulet »).

Démonstration

Par récurrence, ils suffit de considérer le cas k = 3. Soient donc a, b et c trois nombres vérifiant ces conditions. Par hypothèse,

$2\equiv 2^{a}\mod a\quad {\rm {et}}\quad 2^{ab}\equiv 2\mod {ab}.$

Modulo a,on a donc :

$2^{b}\equiv (2^{a})^{b}=2^{ab}\equiv 2$

et de même, 2^c ≡ 2, donc

$2^{abc}=(2^{b})^{ca}\equiv 2^{ca}=(2^{c})^{a}\equiv 2^{a}\equiv 2.$

De même, 2^abc ≡ 2 modulo b et c, donc modulo abc puisque a, b et c sont premiers entre eux.

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.

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 distincts :

• 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 distincts :

• 1861, 5581, 11161, 26041, 37201, 87421, 102301, 316201, 4242661, 52597081, 364831561, 2903110321, 8973817381, 11292210661, 76712902561, 103410510721501, 29126056043168521, 3843336736934094661, 24865899693834809641, 57805828745692758010628581, 9767813704995838737083111101, 934679543354395459765322784642019625339542212601

Facteurs carrés

Il existe aussi des supernombres de Poulet qui ont des facteurs carrés, comme 1 093² × 4 733.

Nombres de Poulet pairs

On connaît 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

$2^{2p}-2=(2^{p}-2)(2^{p}+2)+2.$

Si c'est un nombre de Poulet, il est divisible par $2p$ : on en déduit que

$p$ divise $(2^{p}-2)(2^{p-1}+1)+1.$

Or, d'après le petit théorème de Fermat, $p$ divise $(2^{p}-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.

Voir aussi

Articles connexes

• Petit théorème de Fermat
• Hypothèse chinoise (consistant à croire que la conjecture " $n$ premier ssi $n$ divise 2ⁿ – 2" est d'origine chinoise ancienne)

Liens externes

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 :

• Pseudoprimes (Gérard Michon)