I have been looking at $x^2 – x \equiv 0 \pmod 6$. Factoring $x^2 – x$ yields:
$$x^2-x = x(x-1)$$
Solving $x(x-1) \equiv 0 \pmod 6$ implies $x \equiv 0$ or $x \equiv 1 \pmod 6$. However, these are not all the solutions. As it turns out, $x \equiv 3$ and $x \equiv 4 \pmod 6$ are also solutions. Plugging $3$ and $4$ it is easy to see that indeed $4 \cdot 3 \equiv 0 \pmod 6$.
However, it is not immediately obvious. My question is how to find these non-trivial solutions? Is there a good technique? What if $6$ was replaced by a relatively larger composite number? I can see solving the equations in prime factors could be one way. But I am interested to know if there are methods without needing to find prime factors.
Best Answer
Prime factorization is required for finding all solutions.
As pointed out in the comments, if we know the prime factorization of $n$, then we can find the solutions of $x^2 - x \equiv 0 \pmod n$ using the Chinese remainder theorem. For example, if $n$ is a semiprime $pq$, then the four solutions are $x \equiv 0, 1, p^{q-1}, q^{p-1} \pmod n$.
Conversely, if we know one of the nontrivial solutions $x \not\equiv 0, 1 \pmod n$, then $\gcd(x, n)$ is a nontrivial factor of $n$. So any algorithm for finding these solutions is effectively an algorithm for factoring $n$.