¿Por qué la función totiente de Euler es igual a $(p-1)(q-1)$ cuando $N=pq$ y $p$ y $q$ son primordiales de una manera limpia e intuitiva?

Question

Tenía mi propia prueba para ello, pero realmente no me gusta (¡no se siente nada intuitivo porque requiere la factorización!) y siento que debe haber una manera más directa de hacerlo mediante un argumento de conteo diferente.

Si alguien tiene uno, se lo agradecerá mucho.

Mi "prueba":

Recuerdo:

$\phi(N) = $ el número de elementos que son relativamente primos a $N$ (es decir, tienen un mod inverso)

$N = pq$ donde $p$ y $q$ son primos.

Contemos el número de elementos entre $1$ a $N-1$ que NO son relativamente primordiales para $p$ y $q$ . Estos elementos deben tener al menos $p$ o $q$ como uno de sus factores. Así que incluyamos todos los números que tienen $p$ como factor y $q$ como factor y están en el rango dado.

así:

$0p, 1p, 2p, ..., kp, ..., p(q-1)$

y

$0q,1q,2q,...,jq,...,q(p-1)$

Eso da una cuenta de:

$N - p - q + 1 = pq - p - q + 1 = (p -1)(q-1)$

QED según sea necesario.

La razón por la que no estoy contento con este argumento es que me parece que debería haber una forma clara e intuitiva de hacerlo sin tener que factorizar o sustituir la definición de $N$ . Esto parece claro porque al multiplicar $(p-1)$ por $(q-1)$ parece ser una fórmula muy bonita y me sorprendería que fuera una coincidencia porque $(p-1)$ y $(q-1)$ también tienen interpretaciones claras. Estoy buscando un razonamiento claro más intuitivo, porque parece evidente por la forma de la fórmula que debe existir.

Answer 1

Convirtiendo mi comentario en una respuesta: Algunos resultados elementales en la teoría de números surgen de contar elementos en la teoría de grupos. Para cada número entero $n$ podemos construir el grupo $(\mathbb{Z}/n\mathbb{Z},+)$ cuyos elementos son los números enteros módulo $n$ y cuya operación es la adición.

También se puede pensar en hacer un grupo de los enteros módulo $n$ donde la operación es la multiplicación. Sin embargo, la mayor preocupación es que hay elementos no nulos que no son invertibles (el cero obviamente no es invertible). Por ejemplo, no se puede encontrar un $x$ para lo cual $3x \equiv 1 (\operatorname{mod} 6)$ Así que $3$ no es invertible módulo $6$ . Para hacer un grupo multiplicativo módulo $n$ tenemos que desechar los elementos no invertibles. Escribimos este grupo como $((\mathbb{Z}/n\mathbb{Z})^{\times},\times)$ . Es un ejercicio fácil que $m$ es multiplicativamente invertible módulo $n$ si $m$ y $n$ son coprimos. Por lo tanto, el orden de $(\mathbb{Z}/n\mathbb{Z})^{\times}$ es $\varphi(n)$ .

Su resultado es que si $p,q$ son primos, entonces $$\varphi(pq) = (p-1)(q-1) = \varphi(p)\varphi(q)$$

$\varphi(pq)$ es el orden de $(\mathbb{Z}/(pq)\mathbb{Z})^{\times}$ mientras que $\varphi(p)\varphi(q)$ es el orden de $(\mathbb{Z}/p\mathbb{Z})^{\times} \times (\mathbb{Z}/q\mathbb{Z})^{\times}$ . Su resultado dice que estos grupos tienen el mismo tamaño. De hecho, es más cierto: ¡son el mismo grupo (isomorfo)! Esto es parte de (una forma de) la Teorema chino del resto . Así que, para un argumento más "sano" (si no estás contento con tu prueba actual), puedes decir que estos números son iguales porque están contando los elementos del mismo objeto, pero de diferentes maneras.

Answer 2

Una solución muy diferente utiliza la fórmula clásica $$ \sum_{d \mid n} \phi(d) = n. $$ Una forma de ver esto es considerar las fracciones $1/n, \ldots, n/n$ en términos mínimos. Para $d \mid n$ agrupa las fracciones con denominador $d$ juntos; hay $\phi(d)$ de ellos, como se puede comprobar fácilmente. Por lo tanto, la suma de $\phi(d)$ sobre todos esos $d$ cuenta cada uno de los $n$ fracciones una vez.

De aquí puedes deducir inmediatamente tu caso particular sin necesidad de factorizar: $(1+\phi(p))(1+\phi(q)) = pq = 1+\phi(p)+\phi(q)+\phi(pq)$ . Expandir el lado izquierdo y cancelar para obtener $\phi(p)\phi(q) = \phi(pq)$ .

Esto funciona en general: primero anote $$ \sum_{d \mid n,\ e \mid m} \phi(d) \phi(e) = \sum_{d \mid n} \phi(d) \sum_{e \mid m} \phi(e) = nm = \sum_{f \mid nm} \phi(f). $$ Supongamos ahora que ${\rm gcd}(n, m) = 1$ Así que ${\rm gcd}(d, e) = 1$ siempre. Inductivamente suponer $\phi(de) = \phi(d)\phi(e)$ para $(d, e) \neq (n, m)$ (el caso base es trivial). Puede comprobar la operación $f \mapsto (d, e) = ({\rm gcd}(f, n), {\rm gcd}(f, m))$ mapea el conjunto de índices del lado derecho en el lado izquierdo de forma biyectiva, con la propiedad de que $de=f$ . Por lo tanto, inductivamente cada término excepto el "más alto", donde ( $f=nm, d=n, e=m$ ), se cancela. Pero eso dice $\phi(n)\phi(m) = \phi(nm)$ según sea necesario.