NOMBRES - Curiosités, théorie et usages

Accueil / Dictionnaire / Rubriques / Index / Atlas / Références /    Nouveautés

ORIENTATION GÉNÉRALE    -   M'écrire   -   Édition du: 25/04/2016

Débutants

Nombres

Premiers

Nombres PREMIERS

Glossaire

Nombres

Premiers

 

Recherche de PRIMALITÉ

 

 

 

Index des pages

NOMBRES PREMIERS

 

>>> INDEX

 

Crible d'Ératosthène

Presque-premiers

Carmichaël

Divisibilité

Pseudo Premiers

Carmichaël - Texte

Primalité

Liste pseudo-P.

 

Sommaire de cette page

 

>>> Cas de 561 - Définition

>>> Propriétés

>>> Valeurs

>>> Quantité et facteurs

>>> Historique

 

 

 

Nombres de Carmichaël ayant

>>> 3 facteurs premiers

>>> 4 facteurs premiers

>>> 5 facteurs premiers

>>> 6 facteurs premiers

>>> n facteurs premiers

 


 

 

NOMBRES de CARMICHAËL

ou pseudo-premiers absolus

  

Il y a des exceptions au test de Fermat: ce sont les nombres pseudo-premiers. Les nombres de Carmichaël sont de cette race.

 

 

CAS DE n = 561 et définition

 

Question

 

*           On a vu que de nombreux cas existent pour lesquels n n'est pas premier et pourtant D = a n-1 - 1 est divisible par n.

*           Dans le tableau des pseudo-premiers, on note que pour une valeur de n, il existe parfois plusieurs valeurs de a possibles. 

*           Existe-t-il des valeurs de n donnant la divisibilité de D = a n-1 – 1 quelle que soit la valeur de a?

 

Réponse     OUI !!!

*           Ce sont les nombres de Carmichaël

n = 561 est le plus petit

 

Définition

Nombre de Carmichaël

(1)   n est un nombre composé, appelé nombre de Carmichaël

(2)  Si a, premier avec n, prend toutes les valeurs possibles

(3)  Et D = a n - 1 - 1 est toujours divisible par n.

 

 

Testons n = 561 pour tous les a premiers avec n

a

n

D

 2

561

O.K. divisible

4

561

"

5

561

"

7

561

"

8

561

"

10

561

"

13

561

"

14

561

"

16

561

"

19

561

"

20

561

"

etc.

 

"

 

Note  Les valeurs numériques sont tout de suite faramineuses! 

 En effet:   a560 – 1 = 0,377 10169

 

 

 

 

Propriétés des nombres de Carmichaël

 

*           Cas de 561:  a560 – 1 est divisible par 561, pour tout a.

*           Cas de p:     an – 1  – 1 est divisible par n, pour tout a.

 

*           Ces nombres sont rares, mais il en existe une infinité. Démontré en 1994 par Alfort, Grandville et Pomerance.

*           Le plus petit est 561.

*           Il y a 105 212 nombres de Carmichaël inférieurs à 1015

 

*           Tous impairs.

*           Aucun facteur n'est un carré.

*           Trois facteurs au moins: donc produit de trois nombres impairs premiers:

 

Théorème

Le nombre n est un nombre de Carmichaël

si et seulement si

c'est le produit d'au moins trois nombres

premiers impairs différents

p1 , p2 , p3 , ...pk

et pour chacun de ces diviseurs,

n-1 est divisible par pi -1

 

Par exemple

*           561 = 3 x 11 x 17 et 560 est divisible par 2, 10 et 16.

 

 

 

 

NOMBRES de Carmichaël et facteurs

561

1 105

1 729

2 465

2 821

6 601

8 911

10 585

3 x 11 x 17

5 x 13 x 17

7 x 13 x 19

5 x 17 x 29

7 x 13 x 31

7 x 23 x 41

7 x 19 x 67

5 x 29 x 73

Suite

 

  

Quantité et facteurs

 

Quantité de Carmichaël                           infinité:  OUI

Quantité de Carmichaël à k facteurs      existent toujours: ?

Quantité de Carmichaël à 3 facteurs     infinité: ?

Quantité de Carmichaël à 3 facteurs     < 1012 = 1 000

Quantité de Carmichaël à k facteurs     < 1012 = 8 241

 

 

  

NOMBRE DE CARMICHAËL le plus petit

pour une quantité croissante de facteurs

Qté

n

 

Facteurs

2

n'existe pas

 

 

3

561

=

3 x 11 x 17

4

41 041

=

7 x 11 x 13 x 41

5

825 265

=

5 x 7 x 17 x 19 x 73

6

321 197 185

=

5 x 19 x 23 x 29 x 37 x 137

7

5 394 826 801

=

7 x 13 x 17 x 23 x 31 x 67 x 73

8

232 250 619 601

=

7 x 11 x 13 x 17 x 31 x 37 x 73 x 163

9

9 746 347 772 161

=

7 x 11 x 13 x 17 x 19 x 31 x 37 x 41 x 641

10

1 436 697 831 295 441

=

11 x 13 x 19 x 29 x 31 x 37 x 41 x 43 x 71 x 127

 

etc.

 

 

 

 

NOMBRES DE CARMICHAËL

à 3 facteurs premiers

Carmichaël

 

Facteurs premiers

PPCM*

561

=

3 x 11 x 17

80

1 105

=

5 x 13 x 17

48

1 729

=

7 x 13 x 19

36

2 465

=

5 x 17 x 29

112

2 821

=

7 x 13 x 31

60

6 601

=

7 x 23 x 41

1 320

8 911

=

7 x 19 x 67

198

10 585

=

5 x 29 x 73

504

15 841

=

7 x 31 x 73

360

29 341

=

13 x 37 x 61

180

41 041

=

 

 

46 657

=

13 x 37 x 97

288

52 633

=

7 x 73 x 103

1 224

62 745

=

 

 

63 973

=

 

 

75 361

=

 

 

101 101

=

 

 

115 921

=

13 x 37 x 241

720

126 217

=

 

 

162 401

=

17 x 41 x 233

2 320

172 081

=

 

 

188 461

=

 

 

252 601

=

 

 

294 409

=

37 x 73 x 109

216

314 821

=

13 x 61 x 397

1 980

334 153

=

19 x 43 x 409

8 568

399 001

=

31 x 61 x 211

840

488 881

=

37 x 73 x 181

360

512 461

=

31 x 61 x 271

540

530 881

=

13 x 97 x 421

3 360

1 152 271

=

43 x 127 x 211

630

1 193 221

=

31 x 61 x 631

1 260

1 461 241

=

37 x 73 x 541

1 080

4 335 241

=

53 x 157 x 521

1 560

5 968 873

=

43 x 127 x 1 093

3 276

14 913 991

=

43 x 127 x 2 731

8 190

15 247 621

=

61 x 181 x 1 381

4 140

17 098 369

=

113 x 337 x 449

1 344

17 316 001

=

53 x 157 x 2 081

6 240

23 382 529

=

97 x 193 x 1 249

2 496

60 957 361

=

61 x 181 x 5 521

16 560

362 569 201

=

113 x 337 x 9 521

28 560

 En jaune, la plus petite valeur pour ce nombre de facteurs

PPCM* au sens des gaussiens 

 

NOMBRES DE CARMICHAËL

à 4 facteurs premiers

Carmichaël

 

Facteurs premiers

PPCM*

41 041

=

7 x 11 x 13 x 41

120

62 745

=

3 x 5 x 47 x 89

2 024

63 973

=

7 x 13 x 19 x 37

36

126 217

=

7 x 13 x 19 x 73

72

172 081

=

7 x 13 x 31 x 61

6O

188 461

=

7 x 13 x 19 x 109

108

670 033

=

7 x 13 x 37 x 199

396

748 657

=

7 x 13 x 19 x 433

432

838 201

=

7 x 13 x 61 x 151

300

852 841

=

11 x 31 x 41 x 61

120

997 633

=

7 x 13 x 19 x 577

576

1 033 669

=

7 x 13 x 37 x 307

612

1 082 809

=

7 x 13 x 73 x 163

648

2 100 901

=

11 x 31 x 61 x 101

300

4 909 177

=

7 x 13 x 73 x 739

2 952

8 341 201

=

11 x 31 x 61 x 401

1 200

10 837 321

=

11 x 31 x 61 x 521

1 560

16 046 641

=

13 x 37 x 73 x 457

1 368

27 062 101

=

11 x 31 x 61 x 1301

3 900

33 302 401

=

11 x 31 x 61 x 1601

4 800

37 354 465

=

5 x 29 x 73 x 3 529

3 528

43 286 881

=

11 x 31 x 61 x 2 081

6 240

 

 

 NOMBRES DE CARMICHAËL

à 5 facteurs premiers

Carmichaël

 

Facteurs premiers

PPCM*

825 265

=

5 x 7 x 17 x 19 x 73

144

101 957 401

=

7 x 13 x 19 x 109 x 541

540

1 150 270 849

=

7 x 13 x 19 x 577 x 1 153

1 152

7 103 660 473

=

7 x 13 x 19 x 109 x 37 693

37 692

 

 

 

NOMBRES DE CARMICHAËL

à 6 facteurs premiers

Carmichaël

 

Facteurs premiers

PPCM*

321 197 185

=

5 x 19 x 23 x 29 x 37 x 137

94 248

1 039 531 253 629 141

=

7 x 13 x 19 x 109 x 541 x 10 195 741

10 195 740

 

 

 

 

Robert Carmichaël (1879-1967)

et historique

 

*           En octobre 1640, dans une lettre à Frenicle, Fermat écrit que

 

p divise ap – a pour tout a, dès que p est premier.

 

*           La question qui se pose: est-ce que seuls les premiers satisfont ce critère?

*           En 1899, Korselt avait mis en évidence un critère de test pour caractériser de tels nombres:

 

n divise an – a pour tout a si et seulement si n est un nombre sans carré et p – 1 divise n – 1 pour tout premier p divisant n.

 

*           En 1910, Carmichaël montre que 561 = 3 x 11 x 17 divise a561 – a pour toute valeur de a.

*           Carmichaël se plonge dans l'étude de ces nombres et développe un algorithme qui permet de construire de tels nombre, nommés nombres de Carmichaël. Il a l'intuition que ces nombres sont en quantité infinie.

*           En 1939, Chernick trouve une manière de les construire:

 

Si p = 6m, q = 12m +1 et r = 18m + 1 sont tous trois premiers, alors N = p.q.r et un nombre de Carmichaël.

 

*           Alors, on peut en créer une infinité?
On aurait dénombré plus de 100 000 nombres de Carmichaël jusqu'à 1015. Bonne piste, mais pas une preuve.

*           En 1992, W.R. Alford, Andrew Granville et Carl Pomerance démontrent que les nombres de Carmichaël sont en quantité infinie en prouvant  que:

 

Pour x suffisamment grand, il existe plus de x2/7 nombres de Carmichaël.

 

 

 

 


 

Suite

*    Carmichaël - Texte

*    Nombres premiersIndex

Voir

*    Modulo & Congruences

*    Nombres Premiers

*    Petit théorème de Fermat

*    Presque premiers

*    Pseudo Premiers Absolus

*    Théorie des nombres

Référence

*    Les listes données ci-dessous viennent en majorité de M. Pierre BARDONNET, auteur du texte sur les nombres de Carmichaël.