Función φ 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:

Los primeros mil valores de .

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, es el orden del grupo de unidades del anillo . 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 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

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

  1. si es primo.
  2. si p es primo y k es un número natural.
  3. es una función multiplicativa: si m y n son primos entre sí, entonces .

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 por la propiedad 1, de manera que se puede escribir como . Se debe demostrar que se cumple para . Reescribiendo la identidad, , luego . Como es la cantidad de números coprimos con , si multiplicamos dicha cantidad por p, el número que es coprimo con los demás debe aumentar p veces, con lo que .

Para demostrar la tercera propiedad, sabemos que:

con pi primo, por tanto:

.

Como , entonces ningún primo entre y son iguales y la descomposición en primos de no se ve alterada, es decir si y entonces la descomposición en primos será , lo cual implica que

por lo tanto, si y son primos relativos.

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

donde los pj 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.

Ejemplo de cálculo

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.

Algunos valores

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.

+0+1+2+3+4+5+6+7+8+9
0+  112242646
10+ 41041268816618
20+ 812102282012181228
30+ 8301620162412361824
40+ 16401242202422461642
50+ 20322452184024362858
60+ 16603036324820663244
70+ 24702472364036602478
80+ 32544082246442564088
90+ 24724460467232964260

Propiedades

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

     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.

Véase también

Referencias

    Enlaces externos

    Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.