Función φ de Euler

De Wikipedia, la enciclopedia libre

Este artículo o sección sobre ciencia necesita ser wikificado con un formato adecuado a las convenciones de estilo de Wikipedia.
Por favor, edítalo para cumplir con ellas. No elimines este aviso hasta que lo hayas hecho. ¡Colabora wikificando!

La función φ de Euler indica, para su parámetro m, el número de elementos invertibles en un cuerpo o anillo finito de dimensión m. Su valor se corresponde igualmente con la cantidad de números primos relativos con m menores o iguales que m.

Puede definirse como

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

Su cálculo puede acelerarse conociendo las siguientes propiedades:

φ(p) = p - 1 si p es primo,
φ(p^e) = p^e (1 - p^-1) si p es primo y e es un número natural (ver nota), y
φ(ab) = φ(a)φ(b) si mcd{a, b} = 1

Demostración de las propiedades:

Evidente, ya que si p es primo todos los números naturales de 1 a p-1 son primos con p.
Los únicos números entre 1 y p^e que NO son primos con p^e son los múltiplos de p, que son en total p^e-1. Por tanto φ(p^e)=p^e-p^e-1, de donde se sigue inmediatamente la propiedad.
Empezaremos probando que si p y q son primos distintos entonces φ(pq)=φ(p)φ(q). Los números de 1 a pq serán primos con pq si no son múltiplos de p ni de q. De 1 a pq-1 hay p-1 múltiplos de q y q-1 múltiplos de p, y no hay ninguno común a ambos, ya que MCM(p,q)=pq.

Por tanto φ(pq)=pq-1-(p-1)-(q-1)=pq-p-q+1= (p-1)(q-1)=φ(p)φ(q)

Ahora probaremos que φ(pa)=pφ(a) si p es un primo que divide a a. En estas condiciones, si un número es primo con pa, también lo será con a, y recíprocamente. Así, entre 1 y a hay φ(a) primos con pa, entre a+1 y 2a hay otros φ(a) primos con pa, etc. Entonces, entre 1 y pa hay pΦ(a) primos con pa.

Con estos dos resultados intermedios y agregando el teorema fundamental de la aritmética y el principio de inducción es ya muy sencillo probar la tercera propiedad.

La función φ 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.
Por ejemplo, φ(10) = 4, porque cada uno de los cuatro números 1, 3, 7 y 9 es coprimo con 10.

φ es una función multiplicativa condicional: si m y n son primos entre sí, entonces φ(mn) = φ(m) φ(n).

Con esto, el valor de φ(n) puede calcularse empleando el teorema fundamental de la Aritmética: si n = p₁^k₁ ... p_r^k_r donde los p_j son números primos distintos, entonces φ(n) = (p₁-1) p₁^k₁-1 ... (p_r-1) p_r^k_r-1. (Esbozo de la demostración: el caso r = 1 es fácil, y el resultado general se obtiene por multiplicatividad)

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