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.

Exemples

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}$.

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

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.

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 ${\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.

Notes

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.

• Portail des mathématiques