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.

  • $\begingroup$ Yep, this is perfectly fine. $\endgroup$ Apr 30, 2015 at 3:45
  • $\begingroup$ @Tim Raczkowski Thanks for the feedback. $\endgroup$
    – St Vincent
    Apr 30, 2015 at 3:47
  • 2
    $\begingroup$ 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$. $\endgroup$ Apr 30, 2015 at 3:52
  • $\begingroup$ See also this question: math.stackexchange.com/questions/1241300/… $\endgroup$
    – shalop
    Apr 30, 2015 at 3:58
  • $\begingroup$ @AndréNicolas Thank you, I changed my answer according to your suggestion. $\endgroup$
    – St Vincent
    Apr 30, 2015 at 4:19

1 Answer 1


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

  • $\begingroup$ Thank you, I changed my answer according to the suggestions of you and André Nicolas. $\endgroup$
    – St Vincent
    Apr 30, 2015 at 4:20

You must log in to answer this question.

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