Nombre et supernombre de Poulet
# 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.

