Función φ de Euler
La función φ de Euler (también llamada función indicatriz de Euler) es una función importante en teoría de números. Si n es un número entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n, es decir, formalmente se puede definir como:
donde |·| significa la cardinalidad del conjunto descrito.
La función φ es importante principalmente porque proporciona el tamaño del grupo multiplicativo de enteros módulo n. Más precisamente, es el orden del grupo de unidades del anillo . En efecto, junto con el teorema de Lagrange de los posibles tamaños de subgrupos de un grupo, proporciona una demostración del teorema de Euler que dice que para todo a coprimo con n. La función φ juega también un papel clave en la definición del sistema de cifrado RSA.
Primeras propiedades y cálculo de la función
Se sigue de la definición que , pues el elemento (1) solo puede ser coprimo consigo mismo. Para otros números se cumple que:
- si es primo.
- si p es primo y k es un número natural.
- es una función multiplicativa: si m y n son primos entre sí, entonces .
La primera propiedad se demuestra fácilmente, porque un número primo es coprimo con todos sus anteriores. Y, por tanto, existen p-1 elementos coprimos con p. En otras palabras, como p es primo solo tendrá de divisores a sí mismo y a la unidad, la cual está presente en los p-1 números anteriores a p.
Para la segunda propiedad debemos observar que si es primo solo sus múltiplos ( ) menores que presentan un máximo común divisor con distinto de uno. Esto es, son los únicos números tales que . Como en total hay números que satisfacen esta propiedad, el resto de números entre 1 y solo tiene de divisor en común con a la unidad. Esto es, . Nótese que esta segunda propiedad se cumple porque es primo. En efecto, si hubiera un distinto de 1 tal que , entonces sería divisor de ( veces); es decir, sería una potencia (y por consiguiente múltiplo) de , contradiciendo la suposición inicial .
Para demostrar la tercera propiedad, sabemos que:
con pi primo, por tanto:
- .
Como , entonces ninguno de los primos y son iguales y la descomposición en primos de no se ve alterada, es decir, si y entonces la descomposición en primos será , lo cual implica que
por lo tanto, si y son primos relativos.
Con esto, el valor de φ(n) puede calcularse empleando el teorema fundamental de la Aritmética: si
donde los pj son números primos distintos, entonces
Esta última fórmula es un producto de Euler y a menudo se escribe como
donde los p son los distintos primos que dividen a n.
Ejemplo de cálculo
También,
Se puede comprobar manualmente que los números coprimos con 36 (o sea, que no son divisibles por 2 ni por 3) son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.
Algunos valores
Los 99 primeros valores de la función vienen escritos en la siguiente tabla, así como gráficamente.
+0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 | +8 | +9 | |
---|---|---|---|---|---|---|---|---|---|---|
0+ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | |
10+ | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 |
20+ | 8 | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 |
30+ | 8 | 30 | 16 | 20 | 16 | 24 | 12 | 36 | 18 | 24 |
40+ | 16 | 40 | 12 | 42 | 20 | 24 | 22 | 46 | 16 | 42 |
50+ | 20 | 32 | 24 | 52 | 18 | 40 | 24 | 36 | 28 | 58 |
60+ | 16 | 60 | 30 | 36 | 32 | 48 | 20 | 66 | 32 | 44 |
70+ | 24 | 70 | 24 | 72 | 36 | 40 | 36 | 60 | 24 | 78 |
80+ | 32 | 54 | 40 | 82 | 24 | 64 | 42 | 56 | 40 | 88 |
90+ | 24 | 72 | 44 | 60 | 46 | 72 | 32 | 96 | 42 | 60 |
Propiedades
- El valor de φ(n) es igual al orden del grupo de las unidades del anillo Z/nZ (véase aritmética modular). Esto, junto con el teorema de Lagrange, proporciona una demostración del teorema de Euler.
- φ(n) también es igual al número de generadores del grupo cíclico Cn (y por ello también es igual al grado del polinomio ciclotómico Φn). Como cada elemento de Cn genera un subgrupo cíclico y los subgrupos de Cn son de la forma Cd donde d divide a n (notación: d|n), se tiene que
donde la suma es de todos los divisores positivos d de n.
De esta manera, se puede emplear la fórmula de inversión de Möbius para «invertir» esta suma y obtener otra fórmula para φ(n):
donde μ es la usual función de Möbius definida sobre los enteros positivos.
- La siguiente fórmula es de una serie de Dirichlet que genera un grupo cíclico φ(n):
Véase también
Referencias
Enlaces externos
- Weisstein, Eric W. «Euler's Totient Function». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- EulerPhifunction en PlanetMath.
- Wikilibros alberga un libro o manual sobre Implementaciones de la función φ de Euler.