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.

I need to solve this equation:

$x^2 = 1$ in the ring $\mathbb{Z}/n \mathbb{Z}$.

I know that $(n - 1)(n - 1) \equiv 1 \pmod n$, in general $(n-a)^2 \equiv a^2 \pmod n$.

I also know that for $p$ prime all elements of $\mathbb{Z}_p$ are invertible and here $1$ and $p-1$ are their own inverses.

Could you tell me what other solutions there are to this equation?

share|improve this question
2  
Notice my edit. It's standard TeX usage. –  Michael Hardy May 8 '13 at 21:39
    
Thanks, I'll remember that. –  Colby May 8 '13 at 22:21

1 Answer 1

up vote 5 down vote accepted

You need to solve it for each prime power dividing $n$, then combine the results with the Chinese Remainder Theorem.

For odd prime $p$, $x^2-1\equiv 0\pmod{p}$ has at most 2 solutions, and in fact exactly two since $1, -1$ are solutions. By Hensel's lemma, this will remain true for any power of $p$, since the derivative of $x^2-1$ is $2x\not \equiv 0\pmod{p}$.

However, for powers of 2, things get slightly more complicated. Mod 2, there is one solution (1). Mod 4, there are 2 solutions (1,-1). Mod any higher power of 2, there are four solutions. See here for an explanation.

Example: $n=280=2^357$. Four solutions mod 8, two mod 5, two mod 7, so there will be $4\cdot 2\cdot 2= 16$ solutions mod 280.

share|improve this answer
    
Related: math.stackexchange.com/questions/366756/… –  vadim123 May 8 '13 at 20:00

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.