Proving that if $m$ has a primitive root then $x^{n}\equiv 1 \pmod m$ has at most $n$ solutions?

Question

I'm stuck trying to prove this and need some help. I have cooked up a solution below and would love if someone can verify if it's correct.

First, the congruence is solvable provided $\varphi(m) \mid n$ because $a^n=a^{\varphi(m)t} \equiv 1 \pmod{m}$ via Euler's theorem.

Second, if $g$ is a primitive root (i.e. $g^{\varphi(m)}\equiv 1 \pmod m$), then we can write $x=g^{k}$ for some integer $k$. Then $x^{n}=g^{nk}\equiv 1 \pmod m$ has the same number of solutions as $ny \equiv 0 \pmod {\varphi(m)}$, which is equivalent to $ny=\varphi(m)d$ or $y=\frac{\varphi(m)d}{n}$ for some $d$.

We can take $d=0, 1, \dots, n-1$ to obtain possibly upto $n$ different solutions. The choice $d=n$ wouldn't give a new solution because $n\equiv 0 \pmod{\varphi(m)}$.

Answer 1

What you are arguing here can be in general extended to any cyclic group. Your argument seems to be correct except for "congruence has a solution provided $\varphi(m) | n$". Because $n$ can be even less than $\varphi(m)$. What you are showing is that if $\varphi(m)|n$, then the congruence has a solution.

In general, for a cyclic group $G$, we may adopt your reasoning. We also may argue in a different way as follows: Let us assume that order of $G=m$ and let $n<m$. Let $e$ be the identity element of the group. We are concerned about number of solutions to $$x^n =e$$, in $G$. Note that $n$ need not be a divisor of $m$. If $x$ satisfies the above equation, then order of $x$ say $p$, must divide $n$. Number of elements in G (cyclic) of order $p$ is $\varphi(p)$. Thus number of solutions to the above equation is at most $$\sum_{d|n} \varphi(d) = n$$. The reason for using the word 'at most' is that some of the divisors considered in the above sum may not be divisors of $m$. Since we count only those divisors which are the orders of some elements and since order of elements divide $m$, some divisors may miss in count.