El uso de Euler totient función de un gran número de

Question

Así que tengo una prueba en un par de horas y estoy teniendo problemas para encontrar información sobre cómo utilizar el de Euler totient función de un gran número así que me pregunto si alguien me podría dar paso a paso las instrucciones? :)

Aquí se muestra un ejemplo de pregunta para la prueba:

Encontrar $\psi(93296)$.

Podría también dar instrucciones sobre cómo encontrar el primer factorización así? He utilizado una calculadora en línea y es $2^4 * 7^3 * 17$ pero no sé cómo calcular esto.

Answer 1

Euler totient función da todos los números que son primos relativos a $n$, que están por debajo de $n$. Esta es la fórmula de Euler:

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

In order to use the formula, we must first prime factorize $n$. Let's take a smaller number first. Suppose you want to use $\psi(n)$ for $36$ as stated in the wiki article. Then you would take the following steps.

1. Prime factorize $n$
2. A continuación, aplicar el "sub" (distinto) $p$ y continuará haciéndolo hasta que se han ejecutado de las distintas $p$'s

Así, en primer lugar para la factorización prima de $36$ o cualquier número. Aquí está el proceso.

    Divide n by p
    if n mod p = 0 then continue to divide by n
    if not then move onto the next prime
    You are done when you are left with a prime number

Para $36$ sería el siguiente proceso:

$36/2 = 18 \rightarrow $18 todavía es divisible por 2, por lo que continuará

$18/2 = 9 \rightarrow 9$ es impar y por lo tanto no divisible por $2$. Pasar a la siguiente prime, $3$

$9/3 = 3 \rightarrow 3$ es una de las principales y que están completos.

Por lo tanto, los factores primos de a$36$: $2,2,3,3$ o en otras palabras $2^2*3^2$. Una vez que tenemos los factores primos de a $n$ podemos usar la función.

$$\begin {align} &\psi(n) = n \prod_{p|n} \left(1- \frac{1}{p}\right)\\ &\psi(36) = 36 \prod_{p|n} \left(1- \frac{1}{2}\right)\left(1- \frac{1}{3}\right)\\ &=12 \end{align}$$

Therefore, there are $12$ below $36$ that are relatively prime to $36$.

For the example that you have provided it would look something like this:

$$\begin {align} &\psi(n) = n \prod_{p|n} \left(1- \frac{1}{p}\right)\\ &\psi(93296) = 93296 \prod_{p|n} \left(1- \frac{1}{2}\right)\left(1- \frac{1}{7}\right)\left(1- \frac{1}{17}\right)\\ &=37632 \end{align}$$

This is the basic process to use the Totient function, note that there are various other formulas that one can use, I find that this one is the easiest to understand. Furthermore, prime factorization should not be difficult if you know the primes below $100$.

P. S Para la práctica, usted puede comprobar sus respuestas aquí

Answer 2

$ψ(93296)=ψ(2^4)\timesψ(7^3)\timesψ(17)$ =$(2^4-2^3)\times(7^3-7^2)\times(17-1)$ =$8\times294\times16$ =$37632$