Step in proof Sum of Euler Phi Function over Divisors

Question

I want to show Gauss’ formula. The proof in my book starts as follows: Let $d$ be a positive divisor of $n$. We show that the number of elements $\overline a\in\mathbb Z/n\mathbb Z$ with $\operatorname{order}(\overline a)=d$ equals $\phi(d)$ (where $\phi$ is Euler’s function). I’ve already shown that $\operatorname{order}(\overline a)=n/\gcd(a,n)$. So we can write $\gcd(a,n)=n/d$. Now my book says this is equivalent to saying $$ a=b\cdot\frac{n}{d}\text{ where }\gcd(b,d)=1\text{ and }1\leq b\leq d. $$ I don't understand why this last bit is equivalent. I understand that we can write $a=k\cdot\dfrac{n}{d}$ for some $k\in\mathbb Z$, because $\dfrac{n}{d}$ is a divisor of $a$ after all - but I don't understand why it holds that $\gcd(b,d)=1$? I would guess that if $\gcd(b,d)>1$, then we have a contradiction with $n/d=\gcd(a,n)$, but I'm not sure. Could someone help me out?

Answer 1

If $\mathrm{gcd}(b, \, d)=m>1$ then you can divide both $b$ and $d$ by $m$, obtaining $a=b'\frac{n}{d'}$ with $d'<d$. Then $n/d'$ would be a common divisor of $a$ and $n$ strictly greater than $n/d=\mathrm{gcd}(a, \, n)$, contradiction.