2

I'm trying to solve the following question:

Show that If $x^2 \equiv x\bmod p^k$, then $x \equiv (0\:\text{or}\:1)\bmod 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\bmod p$ or $x \equiv 1\bmod 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\bmod p$:

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

Can I do this?

Gary
  • 31,845
Jake Browning
  • 63
  • 1
    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}$. – Najib Idrissi Mar 05 '14 at 15:11

2 Answers2

1

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

user2345215
  • 16,422
  • 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. – Jake Browning Mar 05 '14 at 15:16
  • Could you elaborate, actually? Why does $p^k$ have to divide one of them because $p$ must only divide one? – Jake Browning Mar 05 '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. – user2345215 Mar 05 '14 at 20:13
  • 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. – Jake Browning Mar 05 '14 at 20:37
0

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

fgp
  • 21,050