Conjecture de Carmichael

En mathématiques, la conjecture de Carmichael concerne la multiplicité des valeurs de l'indicatrice d'Euler ${\displaystyle \varphi (n)}$, dénombrant le nombre d'entiers de 1 à ${\displaystyle n}$ premiers avec ${\displaystyle n}$. Elle énonce que, pour tout ${\displaystyle n}$, il y a au moins un autre entier ${\displaystyle m\neq n}$ tel que ${\displaystyle \varphi (m)=\varphi (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 comme problème ouvert en 1922.

L'indicatrice ${\displaystyle \varphi (n)}$ est égale à 2 lorsque ${\displaystyle n}$ vaut 3, 4 ou 6.

De même, l'indicatrice est égal à 4 lorsque ${\displaystyle n}$ vaut 5, 8, 10 ou 12, et est égal à 6 lorsque ${\displaystyle n}$ vaut 7, 9, 14 ou 18. Dans chaque cas, il existe plus d'une valeur de ${\displaystyle n}$ ayant la même valeur ${\displaystyle \varphi (n)}$.

La conjecture affirme ainsi que cela est vrai pour tout ${\displaystyle n}$.

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 égale à ${\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 telles 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 congrus à 4 modulo 8.

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 ${\displaystyle n}$ soit un contre-exemple de la conjecture (Pomerance 1974). Selon cette dernière, ${\displaystyle n}$ est un contre-exemple si pour tout premier p tel que p − 1 divise φ(n), p ² divise ${\displaystyle 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 congrus à 1 (mod q) (où q est un nombre premier) et tous inférieurs à q ^{k +1}, ${\displaystyle 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 de 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 ${\displaystyle n}$ pour lesquels φ(n) = f, alors A(f) ne vaut jamais 1.

Wacław Sierpiński a conjecturé que tout entier positif autre que 1 apparaît comme valeur de A(f) ; cette conjecture a été prouvée en 1999 par Kevin Ford^[2].

• (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).

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

• Portail des mathématiques