# Is the fact that if $x \equiv a\:mod\:b$ then $x^n \equiv a^n\:mod\:b$ also true in reverse?

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?

• 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}$. 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$.
• Could you elaborate, actually? Why does $p^k$ have to divide one of them because $p$ must only divide one? Mar 5 '14 at 19:52
• @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. Mar 5 '14 at 20:13
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$.