I was requested to solve $x^2\equiv x \pmod{12}$. I'm fairly new to modular arithmetic and wanted to see if my solution is correct. Besides, I'm pretty sure there is a simpler solution and I'm curious to learn what it might be. Also, a question came up as I was solving the problem.
Here's what I did.
Notice that $12=3 \times 4$ with $\gcd (3, 4)=1$. Then notice $x^2 \equiv x \pmod{3} \iff x \equiv 1 \pmod{3}$ and $x^2 \equiv x \iff \equiv 1 \pmod{4}$. So $x$ must simultaneously satisfy the two aforementioned congruences.
If $x \equiv 1 \pmod{3}$ then $x=1+3k$ is the general solution. Then
$$ \begin{align} x &\equiv 1 \pmod{4} \\ \iff 1+3k &\equiv 1 \pmod{4} \\ \iff 3k &\equiv 0 \pmod{4} \\ \iff k &\equiv 0 \pmod{4} \end{align} $$
which implies $k=4q, q \in \mathbb{Z}$, are solutions to the equation. Substituting $k$ in our formulation of $x$, we have $x=1+3(4q)$ or rather
$$ x=1+12q \\ $$
as a general solution.
The question I had comes from the fact that the obtaind solution is equivalent to the one that would have been obtained by noticing that, in $\pmod{12}$,
$$x^2\equiv x \iff x \equiv 1 \iff x=1+12k$$
since $\gcd({12, 1})=1$. However, a professor explicitely warned against using this "direct" method on quadratic congruences. Of course one could argue the congruence is not really quadratic, since $x \in \mathbb{Z}$ by assumption and then $x^2\equiv x\implies x\equiv1$, which is what ends up being solved.
I know this may be very basic, but as I said I'm a beginner. Thanks in advance to any clarification/verification or general answer.
Actually the easiest way to do this is $x^2 \equiv x \pmod {12} \iff$
$12\mid x^2 - x = x(x-1)$.
So as $12=3\time 2^2$ we have $3\mid x$ or $3 \mid x-1$. $2\mid x$ or $2\mid x-1$. As $x,x-1$ are relatively prime we can't have $2\mid x$ and $2\mid x-1$ so we have $4\mid x$ or $4\mid x-1$.
So there are four possibilities.
$3\mid x$ and $4\mid x$. Hence $12\mid x$ and $x\equiv 0 \pmod {12}$
$3\mid x$ and $4\mid x-1$ so $x\equiv 0,3,6,9\pmod {12}$ and $x\equiv 1,5,9 \pmod {12}$ so $x \equiv 9\pmod {12}$.
$3\mid x-1$ and $4\mid x$. so $x \equiv 1,4,7,10\pmod {12}$ and $x \equiv 0, 4, 8\pmod{12}$.
$3\mid x-1$ and $4\mid x-1$ so $12\mod x-1$ and $x-1\equiv 0 \pmod{12}$ and $x \equiv 1 \pmod {12}$.
... but if you want to do division ....
You need to explain (and understand) why and when we can and can not divide in modular arithmetic.
You assume (correctly) that for $x^2 \equiv x \pmod{12}$ that we can't just divide by $x$ to get $x\equiv 1\pmod {12}$. But then you assume (mostly correctly; if we ignore the $x\equiv 0$ solution) that we can do it for $\pmod 3$ and then assume (incorrectly) that we can do it for $\pmod 4$.
The reason why, in general we can not do division, is because if $m|ka - kb$ (i.e. $ka \equiv kb\pmod m$) it does not follow that $m|a-b$. $m$ and $dk$ may have some factors in common.
But it does mean that if $d =\gcd(k,m)$ then if $ka\equiv kb\pmod m$ then $m|ka-kb\implies \frac md = (\frac kd)a -(\frac kd)b = \frac kd(a-b)$ and as $\frac md$ and $\frac kd$ are relatively prime (why?) then $\frac md| a-b$ and $a\equiv b\pmod {\frac md}$.
So
and that is how we do division.
So we have if $x^2 \equiv x \pmod m$ (and we ignore the solution $x\equiv 0 \pmod m$ [I'll get to that later]) then we have the result $x\equiv \pmod {\frac {12}{\gcd(x,12)\}$.
And $\gcd(x,12) = 1, 2, 3, 4, 6,$ or $12$.
If $\gcd(x,12) = 1$ then $x \equiv 1 \pmod {12}$ (and so $5,7,11$ are not solutions)
If $\gcd(x,12)=2$ then $x\equiv 1 \pmod {6}$. But if $\gcd(x,12)=2$ then $x$ is even and $x\equiv 1\pmod {6}$ is odd. .... so.... not everything we write can have a solution. For instance $(2y)^2\equiv (2y)\pmod {12}$ and $y$ odd will have no solution.
If $\gcd(x,12)=3$ then $x\equiv 1\pmod{4}$ but we also have $x\equiv 0 \pmod 3$. Thus we have $x\equiv 1,5,9$ or $x \equiv 0,3,6,9$ so $x\equiv 9\pmod {12}$.
If $\gcd(x,12)=4$ then $x\equiv 1\pmod 3$ and $x\equiv 0 \pmod 4$ and by similar reasoning $x\equiv 4\pmod {12}$
If $\gcd(x,6)=6$ then $x\equiv 1\pmod 2$ and $x\equiv 0\pmod 6$ (a contradiction).
But if $\gcd(x,12)=12$ things get interesting. That means $x \equiv 1 \pmod 1$. But that just means $1|x-1$ and that is true for all integers. Everything is equivalent to $0\pmod 1$. So this gives us $x\equiv 1 \equiv 0 \pmod 1$ which can be anything. And $x\equiv 0 \pmod{12}$ so $x \equiv 0\pmod{12}$.
We've found a loop-hole to dividing by $0$. If $xk = zk \pmod {M}$ then $x \equiv z \pmod {\frac M{\gcd(k,M)}}$. If $k \equiv 0 \pmod M$ that's no problem! As $\gcd(k,M) = 12$ then this result is $x \equiv z \pmod 1$ which is $x,z$ can be any integers. Which is the case with $x\cdot 0 \equiv z\cdot 0 \pmod {M}$.