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.
Number of roots
-
0I assume you mean distinct mod $n$, right? – 2012-01-27
1 Answers
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$.
-
0@lhf: Thanks! :) – 2012-01-27