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$.
-
0According to Maple $x^2 \equiv 1 \pmod 8$ has $2$ solutions.. – 2012-01-27
-
3@pedja: $1^2\equiv 1$, $3^2=9\equiv 1$, $5^2=25\equiv 1$, $7^2=49\equiv 1$. [WA](http://www.wolframalpha.com/input/?i=x%5E2+%3D+1+mod+8) gets it right. – 2012-01-27
-
0,Yes you are right...but why don't count negative solutions also ? $(-1)^2 \equiv 1 \pmod 8$ – 2012-01-27
-
1$-1,-3,-5,-7$ are also solutions of $x^2 \equiv 1 \pmod 8$ – 2012-01-27
-
0@lhf: Thank you :) Would you mind expanding on the field idea, I have looked up what a field is, but how does it imply the result? thanks again! – 2012-01-27
-
1@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! – 2012-01-27
-
0@GregEvans, see my expanded answer. You may want to read about [primitive roots](http://en.wikipedia.org/wiki/Primitive_root_modulo_n) if you haven't already. – 2012-01-27
-
0@lhf: Thanks! :) – 2012-01-27