La Enciclopedia Libre Universal en Español dispone de una lista de distribución pública, enciclo@listas.us.es

Función fi de Euler

Artículo de la Enciclopedia Libre Universal en Español.

Saltar a navegación, buscar

La función Φ de Euler es una función aritmética, de argumento natural (no nulo) y que da como resultado también un entero natural.

Índice

1 I Definición
2 II Ejemplos
3 III Fórmulas
4 IV Vínculo con los polinomios ciclotómicos
5 V Otras fórmulas

[escribe] I Definición

Para todo natural n>1 φ(n) es el número de elementos inversibles del anillo cíclico Z/nZ (también escrito Z_n).
Aunque Z/1Z no es propiamente un anillo (sus dos leyes «+» y «×» se confunden) , tiene un único elemento inversible, y por tanto se extiende Φ con Φ(1) = 1. No se define Φ(0).

Los inversibles de Z_n corresponden a los $\overline {m}$ tales que m es coprimo con n; con 0 < m ≤ n. Esto da una definición alternativa de Φ:

Φ(n) = Card {m ∈ [1; n], mcd(m,n) = 1}

Donde « Card » designa el cardinal o número de elementos de un conjunto, y « mcd » es el máximo común divisor de los dos naturales.

[escribe] II Ejemplos

Los coprimos con 12 = 2²×3 y menor que él son los que no tienen ni 2 ni 3 en su descomposición en factores primos : 1;5;7 y 11. Luego Φ(12) = 4.

Los coprimos con 13 menor que él son todos los enteros entre 1 y 12, pues 13 es un número primo. Luego Φ (13) = 12.

Los coprimos con 14 = 2 × 7 son los impares no múltiples de 7: 1; 3;5;9;11 y 13: Luego Φ(14) = 6.

Estos tres ejemplos permiten intuir que cuando más factores aparezcan en la descomposición en primos, menor será el valor de Φ(n). Con un mismo número de factores, Φ(n) tiende a crecer con n porque el intervalo [1; n] da cabida a más elementos con n grande.

Miremos los primeros valores de Φ:

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35
Φ(n)	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10	22	8	20	12	26	12	28	8	30	16	20	16	24

No se percibe ningun orden subyaciente, lo que no es de extrañar porque esta función depende de la descomposición en primos, que es muy irregular.
A parte de los dos primeros valores, Φ(n) es siempre par (esto se debe a que los factores p-1, con p primo, son pares excepto cuando p = 2; ver la fórmula más abajo).

Aquí están representados los quinientos primero valores. En el caos ambiente, se observan ...puntos alineados sobre varias rectas, que corresponden a tipos particulares de valores de n: n primo, n doble , triple o sextuple de un número primo.

[escribe] III Fórmulas

Estas propiedades permiten calcular Φ(n) para todos los valores de n.

Para todo primo p, Φ(p) = p-1.

En efecto, un primo es coprimo con todos los enteros que no son sus múltiplos, en particular con los del intervalo [1; p-1].

Φ(p^r) = p^r - p^r-1, con p primo y r > 0 natural.

Los enteros no coprimos con p^r son los múltiplos de p, y hay

$\frac{p^r} p = p^{r-1}$

de ellos en el intervalo [1, p^r].

Por ejemplo, los coprimos con 25 en [1;25] son todos menos 5; 10; 15; 20 y 25, lo que da: Φ(25) = 25 5 = 20.

Si m y n son coprimos, entonces Φ(m·n) = Φ(m)· Φ(n). Esta propiedad se llama multiplicatividad condicional (la condición es : m y n coprimos) .

Esto se debe al isomorfismo entre Z_m·n y el producto de anillos cíclicos Z_m × Z_n. Los inversibles de Z_m·n corresponden a las parejas de inversibles (a,b) con a inversible en Z_m y b inversible en Z_m·n. Hay Φ(m) valores posibles para a y Φ(n) valores posibles para b, luego hay Φ(m)· Φ(n) parejas posibles.
Por ejemplo, Z₂ posee 1 como único inversible, Z₃ tiene dos inversibles: 1 y 2. Los inversibles de Z₆ son dos, que corresponden a (1,1) y (1,2) (son 1 y 5).

Con estas reglas se puede enunciar la fórmula general:

Para

$n = p_1^{r_1} p_2^{r_2}... p_k^{r_k}$

, tenemos :

$\Phi (n) = ( p_1^{r_1}- p_1^{r_1 -1} ) (p_2^{r_2} - p_2^{r_2-1} )... (p_k^{r_k}- p_k^{r_k -1})$

Se ha aplicado la tercera regla a los factores

$p_i^{r_i}$

(con 1 ≤ i ≤ k) que son coprimos.

Se puede simplificar esta expresión factorizando por n:

$\Phi (n) = p_1^{r_1}(1 - \frac {1} {p_1}) p_2^{r_2}(1 - \frac {1} {p_2}) ...p_k^{r_k}(1 - \frac {1} {p_k})$

$= p_1^{r_1}p_2^{r_2}...p_k^{r_k}(1 - \frac {1} {p_1}) (1 - \frac {1} {p_2}) ...(1 - \frac {1} {p_k}) = n (1 - \frac {1} {p_1}) (1 - \frac {1} {p_2}) ...(1 - \frac {1} {p_k})$

Finalmente:

$\Phi (n) = n \prod_{i=1}^k (1 - \frac {1} {p_i})$

donde los p_i son los distintos factores primos de n

El factor

$\prod_{i=1}^k (1 - \frac 1 {p_i})$

puede ser tan pequeño como se quiere , porque el producto infinito

$\prod_{p \isin P} (1 - \frac 1 {p})$

diverge hacia cero (P es el conjunto de todos los primos).

Así, la fracción

$\frac {\Phi (n)} {n}$

tiene como límite inferior cero, límite aproximado por los Φ (2 × 3 × 5 × ... p)

con p primo:

$\frac{\Phi (2)}{2} = \frac 1 2 , \frac {\Phi (6)}{6} = \frac 1 3, \frac{\Phi (30)}{30} = \frac 4 {15} \sim 0,27 , \frac {\Phi (210)}{210}= \frac 8 {35} \sim 0,23 ...$

[escribe] IV Vínculo con los polinomios ciclotómicos

Teorema:

El grado del enésimo polinomio ciclotómico es Φ(n)

Aquí radica buena parte del interés de la función Φ pues los polinomios ciclotómicos son muy importantes en aritmética y en álgebra, en particular en las extensiones de cuerpos.

Prueba:

Se recuerda que las raíces de los polinomios ciclotómicos son las raíces primitivas de orden n de la 1, es decir que verifican zⁿ = 1 pero z^d ≠ 1 cuando 0 < d < n. Esto significa que este z es de orden n (como elemento de grupo), es decir que genera todo el grupo de las raíces de orden n (hay n raíces).

En el cuerpo de los complejos, se sabe que el grupo de las raíces de orden n de 1 es U_n = { 1, ω , ω², ω³ ... ω^n-1 }, con $\omega = e^{\frac {2 \pi i} n }$

La aplicación :

(Z, + ) → (U_n, · )

k → ω^k

es un morfismo de grupo ( ω^{k + k'} = ω^k · ω^k') cuyo núcleo es nZ; por tanto se factoriza en :

Z/nZ → U_n, que es un isomorfismo.

Los generadores de U_n corresponden por esta biyección a los del anillo cíclico Z_n = Z/nZ, y tantos de unos como de otros, es decir Φ(n).

Más concretamente, las raíces primitivas son los ω^k, con k y n coprimos, 0 < k < n.

Las raíces de orden n verifican zⁿ = 1, pero en general n no es el menor exponente positivo posible en esta igualdad. El conjunto de los m tal que z^m = 1 forma un subgrupo de Z, y es por tanto de la forma dZ, con d el menor positivo no nulo tal que z^d = 1. Por definición, z es una raíz primitiva de orden d, y está contabilizada en Φ(d). Como n ∈ dZ, d divide n.
Recíprocamente, si z^d = 1 entonces zⁿ = 1 porque n es múltiplo de d.
En conclusión: las n raíces de zⁿ = 1 son exactamente las raíces primitivas de orden d, con d divisor positivo cualquiera de n, lo que lleva a la fórmula: