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

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)}$$.

• Does this answer your question? Does the equation $x^n\equiv 1\pmod p$ has at most $n$ solutions? May 19, 2021 at 9:36
• @ParclyTaxel, the proof there assumes $p$ is a prime. Here $m$ is possibly composite. Moreover, I'm looking to see if my proof is correct. May 19, 2021 at 9:40

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. 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.