# Does $x^2\equiv x\pmod p$ imply $x^2\equiv x\pmod {p^n}$ for all $n$?

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?

-

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

-
Thank you, Zev :) Is there some general rule as to when the relation is true? (There might not be, I'm just interested.) – modulo Feb 16 '12 at 11:31
@modulo: No problem, glad to help - I've updated my answer with some further explanation. If there's anything I should expand on, let me know. – Zev Chonoles Feb 16 '12 at 11:36
Thanks again Zev, you are most kind :) – modulo Feb 16 '12 at 11:47
Your claim that $m$ will divide $x$ or $x-1$ if $m$ divides $x(x-1)$ is not true for arbitrary integers. For example, $3^2\equiv 3\pmod{6}$, $6|3(3-1)$, but $6$ does not divide either $3$ or $2$. It is true for $m$ a prime power, but false otherwise. – Arturo Magidin Feb 16 '12 at 17:07
P.S. You may want to use \pmod instead of \bmod when writing congruences. \bmod is the "binary operator"; $a\bmod b$ is the the nonnegative remainder when dividing $a$ by $b$. – Arturo Magidin Feb 16 '12 at 17:13

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

-