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)$?

  • 5
    $\begingroup$ 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$. $\endgroup$ – Théophile May 18 '18 at 4:00
  • $\begingroup$ Google for Euclid's lemma. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Peter May 18 '18 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.