Quantity of elements of order $d$ in $Z_n$, with $d \mid n $

Question

I'm studying for an exam and I can't answer this problem. I'd appreciate a hint.

What I've got so far:

Let $x$ be an element or order $d$. Then, $x\cdot d \equiv 0 \pmod n \Rightarrow n \mid x\cdot d$.

And, on the other hand, obviously $n \mid d\ .\ n$

$n$ divides each factor $\Rightarrow n\mid \gcd(x\cdot d,d\cdot n)\ =\ d\cdot \gcd(x,n) \Rightarrow \frac{n}{d} \mid \gcd(x,n)$

My guess is that there are at most two elements (if they are different mod $n$): $\pm \frac{n}{d}$

Answer 1

Let $G=Z_n$, and by Fundamental theorem of cyclic groups, there exists unique subgroup of order $d$ in $G$, if $d\mid n$, call it $H=\langle a\rangle$. Now every element of order $d$ must generate $H$, and how many generators does $\langle a \rangle$ have? You must have done it, right?

Generators of $\langle a\rangle$ are elements of the form $a^k$ where gcd$(k,n)=1$. This number is called Euler totient function denoted by $\phi(n)=\{k\in Z : 1\le k \le n, (k,n)=1 \}$. So number of elements of order $d$ in $G=Z_n$ is $\phi(n)$