Función φ de Euler

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
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, es decir, formalmente se puede definir 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 grupo multiplicativo de enteros módulo n. Más precisamente, \varphi(n) es el orden del grupo de 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[editar]

Se sigue de la definición que \varphi(1)=1, pues el elemento (1) sólo puede ser coprimo consigo mismo. Para otros números se cumple que:

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

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.

La segunda propiedad se demuestra por inducción, supongamos que k = 1. Entonces \varphi(p^1) = \varphi(p) = p-1 por la propiedad 1, de manera que se puede escribir como \varphi(p^1) = (p-1)p^{1-1}. Se debe demostrar que se cumple para \varphi(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 = \varphi(p^k)p. Como \varphi(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 \varphi(p^{k})p=\varphi(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 pj 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[editar]

\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[editar]

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[editar]

  • φ(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
\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.

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

Véase también[editar]

Referencias[editar]

Enlaces externos[editar]