Suppose $x^2\equiv x\pmod p$ where $p$ is a prime, then is it generally true that $x^2\equiv x\pmod {p^n}$ for any natural number $n$? And are they the only solutions?
Does $x^2\equiv x\pmod p$ imply $x^2\equiv x\pmod {p^n}$ for all $n$?
3 Answers
No, it is not generally true. For example, $6^2=36\equiv 6\bmod 5$ but $6^2=36\not\equiv 6\bmod 25.$
Suppose we are given an integer $x$. Note that, for any prime power $p^n$, $x^2\equiv x\pmod {p^n}\iff p^n\mid x(x-1)\iff p^n\mid x\;\; \text{ or }\;\;p^n\mid (x-1)$ because $x$ and $x-1$ are relatively prime. Therefore, $x^2\equiv x\pmod {p^n}$ is true if and only if $n\leq\max\{v_p(x),v_p(x-1)\}$ where $v_p(d)$ denotes the number of times $p$ goes into $d$.
-
0Can you please explian the equality after the word "Therefore" ? – 2012-08-07
The English word “any” is slippery, but I think that the question asks whether if $x\equiv x^2 \pmod{p}$, then $x\equiv x^2 \pmod{p^n}$ is true for all $n$. One possible way to look at a congruence that’s true modulo all powers of a prime $p$ is that it’s really a statement about equality in the field ${\mathbb Q}_p$ of $p$-adic numbers. In particular, if $x\equiv x^2$ modulo all powers of $p$, then $x=x^2$ in ${\mathbb Q}_p$. But since the $p$-adic numbers are a field, high-school algebra tells you that either $x=0$ or $x=1$.
Way 1: Let us compute a bit. Let $p=2$. Note that $x^2\equiv x \pmod 2$ for any $x$. Is it true that always $x^2\equiv x\pmod 4$? No, let $x=2$.
Way 2: We do more work, but will get a lot more information. Rewrite the congruence $x^2\equiv x \pmod p$ as $x^2-x\equiv 0 \pmod p$, and then as $x(x-1)\equiv 0\pmod p$.
This says that the product of $x$ and $x-1$ is divisible by $p$. A product $ab$ is divisible by the prime $p$ if and only if $p$ divides $a$ or $p$ divides $b$, or both.
So $x(x-1)$ is divisible by $p$ if and only if $x$ is divisible by $p$ or $x-1$ is divisible by $p$, that is, if and only if $x\equiv 0 \pmod p$ or $x\equiv 1 \pmod p$.
Now does this force $x(x-1) \equiv 0 \pmod {p^2}$? No, for example we could take $x=p$. Certainly it is not true that $p(p-1)$ is divisible by $p^2$. We could also take $x=2p$, or $x=3p$, and so on up to $x=(p-1)p$. Or we could put the badness in the $x-1$ part, by putting $x=1+p$, or $x=1+2p$, and so on up to $x=1+(p-1)p$. We get a total of $2(p-1)$ numbers $x$ between $0$ and $p^2-1$ such that $x^2\equiv x \pmod p$ but $x^2\not\equiv x \pmod{p^2}$.
We can similarly identify the numbers $x$ between $0$ and $p^n-1$ such that $x(x-1)\equiv 0 \pmod p$ but $x(x-1)\not \equiv 0 \pmod{p^n}$. Again, they are of two types: (i) the numbers $p$, $2p$, and so on up to $p(p^{n-1}-1)$ and (ii) the numbers obtained by adding $1$ to numbers in list (i).