Función φ de Euler

Los primeros mil valores de $\scriptstyle \varphi(n)$.

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.

Se define como:

$\varphi(m) = |\{n \in \mathbb{N} | n \leq m \and \mathrm{mcd}(m, n) = 1 \}|$

donde |·| significa la cantidad de números que cumplen la condición.

La función φ es importante principalmente porque proporciona el tamaño del unidades del anillo $\mathbb{Z}/n\mathbb{Z}$. 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 $a^{\varphi(n)}\equiv 1 \pmod{n}$ 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 φ(1) = 1, pues el elemento (1) sólo puede ser coprimo consigo mismo. Para otros números se cumple que:

1. φ(p) = p − 1 si p es primo.
2. φ(p^k) = (p − 1)p^{k − 1} si p es primo y k es un número natural. Se demuestra con inducción:
3. φ es una función multiplicativa condicional: si m y n son primos entre sí, entonces φ(mn) = φ(m)φ(n).

La primera propiedad se demuestra fácilmente, porque un número primo es coprimo con todos sus anteriores. Y, por tanto, existe p-1 elementos coprimos con p.

La segunda propiedad se demuestra por inducción, supongamos que k = 1. Entonces φ(p¹) = φ(p) = p − 1 por la propiedad 1, de manera que se puede escribir como φ(p¹) = (p − 1)p^{1 − 1}. Se debe demostrar que se cumple para φ(p^{k + 1}) = (p − 1)p^k.

Reescribiendo la identidad, (p − 1)p^k = (p − 1)p^{k − 1}p, luego ((p − 1)p^{k − 1})p = φ(p^k)p. Como φ(p^k) es la cantidad de números coprimos con p^k, si multiplicamos dicha cantidad por p, el número que es coprimo con los demás debe aumentar p veces, con lo que φ(p^k)p = φ(p^{k + 1}) = (p − 1)p^k.

Con esto, el valor de φ(n) puede calcularse empleando el teorema fundamental de la Aritmética: si

$n = p_1^{k_1} \cdots p_r^{k_r}$

donde los p_j son números primos distintos, entonces

$\varphi(n)=(p_{1}-1)p_{1}^{k_{1}-1} \cdots (p_{r}-1)p_{r}^{k_{r}-1}.$

Esta última fórmula es un producto de Euler y a menudo se escribe como

$\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$

donde los p son los distintos primos que dividen a n.

Ejemplo de cálculo

$\varphi(36)=\varphi\left(3^2 2^2\right)=36\left(1-\frac{1}{3}\right)\left(1-\frac{1}{2}\right)=36\cdot\frac{2}{3}\cdot\frac{1}{2}=12.$

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

Representación gráfica de los 100 primeros valores. Nótese que el límite inferior marcado por la recta y = 4n/15 no es el límite inferior de la función de manera global, sino para múltiplos de 30.

Los 99 primeros valores de la función vienen escritos en la siguiente tabla, así como gráficamente.

$\varphi(n)$	+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 C_n (y por ello también es igual al grado del polinomio ciclotómico Φ_n). Como cada elemento de C_n genera un subgrupo cíclico y los subgrupos de C_n son de la forma C_d donde d divide a n (notación: d|n), se tiene que

$\sum_{d\mid n}\varphi(d)=n$

     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):

$\varphi(n)=\sum_{d\mid n} d \mu(n/d)$

     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):

$\sum_{n=0}^{\infty} \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}$

Véase también

• Teorema de Euler
• Función de Carmichael

Referencias

Enlaces externos

• Weisstein, Eric W. «Euler's Totient Function» (en inglés). MathWorld. Wolfram Research.
• EulerPhifunction en PlanetMath