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