Paso en la prueba Suma de la función de Euler Phi sobre los divisores

Question

Quiero mostrar la fórmula de Gauss. La prueba en mi libro comienza como sigue: Sea $d$ sea un divisor positivo de $n$ . Demostramos que el número de elementos $\overline a\in\mathbb Z/n\mathbb Z$ con $\operatorname{order}(\overline a)=d$ es igual a $\phi(d)$ (donde $\phi$ es la función de Euler). Ya he demostrado que $\operatorname{order}(\overline a)=n/\gcd(a,n)$ . Así que podemos escribir $\gcd(a,n)=n/d$ . Ahora mi libro dice que esto es equivalente a decir $$ a=b\cdot\frac{n}{d}\text{ where }\gcd(b,d)=1\text{ and }1\leq b\leq d. $$ No entiendo por qué esta última parte es equivalente. Entiendo que podemos escribir $a=k\cdot\dfrac{n}{d}$ para algunos $k\in\mathbb Z$ porque $\dfrac{n}{d}$ es un divisor de $a$ después de todo - pero no entiendo por qué sostiene que $\gcd(b,d)=1$ ? Supongo que si $\gcd(b,d)>1$ entonces tenemos una contradicción con $n/d=\gcd(a,n)$ pero no estoy seguro. ¿Podría alguien ayudarme?

Answer 1

Si $\mathrm{gcd}(b, \, d)=m>1$ entonces puede dividir ambos $b$ y $d$ por $m$ , obteniendo $a=b'\frac{n}{d'}$ con $d'<d$ . Entonces $n/d'$ sería un divisor común de $a$ y $n$ estrictamente mayor que $n/d=\mathrm{gcd}(a, \, n)$ contradicción.