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
    @lhf: Thanks! :)2012-01-27