# Step in proof Sum of Euler Phi Function over Divisors

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?

## 1 Answer

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.

• Oh right, I didn't realise $n/d'$ would be greater, and I also didn't realise we could divide with this $m$, because I didn't realise $b$ is in the numerator and $d$ in the denominator. Thanks! – Sha Vuklia Jun 26 '17 at 19:24