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

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 '15 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.