title: Nombre et supernombre de Poulet
text: # Nombre et supernombre de Poulet
  
  En arithmétique, un test de primalité courant pour un nombre impair n consiste à tester si n divise $2^n$ – 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, 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^n$ – 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^{10}$ – 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^{11}$ – 2 est divisible par 11 ;
  * $2^{31}$ – 2 est divisible par 31 ;
  * $2^{341}$ – 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'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^2$ 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).
  
  Si $2^{p2}$ ≡ 2 mod $p^2$ alors p ≠ 2 donc (mod $p^2)$ 2 est inversible et son ordre multiplicatif est un diviseur de $p^2$ – 1. Or (théorème d'Euler) c'est aussi un diviseur de $p^2$ – p. C'est donc un diviseur de p – 1.
  
  Réciproquement, si $2^{p–1}$ ≡ 1 mod $p^2$ alors (mod $p^2)$ $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_1,$ $n_2,$ … , $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_1n_2…n_k$ est un nombre de Poulet (donc de même en remplaçant « nombre(s) de Poulet » par « supernombre(s) de Poulet »).
  
  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^2$ × 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.
  
  