Función fi de Euler

Keywords: Función fi de Euler, Anillo (álgebra), Aritmética modular, Coprimo, Divisor, Función, Función de Möbius, Función multiplicativa, Fórmula de inversión de Möbius

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

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

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

donde la suma es de todos los divisores positivos d de n.

Ahora podemos 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 relacionada con φ(n):

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

Keywords: Función fi de Euler, Anillo (álgebra), Aritmética modular, Coprimo, Divisor, Función, Función de Möbius, Función multiplicativa, Fórmula de inversión de Möbius