Nombre et supernombre de Poulet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un test de primalité courant pour un nombre impair n consiste à tester si n divise 2n – 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].

  • Un nombre composé n est donc un nombre de Poulet si n divise 2n – 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 2d – 2.

Exemples[modifier | modifier le code]

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

  • 211 – 2 est divisible par 11 ;
  • 231 – 2 est divisible par 31 ;
  • 2341 – 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[modifier | modifier le code]

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[modifier | modifier le code]

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 2p ≡ 2 mod p et 2q ≡ 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 2q – 2 et q divise 2p – 2.

Un nombre semi-premier de la forme p2 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).

(Super)nombres de Poulet à plus de deux facteurs premiers[modifier | modifier le code]

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

Soient n1, n2, … , nk premiers entre eux, avec k ≥ 3. Si tous les ni et tous les ninj pour ij sont des nombres de Poulet ou premiers, alors n1n2nk est un nombre de Poulet (donc de même en remplaçant « nombre(s) de Poulet » par « supernombre(s) de Poulet »).

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[modifier | modifier le code]

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[modifier | modifier le code]

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

Nombres de Poulet pairs[modifier | modifier le code]

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 avec premier, qui serait un nombre de Poulet. Or

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

divise

Or, d'après le petit théorème de Fermat, divise . On a alors divise , ce qui est absurde. Il n'existe donc pas de nombre de Poulet de la forme avec premier, et a fortiori pas de supernombre de Poulet pair.

Liens externes et sources[modifier | modifier le code]

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 :