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

1 Primeras propiedades y cálculo de la función
- 1.1 Ejemplo de cálculo
2 Algunos valores
3 Propiedades
4 Véase también
5 Referencias
6 Enlaces externos

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:

$φ(p) = p - 1$ si $p$ es primo.
$φ(p k) = (p - 1) p k - 1$ si p es primo y k es un número natural. Se demuestra con inducción:
$φ$ es una función multiplicativa condicional: si m y n son primos entre sí, entonces $φ(m n) = φ(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 $φ(p 1) = φ(p) = p - 1$ por la propiedad 1, de manera que se puede escribir como $φ(p 1) = (p - 1) p 1 - 1$ . Se debe demostrar que se cumple para $φ(p k + 1) = (p - 1) p k$ .

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

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 p_j 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

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.

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.

La siguiente fórmula es de una serie de Dirichlet que genera un grupo cíclico φ(n):

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

Véase también

Referencias

Enlaces externos

Weisstein, Eric W. «Euler's Totient Function» (en inglés). MathWorld. Wolfram Research.
EulerPhifunction en PlanetMath

Categoría:

Funciones aritméticas

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

Los diccionarios y las enciclopedias sobre el Académico

Función φ de Euler

Contenido

Primeras propiedades y cálculo de la función

Ejemplo de cálculo

Algunos valores

Propiedades

Véase también

Referencias

Enlaces externos

Mira otros diccionarios:

Compartir el artículo y extractos

$\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

$\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

Los diccionarios y las enciclopedias sobre el Académico

Wikipedia Español

Función φ de Euler

Contenido

Primeras propiedades y cálculo de la función

Ejemplo de cálculo

Algunos valores

Propiedades

Véase también

Referencias

Enlaces externos

Mira otros diccionarios:

Compartir el artículo y extractos

Link directo

$\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