# Show that number of elements $\overline a\in\mathbb Z/n\mathbb Z$ with order $\overline a=d\mid n$ equals $\phi(d)$

Consider $\mathbb Z/n\mathbb Z$ for some $n\in\mathbb Z_{>0}$. Let $d$ be a positive divisor of $n$. Show that the number of elements $\overline a\in\mathbb Z/n\mathbb Z$ ($1\leq a\leq n$) with $\operatorname{order}(\overline a)=d$ is equal to $\phi(d)$, which is defined as $\mid\{a\in\mathbb Z\mid 1\leq a\leq n,\gcd(a,n)=1\}\mid$.

Now my book says that $\operatorname{order}(\overline a)=d$ means the same as $\gcd(a,n)=n/d$, which is equivalent to $$a=b\cdot\frac{n}{d}\quad\text{with }\gcd(b,d)=1\text{ and }1\leq b\leq d.$$ Because we can find $\phi(d)$ such $b$’s, the proof is complete.

I don't understand where this $b$ comes from. I understand that \begin{align}\exists m\in\mathbb Z:a=m\cdot\frac{n}{d}\end{align}, but apparently we can say more about this $m$. It is clear that $1\leq m\leq d$. Assume $\gcd(m,d)=k>1$. I'm guessing we need some contradiction with the fact that $n/d$ is the greatest common divisor of $a$ and $n$, but I can't see how. Could someone give me a hint?

## 1 Answer

In what follows, (1) is justified by the following simple and useful proposition: in any group $G$, $\operatorname{order}\left(g^k\right) = \frac {\operatorname{order} g} {\gcd(\operatorname{order} g, k)}$ for any element $g$, assuming $\operatorname{order} g$ is a positive integer. Note: here notation $g^k$ corresponds to group operation being written multiplicatively. In your case it would be written additively, namely $kg$.

Let $a = m \cdot \frac n d$. Then

\begin{align*}\operatorname{order}\bar a &= \operatorname{order}\left( m \cdot \frac n d \cdot \bar 1\right) \\ (1)&= \frac{\operatorname{order} \bar 1}{\gcd(\operatorname{order} \bar 1, m \cdot \frac n d)} \\ &= \frac n {\gcd(n,m\cdot \frac n d)} \\ &= \frac n {\gcd(d \cdot \frac n d, m \cdot \frac n d)} \\ &= \frac n {\gcd(d, m) \cdot \frac n d} \\ &= \frac d {\gcd(d,m)} \end{align*}

Thus, $\operatorname{order}\bar a = d \iff \gcd(d,m) = 1$.