Función φ de Euler

De Wikipedia, la enciclopedia libre

Los primeros mil valores de $\scriptstyle \varphi(n)$

La función φ 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.

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

[editar] Primeras propiedades y cálculo de la función

Se sigue de la definición que $\varphi(1)=1$ , y que:

$\varphi(p) = p - 1$ si $p$ es primo,
$\varphi(p^{k}) = (p - 1)p^{k - 1}$ si $p$ es primo y $k$ es un número natural. Es más,
$\varphi$ es una función multiplicativa condicional: si m y n son primos entre sí, entonces $\varphi(mn) = \varphi(m) \varphi(n)$ .

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.

[editar] 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.

[editar] Algunos valores

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

[editar] 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.

Ahora podemos 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)}$

[editar] Véase también

[editar] Referencias

Función φ de Euler

De Wikipedia, la enciclopedia libre

Contenido

[editar] Primeras propiedades y cálculo de la función

[editar] Ejemplo de cálculo

[editar] Algunos valores

[editar] Propiedades

[editar] Véase también

[editar] Referencias

Vistas

Herramientas personales

Buscar

Navegación

Crear un libro

Herramientas

En otros idiomas

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

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