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: 08/03/2010

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

>>> Les nombres extraordinaires de Carmichaël

>>> Approche avec le corps z7

>>> Suite avec l'anneau z15

>>> Le nombre de Carmichaël: 561

>>> Réciproque du théorème de Fermat

>>> Nombres de Carmichaël à deux facteurs

>>> Structure du nombre de Carmichaël 561

>>> Recherche des nombres de Carmichaël - cas de 341

>>> Réciproque du théorème de Fermat

>>> Conclusions

 


 

 

Les nombres extraordinaires

 de Carmichaël

 

 

Texte de M. Pierre BARDONNET – Novembre 1999

Avec tous mes remerciements.

 

 

 

 

Les nombres de CARMICHAËL

 

*      Fermat et son petit théorème :

 

Si p est premier,

a p – a est divisible par p,

quel que soit a.

Il s'agit bien sûr d'un nombre a entier.

 

*      Jean ITARD, dans Théorie des Nombres dit que le théorème de Fermat n'a pas de réciproque.

*      Il cite 341 qui est pseudo-premier pour le reste 2, puisque 2341 - 2 est divisible par 341, et il ajoute que Carmichaël a découvert des nombres, tels que 561, qui sont pseudo-premiers pour tout reste premier avec 561; et il ajoute enfin qu'à la puissance 561 tout l'anneau se trouve reconstitué, comme dans le cas des corps Z/p.

 

 

 

 

OBJET de cette page

 

1) Expliquer le mécanisme des nombres de Carmichaël en se servant de l'exemple Z/561, et comparer les différences entre un nombre de Carmichaël, un anneau tel que Z/15 et un corps Z/p.

2) Montrer qu'on ne peut pas trouver de nombres de Carmichaël du type  .

3) Montrer que 561 est le seul Carmichaël du type 3 .

4) Citer des exemples de nombres de Carmichaël à trois, quatre, cinq et six facteurs premiers.

5) Quel doit être le véritable énoncé de la réciproque du petit théorème de FERMAT ?

 

Pour se familiariser, si nécessaire, voir d'abord:

Modulo et congruences

Divisibilité des puissances (Fermat)

 

 

 APPROCHE avec le CORPS Z7

 

Étudions d'abord le corps Z/7

*      On dit corps, car chaque reste a un inverse :

1 et 6 sont leurs propres inverses, car
1 x 1 = 1, 6 x 6 = 36
 1 (modulo 7) ;
2 x 4 = 8                    
 1 (mod. 7) ;
3 x 5 = 15                  
 1 (mod. 7).

 

Voici le tableau de puissances de Z/7

*      Nous n'avons fait figurer que les résidus des puissances, modulo 7.

 p = 7

1

2

3

4

5

6

Puissance 2

1

4

2

2

4

1

Puissance 3

1

1

6

1

6

6

Puissance 4

1

2

4

4

2

1

Puissance 5

1

4

5

2

3

6

Puissance 6

1

1

1

1

1

1

Puissance 7

1

2

3

4

5

6

Pour la notation: se reporter à Z7

 

Trois remarques s'imposent

 

*      Le corps est complètement reconstitué à la rangée des puissances 7 : ce qui montre bien qu'on a par exemple 27 – 2  0 (mod. 7) ; d'ailleurs 27 = 128, et l'on a bien 128 – 2 = 7 x 18.

*      À la rangée p – 1 = 6, il n'y a que des "1" : c'est le Théorème de Fermat.

*      Les rangées de puissances 1, 2, 3 et 6 où apparaissent pour la premières fois des "1" sont toutes des diviseurs de p – 1 = 6. On appelle ces exposants 1, 2, 3 et 6, les gaussiens du corps.

 

 

SUITE avec l'ANNEAU Z15

 

Voyons maintenant ce qui se passe pour l'anneau Z/15

*      On dit anneau parce qu'ici seuls les restes premiers avec 15 possèdent un inverse :

  2 x 8   =   16  1 (mod. 15) ;

  4 x 4   =   16  1 (mod. 15) ;

  7 x 13 =   91  1 (mod. 15) ;

11 x 11 = 121  1 (mod. 15) ;

14 x 14 = 196  1 (mod. 15).

 

*      Un nombre tel que 6 ne peut avoir d'inverse, car 6x = 1 + 15k entraînerait la divisibilité de 1 par 3.

 

Voici le tableau de puissances limité à la rangée 5

 

 p = 15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Puissance 2

1

4

9

1

10

6

4

4

6

10

1

9

4

1

Puissance 3

1

8

12

4

5

6

13

2

9

10

11

3

7

14

Puissance 4

1

1

6

1

10

6

1

1

6

10

1

6

1

1

Puissance 5

1

2

3

4

5

6

7

8

9

10

11

12

13

14

 

*      Le gaussien maxi est ici 4, car il est égal au PPCM de 2 et 4 qui sont les p – 1 de 3 et 5 respectivement.

 

Quatre remarques s'imposent

*      L'anneau est entièrement reconstitué à la rangée de puissance 5.

*      La puissance 4 ne divise pas p – 1 = 14.

*      Il existe quatre "1" en rangée 2 : cela vient du fait qu'il y a deux facteurs premiers dans Z/15. Néanmoins les rangées gaussiennes sont 1, 2 et 4 qui sont tous des diviseurs de 4, le gaussien maxi.

*      Les restes non premiers avec 15 ont des périodes 1, 2 et 4 qui divisent également le gaussien maxi.

 

 

LE NOMBRE de CARMICHAËL 561

 

Et maintenant, voyons ce qui se passe

pour le Carmichaël 561

 

*      561 = 3 x 11 x 17, et le PPCM des a – 1, b – 1, g – 1 qui sont égaux respectivement à 2, 10 et 16 est égal à 80.

*      Or, il se trouve que 80 est contenu un nombre entier de fois dans 560, puisque 560 = 80 x 7.

*      Le gaussien maxi de l'anneau divise donc 561 – 1, et tous les restes premiers avec 3, 11 et 17 seront donc congrus à 1 modulo 561 à la rangée 560.

*      Quant aux restes non premiers avec 561, ils auront une période qui sera un diviseur de 80.

 

Prenons par exemple le reste 3

*      Il a le gaussien maxi 80 dans l'anneau Z/187 (187 = 11x17).

*      En effet, le PPCM des gaussiens de 11 et de 17 est le PPCM de 10 et 16 qui vaut 80.

*      On pourra donc écrire :  380 = 1 + k . 187
et en multipliant par 3 :   381 = 3 + k . 561

 

*      Ceci montre bien qu'en rangée de puissance 81,le reste 3 recommence une nouvelle période.

*      Il en est de même pour le reste 11 qui a une période de 16 : 
11, 121, 209, 55, 44, 484, 275, 781, 176, 253, 539, 319, 143, 451, 473, 154 / 11, etc.

*      Le reste 17 a une période de 10 termes :
17, 289, 425, 493, 527, 544, 272, 136, 68, 34 / 17, etc.

 

Remarquons que

*      Tous les résidus des puissances de 3, 11 et 17 sont divisibles respectivement par 3, 11 et 17.

*      Toutes les périodes, en tout cas, divisent 80, et en rangée 560, tous les restes non-premiers avec 561 vont arriver en fin de période.

*      Donc, en rangée 561, tout l'anneau sera reconstitué, et l'on pourra écrire :    A561 - a  0 (modulo 561)

 

 

RÉCIPROQUE DU THÉORÈME DE FERMAT

 

*      La réciproque du théorème de FERMAT est ainsi mise en échec.

*      Il est possible de trouver des restes non-premiers avec 561, qui ont des périodes 2, 4, 5, 8, 10, 16, 20, 40 et 80.

 

Par exemple

*      Le reste 441 qui est le quarantième terme de la période de 3, a la période 2 :441, 375 / 441, etc.

*      De même le vingtième terme de cette même période de 3 qui vaut 540 donne 540, 441, 276, 375 / 540, etc. donc une période de 4 termes.

 

 

 

Nombres de Carmichaël à deux facteurs

 

Il est impossible de trouver un nombre de Carmichaël

composé des deux seuls facteurs premiers ab.

 

Supposons en effet

*      Qu'on puisse en construire un avec deux facteurs premiers seulement :

 – 1 = 2x m P

 – 1 = 2y m Q

m étant la partie commune impaire entre  -1 et  -1

PQ = 1.

*      On suppose de plus x  y.

Le PPCM ( -1,  -1) est donc 2x m P Q, et l'on devrait avoir :

  - 1 = (2x m P + 1) (2y m Q + 1) - 1 = K x 2x m P Q

ou encore

2x m P + 2y m Q + 2xy m2 P Q = K x 2x m P Q

 

*      Après simplification par m, on voit, par exemple, queP divise tous les termes de cette équation, sauf le deuxième, ce qui est impossible, puisque P et Q sont premiers entre eux par construction.

*      Un nombre de Carmichaël comporte donc au moins trois facteurs premiers.

 

De même

 

Il n'est pas possible d'avoir

un nombre de Carmichaël du type  2

*      Car le gaussien maxi de Z/ 2 est  ( – 1).

En effet, on a par hypothèse, a – 1 = 1 + K.

En élevant à la puissance a, on obtient :

A ( – 1) = 1 +  K + K' 3 + . . .

*      Ce qui montre bien que le gaussien maxi dans Z/ 2 est  ( – 1).

*      Dans ces conditions, on va avoir  2 – 1  – 1 modulo .

Et l'on voit que cette expression ne sera pas divisible par .

*      Un nombre de Carmichaël ne peut donc comporter un carré, ni un facteur premier à une puissance quelconque.

 

 

 

Structure du nombre de Carmichaël 561

 

561 est le seul nombre de Carmichaël

du type 3

 

Remarquons tout d'abord

*      Qu'on ne peut associer à 3 que des nombres premiers congrus à – 1 modulo 3.

*      En effet, si  = 3k + 1, on va avoir :

M – 1 = 3 x (3k + 1) x  – 1  –1  (mod. 3)

*       Donc le gaussien maxi de 3k+1qui est égal à 3k ne sera pas contenu un nombre entier de fois dans M-1.

 

Plus généralement,

*      On ne peut pas associer deux facteurs premiers dont l'un est un multiple + 1 de l'autre.

*      Ainsi, on ne peut associer 7 et 29, 11 et 23, etc.

On a donc à étudier les solutions

A = 3 ; B = 3k - 1 ;  C = 3m - 1.

*      On suppose toujours les facteurs premiers rangés par ordre croissant : A < B < C

D'autre part,

*      Si on a :            A B C – 1 = k . PPCM(A – 1, B – 1, C – 1)
on en déduit a fortiori :   A B C – 1 = K(C – 1)
d'où:                         C = (K – 1) / (K – AB)

Il faut aussi que l'on ait

*      K > AB pour que C soit positif.
K = AB + 1, correspond à C = AB qui n'est pas premier.

On incrémente ensuite K

*      En faisant K = AB + 2, AB + 3, etc.

On s'aperçoit

*      Que la fonction C(K) décroît très vite.

Souvent,

*      On aboutit à des valeurs fractionnaires qu'il faut bien sûr rejeter, ou à des valeurs qui ne sont pas des nombres premiers.

De toute façon,

*      Il faudra vérifier que toutes les conditions pour obtenir un nombre de Carmichaël sont bien vérifiées.

On peut faire une autre remarque

*      Les solutions du type K = AB + 3 ne peuvent convenir, car on obtient C = (AB + 2) / 3, et AB étant divisible par 3, AB + 2 ne l'est pas.

Les solutions

*      Du type K = AB + 4, donnent C = 3(B + 1) / 4 < B.

Il en est de même de

*      Toutes les solutions K = AB + 5, etc. qui donnent toutes des valeurs de C inférieures à B.

Finalement,

*      Seules les solutions du type AB + 2 sont susceptibles de donner satisfaction.

Enfin,

*      On ne peut choisir pour B que les nombres congrus à – 1 modulo 4.

*      En effet, si l'on a C = (3B + 1)/2, ce nombre est  0 modulo 4, si B est un 4n + 1.

*      Donc, divisé par 2, on aura encore un nombre pair.

 

Exemple :

*      Avec B = 5, on a: C = (15+1)/(15+2-15) = 8.

 

On a donc à n'étudier que les solutions :

*      A = 3 ; B = 4n – 1 et donc C = 6n – 1.

*      D'où ABC - 1 = 3(4n-1)(6n-1) - 1 = 72n2 - 30n + 2

*      Et l'on a :

PPCM (2, 4n-2, 6n-2) = 2(2n-1)(3n-1) = 12n2 - 10n + 2

*      On doit donc avoir :

72n2 - 30n + 2 = m(12n2 - 10n + 2)

*      Ou encore :     

36n2 - 15n + 1 = m(6n2 - 5n + 1)

*      De m = 1 à m = 6, on ne trouve que des solutions fractionnaires.

Pour m = 7,

*      On trouve la solution C = 17, et ABC = 561.

Au dessus de m = 7,

*      Il n'y a plus de solution car n est constamment inférieur à 2.

Il est facile de prouver que

*      n reste compris entre 1 et 2 lorsque m augmente, en posant m = 8+q :

 36n2 - 15n + 1 = (8+q)(6n2 - 5n + 1)

*      Ou encore :

(12+6q)n2 - (25+5q)n + 7 + q = 0

*      D'où

n = (25+5q + {(25+5q)2 - 4(12+6q)(7+q)}) / (24+12q)

n = (25+5q +17+q ) / (24+12q)

= (42+6q) / (24+12q)

< (48+24q) / (24+12q)

< 2

        

*      On est donc assuré que 561 est la seule solution du type 3.

 

 

 

 

 

Recherche des nombres de Carmichaël

 

*      La recherche des nombres de Carmichaël n'est pas chose aisée.

*      Il est paradoxalement plus difficile de découvrir des pseudo-premiers pour le reste 2 composé de deux facteurs premiers seulement.

*      341est une exception remarquable, et elle est due au fait que le gaussien de 2 dans Z/31 est 5, juste égal à la moitié du gaussien de 2 dans Z/11.

*      Le gaussien de 2 dans Z/341 est donc 10 qui est contenu un nombre entier de fois dans 340.

 

*      Les remarques que nous avons faites nous ont beaucoup facilité la tâche pour découvrir de nombreux Carmichaël.

*      Souvent aussi, nous avons remarqué qu'une combinaison  en donnait une valable en , etc.

*      Il faut aussi remarquer que certains facteurs premiers sont très prolifiques, alors que d'autres ne le sont pas du tout.

  

Voir la liste des Nombres de Carmichaël

 

 

RÉCIPROQUE DU THÉORÈME DE FERMAT

 

*      Si on énonce le petit théorème de FERMAT dans sa forme actuelle :

 

Si p est premier, on a : ap-1 - 1 = k .p

pour tout a non multiple de p.

 

*      Cette forme est obtenue en divisant ap - a = K .p par a

*      Alors on peut énoncer une réciproque tout à fait valable :

 

Si on a   ap-1 - 1 = k . p

pour tout a non multiple de p,

on est assuré que p est premier

 

 

 

 

CONCLUSIONS

 

*      Les nombres de Carmichaël sont relativement rares.

*      Carl Pomerance dans un article de la revue Pour la Science, de février 1983, cite le chiffre de un nombre de Carmichaël tous les 106 nombres.

 

*      Pour notre part, nous en avons trouvé

   1 dans le premier millier ;

   6 entre 1000 et 10.000 ;

   7 entre 104 et 105 ;

17 entre 105 et 106 ;

10 entre 106 et 107 ;

12 entre 107 et 108 ;

  2 entre 108 et 109 ;

et 3 > 109.

 

*      Mais notre liste est certainement incomplète…
Pourtant, on sait depuis 1994 qu'il y en a une infinité (Alford).

 

 


 

Suite

*    Presque-premiers

*    Nombres premiersIndex

Voir

*    Fermat

*    Modulo & Congruences

*    Nombres Premiers

*    Pseudo Premiers

*    Pseudo Premiers Absolus

Sites

*    Carmichael's Conjecture

*    Carmichael numbers