# Show that if $p$ is an odd prime, then the congruence $x^2\equiv1\pmod{p^{\alpha}}$ has only two solutions, $x\equiv1,x\equiv-1\pmod{p^{\alpha}}$.

Show that if $p$ is an odd prime, then the congruence $x^2 \equiv 1 \pmod{p^{\alpha}}$ has only two solutions, which are $x \equiv 1, x \equiv -1 \pmod{p^{\alpha}}$.

Clearly $x \equiv 1, x \equiv - 1 \pmod{p^{\alpha}}$ are solutions. We'll show that there are no other solutions. Suppose that $x^2 \equiv 1 \pmod{p^{\alpha}}$. Then

\begin{align} x^2-1 \equiv 0 \pmod{p^{\alpha}} &\Longleftrightarrow (x+1)(x-1) \equiv 0 \pmod{p^{\alpha}} \\ &\Longrightarrow p^{\alpha} \mid (x+1)(x-1) \\ &\Longrightarrow p \mid (x+1)(x-1) \end{align}

By Euclid's Lemma, if a prime divides a product $ab$, then it must divide either $a$ or $b$. So $p \mid (x+1)$ or $p \mid (x-1)$. Suppose $p \mid x + 1$. Since $x +1$ and $x-1$ differ by a factor of $2$ and $p > 2$ ($p$ odd), it follows that $\gcd(p^{\alpha},x-1) = 1$. Thus $p^{\alpha} \mid x + 1 \Longrightarrow x \equiv -1 \pmod{p^{\alpha}}$. Similarly, if $p \mid (x-1)$, then $\gcd(p^{\alpha},x+1) = 1 \Longrightarrow p^{\alpha} \mid (x-1) \Longrightarrow x \equiv 1 \pmod{p^{\alpha}} \text{. } \Box$

Is my proof correct? Criticism appreciated.

• Yep, this is perfectly fine. Apr 30, 2015 at 3:45
• @Tim Raczkowski Thanks for the feedback. Apr 30, 2015 at 3:47
• I would add a bit of detail. By Euclid's Lemma, $p$ divides $x-1$ or $p$ divides $x+1$. Suppose $p$ divides $x-1$. Argue that since $p$ is odd, $p$ cannot divide $x+1$. So $p^\alpha$ and $x+1$ are relatively prime. It follows that $p^\alpha$ divides $x-1$. Now do the same for the case $p$ divides $x+1$. Apr 30, 2015 at 3:52
IMHO there is something missing. Your last implication says, in effect, that if $p\mid x-1$ then $p^\alpha\mid x-1$, which is certainly not true.
The point you need to make (earlier in the proof) is this: since $x+1$ and $x-1$ differ by $2$, they cannot both be multiples of $p$ (because $p$ is greater than $2$). Therefore, the $p^\alpha$ which is a factor of $(x-1)(x+1)$ must be entirely a factor of $x-1$, or entirely a factor of $x+1$.