# Is $x^2 \equiv 1 \pmod{p^k} \iff x \equiv \pm 1 \pmod {p^k}$ for odd prime $p$?

Problem: As the title says, is $x^2 \equiv 1 \pmod {p^k} \iff x \equiv \pm 1 \pmod {p^k}$ for odd prime $p$? If not, is it at least true that there are two solutions to the congruence equation?

Attempt: I am a beginner in number theory, and I am not sure if the statement in question is true. The following is my attempt. Assume $x^2 \equiv 1 \pmod {p^k}$. Then $p^k | (x-1)(x+1) \Rightarrow p^k|(x-1)$ or $p^k|(x+1)$, because if $p^k$ can divide both, then $p^k|2$ which is false. This shows the forward direction.

The converse is easy.

For any $y^2 \equiv 1 \pmod {p^k}$, $y^2 \equiv x^2 \pmod {p^k}$ which yields the conclusion before, so $\pm 1$ are the only solutions $\pmod {p^k}$.

The idea is essentially correct, but you have to be more careful in the step $p^k\mid (x+1)(x-1) \Rightarrow p^k \mid (x+1)$ or $p^k \mid (x-1)$. It is possible that $p^k$ divides neither $a$ nor $b$, but $p^k \mid ab$ (for example $9 \not \mid 3$ and $9 \not \mid 6$, but $9 \mid 18$), because if $k > 1$, then $p^k$ is not prime.

The proper argument would go like this: We have $p^k \mid (x+1)(x-1)$. Now assume that $p \mid (x+1)$ and $p \mid (x-1)$, then $p \mid 2$ which is false. So $p$ does only divide one of the factors in $(x+1)(x-1)$. This means that all $k$ copies of $p$ that appear in the decomposition of $(x+1)(x-1)$ must come from either $(x+1)$ or $(x-1)$, thus $p^k \mid (x+1)$ or $p^k \mid (x-1)$.

Assume $x^2 \equiv 1 \pmod {p^k}$. Then $x^2-1 \equiv 0 \pmod {p^k}$, meaning $p^k | x^2-1=(x-1)(x+1)$. Since $p$ is prime, we can conclude that $p^k\vert(x-1)$ or $p^k\vert(x+1)$. Yet, $p^k\vert(x-1) \Rightarrow x-1 \equiv 0 \pmod {p^k} \Rightarrow x \equiv +1 \pmod {p^k}$ and $p^k\vert(x+1) \Rightarrow x+1 \equiv 0 \pmod {p^k} \Rightarrow x \equiv -1 \pmod {p^k}$.

Thus, there are two solutions: If $x^2 \equiv 1 \pmod {p^k}$, then, $x \equiv -1 \pmod {p^k}$ and $x \equiv +1 \pmod {p^k}$.

• Thank you for the nice answer, but MatheinBoulomenos's answer came sooner so I already accepted his/hers.. – Longti Mar 16 '18 at 4:13
• That's fine as long as you got what you wanted. Thank you, though. :-) – Mathew Mahindaratne Mar 16 '18 at 4:42

Here’s an answer that you will be entirely justified in finding unsatisfactory:

For odd $p$, $(\Bbb Z/p^n\Bbb Z)^\times$ is cyclic (of order $(p-1)p^{n-1}$). It takes only a little work, but rather more writing, to show this. And in a cyclic group of even order, there are only two elements such that $x^2=1$. In this case, they are $1$ and $-1$.

(In the other case, that $p=2$, the group $\Bbb Z/2^n\Bbb Z$ has the structure $\{\pm1\}\oplus(1+4\Bbb Z)$, where the right-hand group is cyclic of order $2^{n-2}$, generated by $5$. Here, there will always be four solutions of $x^2=1$, namely $\pm1$ and $\pm(1+2^{n-1})$. )