Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I assume you mean distinct mod $n$, right? –  lhf Jan 27 '12 at 10:33

1 Answer 1

up vote 7 down vote accepted

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$.

share|improve this answer
    
According to Maple $x^2 \equiv 1 \pmod 8$ has $2$ solutions.. –  pedja Jan 27 '12 at 9:58
3  
@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  
$-1,-3,-5,-7$ are also solutions of $x^2 \equiv 1 \pmod 8$ –  pedja Jan 27 '12 at 10:08
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! –  Ravi Donepudi Jan 27 '12 at 10:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.