Función φ de Euler

De Wikipedia, la enciclopedia libre

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 que m.

Puede definirse como

Φ(m) = cardinal de {n ∈ N tal que n < m ^ 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). (Falta algún esbozo de la demostració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