Función φ de Euler

Función φ de Euler
Los primeros mil valores de \scriptstyle \varphi(n).

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.

Se define como:

\varphi(m) = |\{n \in \mathbb{N} | n \leq m \and \mathrm{mcd}(m, n) = 1 \}|

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

La función φ es importante principalmente porque proporciona el tamaño del unidades del anillo \mathbb{Z}/n\mathbb{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 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.

Contenido

Primeras propiedades y cálculo de la función

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

  1. φ(p) = p − 1 si p es primo.
  2. φ(pk) = (p − 1)pk − 1 si p es primo y k es un número natural. Se demuestra con inducción:
  3. φ es una función multiplicativa condicional: si m y n son primos entre sí, entonces φ(mn) = φ(m)φ(n).

La primera propiedad se demuestra fácilmente, porque un número primo es coprimo con todos sus anteriores. Y, por tanto, existe p-1 elementos coprimos con p.

La segunda propiedad se demuestra por inducción, supongamos que k = 1. Entonces φ(p1) = φ(p) = p − 1 por la propiedad 1, de manera que se puede escribir como φ(p1) = (p − 1)p1 − 1. Se debe demostrar que se cumple para φ(pk + 1) = (p − 1)pk.

Reescribiendo la identidad, (p − 1)pk = (p − 1)pk − 1p, luego ((p − 1)pk − 1)p = φ(pk)p. Como φ(pk) es la cantidad de números coprimos con pk, si multiplicamos dicha cantidad por p, el número que es coprimo con los demás debe aumentar p veces, con lo que φ(pk)p = φ(pk + 1) = (p − 1)pk.

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

n = p_1^{k_1} \cdots p_r^{k_r}

donde los pj son números primos distintos, entonces

 \varphi(n)=(p_{1}-1)p_{1}^{k_{1}-1} \cdots (p_{r}-1)p_{r}^{k_{r}-1}.

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

\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)

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

Ejemplo de cálculo

\varphi(36)=\varphi\left(3^2 2^2\right)=36\left(1-\frac{1}{3}\right)\left(1-\frac{1}{2}\right)=36\cdot\frac{2}{3}\cdot\frac{1}{2}=12.

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.

\varphi(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+   1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60

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
\sum_{d\mid n}\varphi(d)=n

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

\varphi(n)=\sum_{d\mid n} d \mu(n/d)

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

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

Véase también

Referencias

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Función fi de Euler — 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 …   Enciclopedia Universal

  • Función zeta de Riemann — ζ(s) en el plano complejo. El color de un punto s codifica el valor de ζ(s): Colores fuertes denotan valores cercanos a 0 y el tono codifica el valor del argumento. El punto blanco en s=1 es el polo de la función zeta; los puntos negros en el eje …   Wikipedia Español

  • Función divisor — σ0(n) representada hasta n=250. Función divis …   Wikipedia Español

  • Función beta (desambiguación) — Función beta puede referirse a los siguientes términos: Función beta de Euler, integral de primera especie de Euler. Función beta de Dirichlet, función L de Dirichlet, concretamente la función L para el carácter alternado de periodo cuatro.… …   Wikipedia Español

  • Función indicatriz (desambiguación) — Función indicatriz puede referirse a: Función indicatriz, (también llamada función característica), es una función matemática definida en un conjunto que indica la pertenencia de un elemento en el subconjunto de Función indicatriz de Euler,… …   Wikipedia Español

  • Función beta — Este artículo trata sobre función beta de Euler. Para otras funciones beta, véase Función beta (desambiguación). Función beta. Representación de la función para valores reales positivos de x e y. En matemáticas, la función beta …   Wikipedia Español

  • Función de Bessel — En matemática, las funciones de Bessel, primero definidas por el matemático Daniel Bernoulli y más tarde generalizadas por Friedrich Bessel, son soluciones canónicas y(x) de la ecuación diferencial de Bessel: (1) donde α es un …   Wikipedia Español

  • Función de Carmichael — En Teoría de números, la función de Carmichael de un entero positivo n, denotada λ(n), se define como el menor entero m tal que cumple: para cada número entero a coprimo con n. En otras palabras, define el exponente del grupo multiplicativo de… …   Wikipedia Español

  • Función de Möbius — La función de Möbius μ(n), nombrada así en honor a August Ferdinand Möbius, es una función multiplicativa estudiada en teoría de números y en combinatoria. Contenido 1 Definición 2 Propiedades y aplicaciones 2.1 Teoría de números …   Wikipedia Español

  • Función multiplicativa — En teoría de números, una función discreta (es decir, definida para n entero) se dice multiplicativa si f(1) = 1 f(m·n) = f(m)·f(n) cuando m y n son enteros coprimos (no tienen factores comunes). Una función multiplicativa queda determinada si se …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”