Conjecture de Carmichael
En mathématiques, la conjecture de Carmichael concerne la multiplicité des valeurs de l'indicatrice d'Euler φ (n), dénombrant le nombre d'entiers inférieur premier avec n. Elle énonce que, pour chaque n, il y a au moins un autre entier m ≠ n tel que φ (m) = φ (n). Robert Carmichael a énoncé cette conjecture pour la première fois en 1907, en tant que théorème, pensant l'avoir démontrée. Il la déclara ensuite en tant que problème ouvert en 1922.
Exemples modifier
L'indicatrice φ (n) est égale à 2 lorsque n vaut 3, 4 ou 6.
De même, l'indicatrice est égal à 4 lorsque n est l'une des quatre valeurs 5, 8, 10 et 12, et vaut 6 lorsque n est l'une des quatre valeurs 7, 9, 14 et 18. Dans chaque cas, il existe plus d'une valeur de n ayant la même valeur φ(n).
La conjecture affirme ainsi que cela est vrai pour chaque n.
| k | n tels que φ(n) = k suite A032447 de l'OEIS | nombre de tels n suite A014197 de l'OEIS |
| 1 | 1, 2 | 2 |
| 2 | 3, 4, 6 | 3 |
| 4 | 5, 8, 10, 12 | 4 |
| 6 | 7, 9, 14, 18 | 4 |
| 8 | 15, 16, 20, 24, 30 | 5 |
| 10 | 11, 22 | 2 |
| 12 | 13, 21, 26, 28, 36, 42 | 6 |
| 16 | 17, 32, 34, 40, 48, 60 | 6 |
| 18 | 19, 27, 38, 54 | 4 |
| 20 | 25, 33, 44, 50, 66 | 5 |
| 22 | 23, 46 | 2 |
| 24 | 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 | 10 |
| 28 | 29, 58 | 2 |
| 30 | 31, 62 | 2 |
| 32 | 51, 64, 68, 80, 96, 102, 120 | 7 |
| 36 | 37, 57, 63, 74, 76, 108, 114, 126 | 8 |
| 40 | 41, 55, 75, 82, 88, 100, 110, 132, 150 | 9 |
| 42 | 43, 49, 86, 98 | 4 |
| 44 | 69, 92, 138 | 3 |
| 46 | 47, 94 | 2 |
| 48 | 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 | 11 |
| 52 | 53, 106 | 2 |
| 54 | 81, 162 | 2 |
| 56 | 87, 116, 174 | 3 |
| 58 | 59, 118 | 2 |
| 60 | 61, 77, 93, 99, 122, 124, 154, 186, 198 | 9 |
| 64 | 85, 128, 136, 160, 170, 192, 204, 240 | 8 |
| 66 | 67, 134 | 2 |
| 70 | 71, 142 | 2 |
| 72 | 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 | 17 |
Bornes inférieures modifier
Il existe bornes inférieures assez élevées qui sont relativement aisées à déterminer. Carmichael a prouvé que tout contre-exemple de sa conjecture doit être supérieur à 1037, et Victor Klee a étendu ce résultat à 10 400. Une borne inférieure de a été donnée par Schlafly et Wagon, et une autre de a été déterminé par Kevin Ford en 1998[1].
Les méthodes permettant d'atteindre de tels bornes inférieures reposent sur quelques résultats clés de Klee qui permettent de montrer que le plus petit contre-exemple doit être divisible par les carrés des nombres premiers divisant son indicatrice d'Euler. Les résultats de Klee impliquent que 8 et les nombres premiers de Fermat (nombres premiers de la forme 2k + 1) excluant 3 ne divise pas le plus petit contre-exemple. Par conséquent, prouver la conjecture équivaut à prouver que la conjecture est vraie pour tous les entiers congruents à 4 modulo 8.
Autres résultats modifier
Ford a également prouvé que s'il existe un contre-exemple à cette conjecture, alors une proportion positive (au sens de densité asymptotique) des nombres entiers sont également contre-exemples[1].
Bien que la conjecture soit largement acceptée, Carl Pomerance a donné une condition suffisante pour qu'un entier n soit un contre-exemple de la conjecture (Pomerance 1974). Selon cette dernière, n est un contre-exemple si pour tout premier p tel que p − 1 divise φ(n), p 2 divise n. Cependant, Pomerance a montré que l'existence d'un tel entier est très improbable. En effet, on peut montrer que si les k premiers p sont congruents à 1 (mod q) (où q est un nombre premier) et tous inférieurs à q k +1, n sera en fait divisible par tout nombre premier, ce qui n'est pas possible. Cependant, montrer que le contre-exemple de Pomerance n'existe pas ne permet pas prouver la conjecture de Carmichael. Cependant, s'il existe, il existe une infinité de contre-exemples, comme nous l'avons vu.
Une autre façon de formuler la conjecture de Carmichael est que, si A(f) désigne le nombre d'entiers positifs n pour lesquels φ(n) = f, alors A(f) ne vaut jamais 1.
Wacław Sierpiński a conjecturé que chaque entier positif autre que 1 apparaît comme une valeur de A(f), celle-ci a été prouvée en 1999 par Kevin Ford[2].
Notes modifier
- Sándor & Crstici (2004) p. 228
- Sándor & Crstici (2004) p. 229
Références modifier
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Carmichael conjecture » (voir la liste des auteurs).
- R. D. Carmichael, « On Euler's φ-function », Bulletin of the American Mathematical Society, vol. 13, no 5, (DOI 10.1090/S0002-9904-1907-01453-2, MR 1558451).
- R. D. Carmichael, « Note on Euler's φ-function », Bulletin of the American Mathematical Society, vol. 28, no 3, (DOI 10.1090/S0002-9904-1922-03504-5, MR 1560520).
- K. Ford, « The number of solutions of φ(x) = m », Annals of Mathematics, vol. 150, no 1, (DOI 10.2307/121103, JSTOR 121103, MR 1715326, zbMATH 0978.11053).
- (en) Richard K. Guy, Unsolved problems in number theory, New York, Springer-Verlag, , 3e éd., 437 p. (ISBN 978-0-387-20860-2, zbMATH 1058.11001, lire en ligne).
- V. L., Jr. Klee, « On a conjecture of Carmichael », Bulletin of the American Mathematical Society, vol. 53, no 12, (DOI 10.1090/S0002-9904-1947-08940-0, MR 0022855, zbMATH 0035.02601).
- Carl Pomerance, « On Carmichael's conjecture », Proceedings of the American Mathematical Society, vol. 43, no 2, (DOI 10.2307/2038881, JSTOR 2038881, zbMATH 0254.10009, lire en ligne).
- Jozsef Sándor et Borislav Crstici, Handbook of number theory II, Dordrecht, Kluwer Academic, , 228–229 p. (ISBN 978-1-4020-2546-4, zbMATH 1079.11001, lire en ligne).
- A. Schlafly et S. Wagon, « Carmichael's conjecture on the Euler function is valid below 1010,000,000 », Mathematics of Computation, vol. 63, no 207, (DOI 10.2307/2153585, JSTOR 2153585, MR 1226815, zbMATH 0801.11001).
Liens externes modifier
- Weisstein, Eric W. "Carmichael's Totient Function Conjecture". MathWorld.
