Conjecture de Carmichael
# 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 $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 $^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.

