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[1].

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^p² ≡ 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^p² = 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 \equiv 2$ , donc

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

De même, $2 abc \equiv 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.

Notes et références

Jean-Paul Delahaye, Merveilleux nombres premiers, 2012, 2^e éd. (ISBN 978-2-84245-117-2), p. 213.

Liens externes

Sur l'encyclopédie électronique des suites entières de Sloane on trouve :

Cette page (en anglais) donne beaucoup d'informations sur les nombres et supernombres de Poulet :

Pseudoprimes (Gérard Michon)

Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Jean-Paul Delahaye, Merveilleux nombres premiers, 2012, 2^e éd. (ISBN 978-2-84245-117-2), p. 213.