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³⁷, et Victor Klee a étendu ce résultat à 10 ⁴⁰⁰. Une borne inférieure de $10^{10^{7}}$ a été donnée par Schlafly et Wagon, et une autre de $10^{10^{10}}$ a été déterminé par Kevin Ford en 1998.

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.

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 ² 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.

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.