6
$\begingroup$

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.

  • 0
    I assume you mean distinct mod $n$, right?2012-01-27

1 Answers 1

6

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