# Number of roots

Would I be right in thinking that $x^m\equiv 1 (\mod n)$ has only $m$ distinct roots? If not, would it be true if m,n are coprime or simply distinct primes? My gut feeling is that there should ony be m roots, but I don't know how to prove it.

-
I assume you mean distinct mod $n$, right? –  lhf Jan 27 '12 at 10:33

This is not true in general. For instance, $x^2\equiv 1\bmod 8$ has 4 solutions. More generally, if $n$ is a power of 2 then $x^2\equiv 1\bmod n$ has $n/2$ solutions.

If $n$ is prime, then $x^m\equiv 1\bmod n$ has at most $m$ solutions because $\mathbb Z/(n)$ is a field.*

If $n$ is a prime, the number of solutions of $x^m\equiv 1\bmod n$ depends on the gcd of $m$ and $\varphi(n)=n-1$. This holds in general for $n$ a prime power or twice a prime power with the appropriate value of $\varphi(n)$, where $\varphi$ is Euler's totient.

In general, the exact number of solutions is not known. See http://en.wikipedia.org/wiki/Root_of_unity_modulo_n.

[*] A polynomial equation of degree $m$ over a field has at most $m$ solutions. This is easily proved by induction. If the equation has no solution, you're done. If $a$ is a solution, you can factor $x-a$ and you're left with an equation of degree $m-1$.

-
According to Maple $x^2 \equiv 1 \pmod 8$ has $2$ solutions.. –  pedja Jan 27 '12 at 9:58
@pedja: $1^2\equiv 1$, $3^2=9\equiv 1$, $5^2=25\equiv 1$, $7^2=49\equiv 1$. WA gets it right. –  lhf Jan 27 '12 at 10:01
,Yes you are right...but why don't count negative solutions also ? $(-1)^2 \equiv 1 \pmod 8$ –  pedja Jan 27 '12 at 10:03
$-1,-3,-5,-7$ are also solutions of $x^2 \equiv 1 \pmod 8$ –  pedja Jan 27 '12 at 10:08
@pedja But $-1 \equiv 7 \pmod 8, -3 \equiv 5 \pmod 8,-5 \equiv 3 \pmod 8$ and $-7 \equiv 1 \pmod 8$, so they are in our list already! –  Galois Group Jan 27 '12 at 10:15