¿Por qué $\phi(pq)=\phi(p)\phi(q)$?

Question

En un papel RSA estoy leyendo se supone que donde $p$ y $q$ son números primos distintos:

$\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$

¿Me encantaría saber por qué y cómo que esto es así? ¿Hay alguna forma de probar esto?

Answer 1

Los enteros positivos a menos de $pq$ que no relativamente primer a $pq$ son positivos múltiplos de $p$ menos de $pq$ y la positiva múltiplos de $q$ menos de $pq$. Los positivos múltiplos de $p$ menos de $pq$ son los números de $kp$$k=1,2,\dots,q-1$, por lo que hay $q-1$ de ellos. Del mismo modo, los positivos múltiplos de $q$ menos de $pq$ son los números de $kq$$k=1,2,\dots,p-1$, por lo que hay $p-1$ de ellos. Por lo tanto, hay un total $(p-1)+(q-1) = p+q-2$ enteros positivos a menos de $pq$ que no relativamente primer a $pq$.

Hay un total $pq-1$ enteros positivos a menos de $pq$, por lo que debe ser $$(pq-1)-(p+q-2) = pq-p-q+1 = (p-1)(q-1)$$ positive integers less than $pq$ that are relatively prime to $pq$. Thus, $\varphi(pq) = (p-1)(q-1) =$ $\varphi(p)\varphi(q)$.

Answer 2

Lo que están pidiendo es un caso especial de la multiplicativity de la totient función de $\varphi$. En general, una función de $f: \mathbb{Z}^+ \rightarrow \mathbb{R}$ es multiplicativa si para todas las $n_1$ $n_2$ con $\operatorname{gcd}(n_1,n_2) = 1$, $f(n_1 n_2) = f(n_1) f(n_2)$. (No se podría haber esperado que la definición para incluir la restricción de que el $n_1$ $n_2$ no tienen ningún factor común: las funciones que satisfacen $f(n_1 n_2) = f(n_1) f(n_2)$ para todos los $n_1,n_2 \in \mathbb{Z}^+$ son llamados completamente multiplicativa. Pero esta última propiedad es de alguna manera demasiado fuerte: muchos de los más comunes "aritmética", las funciones estudiadas en las escuelas primarias y la teoría analítica de números son multiplicativos, pero muy pocos son completamente multiplicativa. Por ejemplo, $\varphi$ no es completamente multiplicativa: para cualquier número primo $p$, $\varphi(p^2) = p^2 -p = p(p-1) \neq (p-1)^2 = \varphi(p) \varphi(p)$.)

Un elemental de la prueba (bueno, nunca he visto a ningún otro tipo...) de la multiplicativity de $\varphi$ utilizando el Teorema del Resto Chino se puede encontrar en $\S 2.4$ de estas notas. Sabiendo que $\varphi$ es multiplicativo conduce a una fórmula explícita para $\varphi(n)$ en términos de la descomposición en factores primos de a $n$, ya que para cualquier potencia principal $p^a$, los números entre el $1$ $p^a$ que son relativamente primos a $p^a$ son precisamente los que están no múltiplos de $p$, lo $\varphi(p^a) = p^a - p^{a-1} = p^{a-1}(p-1)$. Por un segundo (aún la primaria!) la prueba de la multiplicativity de $\varphi$, ver $\S 2.1$ de estas notas. Esta última prueba se utiliza el Möbius de la Inversión de la Fórmula.