probar que$\phi(xy) =\phi(x)\phi(y)$ para cualquier$x$ y$y$ con$(x, y) = 1$.

Question

Demuestre que$\phi(xy) = \phi(x) \phi(y)$ para cualquier$x$ y$y$ con$(x, y) = 1$.

Entiendo el concepto, y he hecho varios ejemplos de prueba de esto pero no puedo ponerlo en "forma de prueba" porque a menos que sea un contraejemplo, no puede ser probado simplemente usando los números que tengo de una tabla.

Answer 1

Si has visto una prueba de la fórmula $$\sum\limits_{d \mid n} \phi(d) = n$$ ($d$ runs through all the positive divisors of $n$, including $1$ and $n$), you can actually deduce the multiplicativity of $\phi$ desde aquí. La regla anterior en sí no es difícil de demostrar, y requiere poco más que una buena intuición sobre el máximo común divisor de dos números. Me puede dar una prueba de la regla anterior, si lo desea.

Por ejemplo, vamos a utilizar la fórmula anterior para mostrar que $\phi(pq) = \phi(p)\phi(q)$ para distintos números primos $p$$q$. Los divisores de $pq$$1, p, q, pq$, por lo que $$pq = \phi(1) + \phi(p) + \phi(q) + \phi(pq) = 1 + (p-1) + (q-1) + \phi(pq)$$ which implies $$\phi(pq) = pq + 1 - p - q = (p - 1)(q-1) = \phi(p) \phi(q)$$ El caso general de multiplicativity puede ser igual de hecho, aunque requiere cierta difícil de inducción.

Answer 2

El teorema del resto chino indica que siempre podemos resolver por separado

ps

para números primos distintos$$\begin{cases}a\equiv b_1\mod p_1^{\alpha_1} \\ \vdots \\a\equiv b_n\mod p_n^{\alpha_n}\end{cases}$

Entonces, dado que hay$p_i$ opciones para las clases de equivalencia mod$\varphi(p_i^{\alpha_i})$ coprime para el módulo para cada una de las elecciones independientes, la cantidad total de números coprime a$p_i^{\alpha_i}$ es

ps