I'm trying to solve the following question:

Show that If $x^2 \equiv x\:mod\:p^k$, then $x \equiv (0\:or\:1)\:mod\:p^k$ where $p$ is prime and $k$ is a positive integer.

I've managed to get as far as to show that since $p^k|x(x-1)$ then $p|x(x-1)$ and so either $p|x$ or $p|(x-1)$ since $p$ is prime.

This means that there are two cases: either $x \equiv 0\:mod\:p$ or $x \equiv 1\:mod\:p$. However I'm not sure how to show that since it's true for $p$, then it is true for $p^k$.

I had one idea, which is to use the theorem mentioned in the title in reverse, but I'm not sure whether the theorem works both ways. For example in the case that $x \equiv 0\:mod\:p$:

$x = pm$ for some integer $m$, so $x^k = p^km^k$. This means that $x^k = 0\:mod\:p^k$ and if the theorem works in reverse, I could finalise the proof of the first case by saying therefore that $x = 0\:mod\:p^k$.

Can I do this?

  • 1
    $\begingroup$ The "theorem in reverse" you mention in the title is wrong. $(-1)^2 \equiv 1^2 \pmod{3}$ but $-1 \not\equiv 1 \pmod{3}$. $\endgroup$ Mar 5 '14 at 15:11

$\gcd(x,x-1) = 1$, so $p^k|x(x-1)\Longrightarrow p^k|x\lor p^k|x-1$, because $p$ can't divide both $x$ and $x-1$.

  • $\begingroup$ I guess I was over-complicating things! I considered this method, but was skeptical of it because in the question before I used a proof that's almost identical to this. $\endgroup$ Mar 5 '14 at 15:16
  • $\begingroup$ Could you elaborate, actually? Why does $p^k$ have to divide one of them because $p$ must only divide one? $\endgroup$ Mar 5 '14 at 19:52
  • $\begingroup$ @Jake Browning: Sure. Suppose $p\nmid x$, then $\gcd(p^k,x)=1$ and by Euklid's lemma $p^k|x(x-1)$ implies $p^k|x-1$. Similarly for the other case. $\endgroup$ Mar 5 '14 at 20:13
  • $\begingroup$ Thanks for the clarification. I confused myself over part of your original comment and asked another question before realising that you'd answered it here. $\endgroup$ Mar 5 '14 at 20:37

The theorem doesn't work in reverse. For example, $ 3^2 \equiv 0^2 \mod 9$, yet $3 \not\equiv 0 \mod 9$. Or, more generally, $(-1)^{2k} \equiv 1^{2k} \mod p$, yet for $p > 2$ you have $-1 \not\equiv 1 \mod p$.


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.