# Finding the solutions $x \in \mathbb{Z}$ such that $x^2 \, \equiv x\ \, (\operatorname{mod} \, p)$

Let $p$ be a prime number and let $x \in \mathbb{Z}$.

I want to show that the only solutions of the congruence $x^2 \equiv x \, (\operatorname{mod} p)$ are those integers $x$ such that $x \equiv 0 \text{ or } 1 \, (\operatorname{mod} \, p)$.

My main concern isn't writing up the proof, but where to begin.

For instance, my proof begins with $x^2 \, \equiv \, x \, (\operatorname{mod} \, p)$, and then deduced that $x \, \equiv \, 0 \, (\operatorname{mod} p)$ and $x \equiv 1 \, (\operatorname{mod} \, p)$ are the only possible cases.

However, I have second thoughts: Would I have to begin with $x \equiv 0 \, (\operatorname{mod} \, p)$ or $x \equiv 1 \, (\operatorname{mod} \, p)$, and then show that in either case $x^2 \, \equiv \, x \, (\operatorname{mod} \, p)$?

• Beginning with $x\equiv 0$ or $1$ doesn't show anything except that these two choices fit the equation (which is already immediately apparent). You wouldn't be able to deduce that there are no other solutions. Use your first idea, i.e., start with $x^2\equiv x$. – Théophile May 18 '18 at 4:00
• Google for Euclid's lemma. – rtybase May 18 '18 at 8:18

By definition, $x^2\equiv x \ \ (\operatorname{mod} p)$ means that $$p\mid x^2-x=x(x-1).$$ Then using Euclid’s Lemma, since $p$ is prime, we have $p\mid x$ or $p\mid x-1$ and thus, $$x\equiv 0 \ \ (\operatorname{mod} p) \quad \text{or} \quad x\equiv 1 \ \ (\operatorname{mod} p),$$ as desired.
• You can also use the fact that in the field $\mathbb Z_p$, a polynomial with degree $d$ has at most $d$ roots, which would also prove the claim. – Peter May 18 '18 at 6:52