Conjecture de Carmichael

conjecture en théorie des nombres portant sur l'indicatrice d'Euler

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 mn 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

modifier

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

modifier

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 à 1037, et Victor Klee a étendu ce résultat à 10 400. Une borne inférieure de   a été donnée par Schlafly et Wagon, et une autre de   a été déterminé par Kevin Ford en 1998[1].

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 2k + 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

modifier

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 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[2].

  1. a et b Sándor & Crstici (2004) p. 228
  2. Sándor & Crstici (2004) p. 229

Références

modifier

Liens externes

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