# 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$_i$n$_j$ pour i ≠ j sont des nombres de Poulet ou premiers, alors n$_1$n$_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.