Conjecture de Carmichael

En mathématiques, la conjecture de Carmichael concerne la multiplicité des valeurs de l'indicatrice d'Euler $\phi (n)$, dénombrant le nombre d'entiers de 1 à $n$ premiers avec $n$. Elle énonce que, pour tout $n$, il y a au moins un autre entier $m\ne n$ tel que $\phi (m)=\phi (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 $\phi (n)$ est égale à 2 lorsque $n$ vaut 3, 4 ou 6.

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

La conjecture affirme ainsi que cela est vrai pour tout $n$.

k	n tels que φ(n) = k ; Modèle:OEIS	nombre de tels n : Modèle: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 égale à $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 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 $n$ soit un contre-exemple de la conjecture Modèle:Référence Harvard. 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 congrus à 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 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 $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.

Références

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.

Liens externes

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