En matemáticas, función totient conjetura de Carmichael se refiere a la multiplicidad de valores de la función totient de Euler φ ( n ), que cuenta el número de enteros menor que y primos entre sí a n . Establece que, para cada n hay al menos otro entero m ≠ n tal que φ ( m ) = φ ( n ). Robert Carmichael enunció por primera vez esta conjetura en 1907, pero como un teoremamás que como una conjetura. Sin embargo, su prueba era defectuosa y, en 1922, se retractó de su afirmación y declaró la conjetura como un problema abierto .
Ejemplos de
La función totient φ ( n ) es igual a 2 cuando n es uno de los tres valores 3, 4 y 6. Por lo tanto, si tomamos cualquiera de estos tres valores como n , entonces se puede usar cualquiera de los otros dos valores como la m para la cual φ ( m ) = φ ( n ).
De manera similar, el totient es igual a 4 cuando n es uno de los cuatro valores 5, 8, 10 y 12, y es igual a 6 cuando n es uno de los cuatro valores 7, 9, 14 y 18. En cada caso, hay más de un valor de n que tiene el mismo valor de φ ( n ).
La conjetura establece que este fenómeno de valores repetidos se cumple para cada n .
k | números n tales que φ ( n ) = k (secuencia A032447 en la OEIS ) | número de tales n s (secuencia A014197 en la 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 |
dieciséis | 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 |
Límites inferiores
Hay límites inferiores muy altos para la conjetura de Carmichael que son relativamente fáciles de determinar. El mismo Carmichael demostró que cualquier contraejemplo de su conjetura (es decir, un valor n tal que φ ( n ) es diferente de los totales de todos los demás números) debe ser al menos 10 37 , y Victor Klee amplió este resultado a 10 400 . Un límite inferior defue dada por Schlafly y Wagon, y un límite inferior de fue determinada por Kevin Ford en 1998. [1]
La técnica computacional subyacente a estos límites inferiores depende de algunos resultados clave de Klee que hacen posible mostrar que el contraejemplo más pequeño debe ser divisible por cuadrados de los números primos dividiendo su valor total. Los resultados de Klee implican que 8 y Fermat primos (primos de la forma 2 k + 1) excluyendo 3 no dividen el contraejemplo más pequeño. En consecuencia, probar la conjetura es equivalente a probar que la conjetura es válida para todos los enteros congruentes con 4 (mod 8).
Otros resultados
Ford también demostró que si existe un contraejemplo de la Conjetura, entonces una proporción positiva (en el sentido de densidad asintótica) de los números enteros son igualmente contraejemplos. [1]
Aunque la conjetura se cree ampliamente, Carl Pomerance dio una condición suficiente para que un número entero n sea un contraejemplo de la conjetura ( Pomerance 1974 ). De acuerdo con esta condición, n es un contraejemplo si para cada primo p tal que p - 1 divide a φ ( n ), p 2 divide a n . Sin embargo, Pomerance demostró que la existencia de tal número entero es muy improbable. Esencialmente, se puede demostrar que si los primeros k primos p congruentes con 1 (mod q ) (donde q es un primo) son todos menores que q k +1 , entonces dicho número entero será divisible por cada primo y, por lo tanto, no puede existir. En cualquier caso, probar que el contraejemplo de Pomerance no existe está lejos de probar la conjetura de Carmichael. Sin embargo, si existe, existen infinitos contraejemplos, como afirma Ford.
Otra forma de plantear la conjetura de Carmichael es que, si A ( f ) denota el número de enteros positivos n para los cuales φ ( n ) = f , entonces A ( f ) nunca puede ser igual a 1. De manera similar, Wacław Sierpiński conjeturaba que todo entero positivo otro que 1 ocurre como un valor de A ( f ), una conjetura que fue probada en 1999 por Kevin Ford. [2]
Notas
Referencias
- Carmichael, RD (1907), "On Euler's φ- function", Bulletin of the American Mathematical Society , 13 (5): 241–243, doi : 10.1090 / S0002-9904-1907-01453-2 , MR 1558451.
- Carmichael, RD (1922), "Nota sobre de Euler φ -Función", Boletín de la Sociedad Americana de Matemáticas , 28 (3): 109-110, doi : 10.1090 / S0002-9904-1922-03504-5 , MR 1560520.
- Ford, K. (1999), "El número de soluciones de φ ( x ) = m ", Annals of Mathematics , 150 (1): 283–311, doi : 10.2307 / 121103 , JSTOR 121103 , MR 1715326 , Zbl 0978.11053.
- Guy, Richard K. (2004), Problemas no resueltos en teoría de números (3.a ed.), Springer-Verlag , B39, ISBN 978-0-387-20860-2, Zbl 1058.11001.
- Klee, VL, Jr. (1947), "Sobre una conjetura de Carmichael", Boletín de la American Mathematical Society , 53 (12): 1183-1186, doi : 10.1090 / S0002-9904-1947-08940-0 , MR 0022855 , Zbl 0035.02601.
- Pomerance, Carl (1974), "Sobre la conjetura de Carmichael" (PDF) , Proceedings of the American Mathematical Society , 43 (2): 297-298, doi : 10.2307 / 2038881 , JSTOR 2038881 , Zbl 0254.10009.
- Sándor, Jozsef; Crstici, Borislav (2004), Manual de teoría de números II , Dordrecht: Kluwer Academic, págs. 228–229, ISBN 978-1-4020-2546-4, Zbl 1079.11001.
- Schlafly, A .; Wagon, S. (1994), "La conjetura de Carmichael sobre la función de Euler es válida por debajo de 10 10,000,000 ", Mathematics of Computation , 63 (207): 415–419, doi : 10.2307 / 2153585 , JSTOR 2153585 , MR 1226815 , Zbl 0801.11001.
enlaces externos
- Weisstein, Eric W. "Conjetura de la función Totient de Carmichael" . MathWorld .