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

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

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 à 10^37, et Victor Klee a étendu ce résultat à 10 ^400. Une borne inférieure de ${\displaystyle 10^{10^{7}}}$ a été donnée par Schlafly et Wagon, et une autre de ${\displaystyle 10^{10^{10}}}$ 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 2^k + 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

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

1. Sándor & Crstici (2004) p. 228
2. Sándor & Crstici (2004) p. 229

Références

• (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, n^o 5,‎ 1907 (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, n^o 3,‎ 1922 (DOI 10.1090/S0002-9904-1922-03504-5, MR 1560520).
• K. Ford, « The number of solutions of φ(x) = m », Annals of Mathematics, vol. 150, n^o 1,‎ 1999 (DOI 10.2307/121103, JSTOR 121103, MR 1715326, zbMATH 0978.11053).
• (en) Richard K. Guy, Unsolved problems in number theory, New York, Springer-Verlag, 2004, 3^e é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, n^o 12,‎ 1947 (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, n^o 2,‎ 1974 (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, 2004, 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 10^10,000,000 », Mathematics of Computation, vol. 63, n^o 207,‎ 1994 (DOI 10.2307/2153585, JSTOR 2153585, MR 1226815, zbMATH 0801.11001).

Liens externes

• Weisstein, Eric W. "Carmichael's Totient Function Conjecture". MathWorld.