Función φ de Euler

Los primeros mil valores de .

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:

donde |·| significa la cantidad de números que cumplen la condición.

La función φ es importante principalmente porque proporciona el tamaño del . 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. Se demuestra mediante inducción sobre k:
  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 .

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

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.

Other Languages