NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 13/12/2019 Orientation générale  DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique Brèves de Maths
	Nombres PREMIERS
Débutants Nombres Premiers	Recherche de PRIMALITÉ			Glossaire Nombres Premiers
Index des pages NOMBRES PREMIERS >>> INDEX	Crible d'Ératosthène	Presque-premiers	Carmichael
	Divisibilité	Pseudo Premiers	Carmichael - Texte
	Primalité	Liste pseudo-P.	Nombres de Poulet
	Sommaire de cette page >>> Les nombres extraordinaires de Carmichael >>> Approche avec le corps z7 >>> Suite avec l'anneau z15 >>> Le nombre de Carmichael: 561 >>> Réciproque du théorème de Fermat >>> Nombres de Carmichael à deux facteurs >>> Structure du nombre de Carmichael 561 >>> Recherche des nombres de Carmichael - cas de 341 >>> Réciproque du théorème de Fermat >>> Conclusions

Les nombres extraordinaires

de Carmichael

Texte de M. Pierre BARDONNET – Novembre 1999

Avec tous mes remerciements.

Les nombres de CARMICHAEL

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 2^341 - 2 est divisible par 341, et il ajoute que Carmichael 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 Carmichael en se servant de l'exemple Z/561, et comparer les différences entre un nombre de Carmichael, un anneau tel que Z/15 et un corps Z/p. 2) Montrer qu'on ne peut pas trouver de nombres de Carmichael du type . 3) Montrer que 561 est le seul Carmichael du type 3 . 4) Citer des exemples de nombres de Carmichael à 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 2⁷ – 2 0 (mod. 7) ; d'ailleurs 2⁷ = 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 CARMICHAEL 561

Et maintenant, voyons ce qui se passe pour le Carmichael 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 : 3^80= 1 + k . 187 et en multipliant par 3 : 3^81 = 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 : A^561 - 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 Carmichael à deux facteurs

Il est impossible de trouver un nombre de Carmichael composé des deux seuls facteurs premiers ab. Supposons en effet Qu'on puisse en construire un avec deux facteurs premiers seulement : – 1 = 2^xm P – 1 = 2^ym 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 2^xm P Q, et l'on devrait avoir : - 1 = (2^xm P + 1) (2^ym Q + 1) - 1 = K x 2^xm P Q ou encore 2^xm P + 2^ym Q + 2^xym^2P Q = K x 2^xm 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 Carmichael comporte donc au moins trois facteurs premiers. De même Il n'est pas possible d'avoir un nombre de Carmichael 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 Carmichael ne peut donc comporter un carré, ni un facteur premier à une puissance quelconque.

Structure du nombre de Carmichael 561

561 est le seul nombre de Carmichael 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 Carmichael 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 = 72n^2 - 30n + 2 Et l'on a : PPCM (2, 4n-2, 6n-2) = 2(2n-1)(3n-1) = 12n^2- 10n + 2 On doit donc avoir : 72n^2 - 30n + 2 = m(12n^2 - 10n + 2) Ou encore : 36n^2 - 15n + 1 = m(6n^2 - 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 : 36n^2 - 15n + 1 = (8+q)(6n^2 - 5n + 1) Ou encore : (12+6q)n^2 - (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 Carmichael

La recherche des nombres de Carmichael 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 Carmichael. 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 Carmichael

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 : a^p-1- 1 = k .p pour tout a non multiple de p. Cette forme est obtenue en divisant a^p - a = K .p par a Alors on peut énoncer une réciproque tout à fait valable : Si on a a^p-1 - 1 = k . p pour tout a non multiple de p, on est assuré que p est premier

CONCLUSIONS

Les nombres de Carmichael 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 Carmichael tous les 10^6 nombres. Pour notre part, nous en avons trouvé 1 dans le premier millier ; 6 entre 1000 et 10.000 ; 7 entre 10^4 et 10^5 ; 17 entre 10^5 et 10^6 ; 10 entre 10^6 et 10^7 ; 12 entre 10^7 et 10^8 ; 2 entre 10^8 et 10^9 ; et 3 > 10^9. Mais notre liste est certainement incomplète… Pourtant, on sait depuis 1994 qu'il y en a une infinité (Alford).

Retour	Nombres de Carmichael
Suite	Presque-premiers Nombres premiers – Index
Voir	Fermat Modulo & Congruences Nombres Premiers Pseudo Premiers Pseudo Premiers Absolus
Sites	Carmichael's Conjecture Carmichael numbers
Cette page	http://villemin.gerard.free.fr/ThNbDemo/TextCarm.htm