Cálculo de los valores de la función totiente de Euler.

Question

Nunca entendí cómo calcular los valores de la función totiente de Euler. ¿Alguien puede ayudar?

Por ejemplo, ¿cómo puedo calcular $\phi(2010)$ ?

Tengo entendido que hay una fórmula de producto, pero es muy diferente de los productos normales, así que ¿cómo debo hacerlo? Gracias.

Answer 1

De Wikipedia: si $\displaystyle n=p_1^{k_1}\cdots p_r^{k_r}$ entonces

$\varphi(n)=\varphi(p_1^{k_1})\varphi(p_2^{k_2})\cdots\varphi(p_r^{k_r})=p_1^{k_1}\left(1- \frac{1}{p_1}\right)p_2^{k_2}\left(1-\frac{1}{p_2}\right)\cdots p_r^{k_r}\left(1-\frac{1}{p_r} \right)=$

$=n\cdot\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right)$

Así que tendrás que encontrar todos los diferentes factores primos $p_1,\cdots,p_r$ de n.

Answer 2

Me parece que para entender cómo calcular los valores de la función totiente de Euler hay que entender primero lo que hace la función. Sin esa comprensión, todas las fórmulas del mundo son inútiles.

Unos cuantos ejemplos más pequeños, pero bien elegidos, también podrían ser de gran ayuda. Primero pensemos en $\phi(3) = 2$ y la secuencia de tercios de $\frac{1}{3}$ a $1$ : $$\frac{1}{3}, \frac{2}{3}, \frac{3}{3}.$$ Se pueden reescribir como $$\frac{1}{3}, \frac{2}{3}, 1.$$ Dos de estas fracciones retuvieron $3$ como denominador.

Ahora considere $\phi(6) = 2$ . Considere también la secuencia de sextas desde $\frac{1}{6}$ a $1$ : $$\frac{1}{6}, \frac{2}{6}, \frac{3}{6}, \frac{4}{6}, \frac{5}{6}, \frac{6}{6}.$$ Se pueden reescribir así: $$\frac{1}{6}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{5}{6}, 1.$$ Sólo dos de ellos conservaron $6$ como denominador.

Considerar a continuación $\phi(12) = 4$ . Consideremos también la secuencia de doceavas partes de $\frac{1}{12}$ a $1$ : $$\frac{1}{12}, \frac{2}{12}, \frac{3}{12}, \frac{4}{12}, \frac{5}{12}, \frac{6}{12}, \frac{7}{12}, \frac{8}{12}, \frac{9}{12}, \frac{10}{12}, \frac{11}{12}, \frac{12}{12}.$$ Se pueden reescribir así: $$\frac{1}{12}, \frac{1}{6}, \frac{1}{4}, \frac{1}{3}, \frac{5}{12}, \frac{1}{2}, \frac{7}{12}, \frac{2}{3}, \frac{3}{4}, \frac{5}{6}, \frac{11}{12}, 1.$$ Sólo cuatro de ellos conservaron $12$ como denominador.

Pero más importante que eso, fíjese en dónde está el $12$ s: los numeradores correspondientes son $1, 5, 7, 11$ y $7 = 1 + 6$ y $11 = 5 + 6$ . Es como si duplicáramos la estructura de las sextas y la lleváramos a las doce. ¿Entiendes en qué sentido es diferente pasar de sextas a doceavas que pasar de terceras a sextas?

Esa diferencia no tiene por qué preocuparnos en su ejemplo de $2010$ ya que ese número es libre de cuadrados:

• $\phi(67) = 66$ . Al escribir sesenta y siete de $\frac{1}{67}$ a $1$ no podrá cambiar el numerador de ninguno de ellos, excepto de $\frac{67}{67}$ .
• $\phi(5) = 4$ y $\phi(335) = 264$ . De los enteros entre $1$ y $335$ sesenta y siete de ellos son divisibles por $5$ y cinco son divisibles por $67$ pero sólo uno de ellos es divisible por ambos $5$ y $67$ (y eso es $335$ mismo). Aviso: $335 - 5 - 67 = 263$ (esto cuenta de más $335$ ).
• $\phi(3) = 2$ y $\phi(1005) = 528$ . Dejo esto para que lo resuelvas tú mismo.
• $\phi(2) = 1$ y $\phi(2010) = 528$ . Aquí tenemos el doble de números que tratar, pero el doble de un número impar es un número par que, por supuesto, es divisible por $2$ Así que si realmente nos preocupamos por escribir fracciones de $\frac{1}{2010}$ a $1$ podríamos cambiar el denominador en al menos la mitad de ellos, así que multiplicando por $2$ no nos hace ganar realmente coprimas...

Answer 3

Si se tiene en cuenta que la función totiente es multiplicativa $\phi(ab)=\phi(a)\phi(b)$ y que $\phi(p^n)=p^n-p^{n-1}$ para cualquier primo $p$ un simple cálculo da como resultado $$\phi(n)=n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)$$ donde $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ es la descomposición primaria de $n$

Answer 4

El hecho más importante a recordar es que la función totiente de Euler es multiplicativa, condicionada a la coprimalidad. Si $\gcd(m, n) = 1$ entonces $\phi(mn) = \phi(m) \phi(n)$ .

Por ejemplo, $\phi(2010) = \phi(2) \phi(3) \phi(5) \phi(67) = 1 \times 2 \times 4 \times 66 = 528$ . Esta es fácil porque el número es libre de cuadrados. Hay que tener un poco más de cuidado cuando el número no es libre de cuadrados.