4
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Notice my edit. It's standard TeX usage. $\endgroup$ May 8, 2013 at 21:39
  • $\begingroup$ Thanks, I'll remember that. $\endgroup$
    – Colby
    May 8, 2013 at 22:21

1 Answer 1

6
$\begingroup$

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^3\cdot 5\cdot 7$. Four solutions mod 8, two mod 5, two mod 7, so there will be $4\cdot 2\cdot 2= 16$ solutions mod 280.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .