Función phi de Euler

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:

${displaystyle varphi (n)=|{min mathbb {N} |mleq nland mathrm {mcd} (m,n)=1}|}$

donde |·| significa la cardinalidad del conjunto descrito.

La función φ es importante principalmente porque proporciona el tamaño del grupo multiplicativo de enteros módulo n. Más precisamente, ${displaystyle varphi (n)}$ es el orden del grupo de unidades del anillo ${displaystyle mathbb {Z} /nmathbb {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 ${displaystyle 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.

Se sigue de la definición que ${displaystyle varphi (1)=1}$, pues el elemento (1) solo puede ser coprimo consigo mismo. Para otros números se cumple que:

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. En otras palabras, como p es primo solo tendrá de divisores a sí mismo y a la unidad, la cual está presente en los p-1 números anteriores a p.

Para la segunda propiedad debemos observar que si ${displaystyle p}$ es primo solo sus múltiplos (${displaystyle np}$) menores que ${displaystyle p^{k}}$ presentan un máximo común divisor con ${displaystyle p^{k}}$ distinto de uno. Esto es, ${displaystyle 1p,2p,3p,...,(p^{k-1})p}$ son los únicos números ${displaystyle m}$ tales que ${displaystyle operatorname {mcd} (p^{k},m) eq 1}$. Como en total hay ${displaystyle p^{k-1}}$ números que satisfacen esta propiedad, el resto de números entre 1 y ${displaystyle p^{k}}$ solo tiene de divisor en común con ${displaystyle p^{k}}$ a la unidad. Esto es, ${displaystyle varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}}$. Nótese que esta segunda propiedad se cumple porque ${displaystyle p}$ es primo. En efecto, si hubiera un ${displaystyle m eq np}$ distinto de 1 tal que ${displaystyle operatorname {mcd} (p^{k},m)=a eq 1}$, entonces ${displaystyle a}$ sería divisor de ${displaystyle p^{k}=pcdot p...p}$ (${displaystyle k}$ veces); es decir, ${displaystyle a}$ sería una potencia (y por consiguiente múltiplo) de ${displaystyle p}$, contradiciendo la suposición inicial ${displaystyle m eq np}$.

Para demostrar la tercera propiedad, sabemos que:

con p_i primo, por tanto:

Como ${displaystyle operatorname {mcd} (m,n)=1}$, entonces ninguno de los primos ${displaystyle p_{i}}$ y ${displaystyle q_{i}}$ son iguales y la descomposición en primos de ${displaystyle mn}$ no se ve alterada, es decir, si ${displaystyle m=q_{1}^{eta _{1}}q_{2}^{eta _{2}}...q_{k}^{eta _{1}}}$ y ${displaystyle n=p_{1}^{alpha _{1}}p_{2}^{alpha _{2}}...p_{j}^{alpha _{j}}}$ entonces la descomposición en primos será ${displaystyle mn=q_{1}^{eta _{1}}q_{2}^{eta _{2}}...q_{k}^{eta _{1}}p_{1}^{alpha _{1}}p_{2}^{alpha _{2}}...p_{j}^{alpha _{j}}}$, lo cual implica que

por lo tanto, ${displaystyle varphi (mn)=varphi (m)varphi (n)}$ si ${displaystyle m}$ y ${displaystyle n}$ son primos relativos.

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

donde los p_j son números primos distintos, entonces

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

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

También,

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.

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

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

     donde μ es la usual función de Möbius definida sobre los enteros positivos.