Problem: Find all integer solutions of $x^2 \equiv -x \pmod{2015}$.
I proceeded this way: first, I realized that $2015 = 5 \times 13 \times 31$. I rewrote $x^2 \equiv -x$ as $x^2 + x \equiv 0$.
Then, for each factor $d$, I have that $d\ |\ x(x+1)$, therefore $d\ |\ x$ or $d\ |\ x + 1$.
This gives eight cases:
- $3,13,31\ |\ x$
- $3,13\ |\ x\quad{\rm and}\quad 31\ |\ (x + 1)$
- etc.
Solving each case separately and taking union of the results gives correct results (the conditions are both necessary and sufficient), but it's really tedious.
I am sure someone can come up with a better approach.
There's this general trick for solving quadratic congruences: if $\gcd(4a,n)=1$, then:
$$ax^2+bx+c\equiv 0\pmod{n}\stackrel{\cdot 4a}\iff (2ax+b)^2\equiv b^2-4ac\pmod{n}$$
In your case, $2015=5\cdot 13\cdot 31$ and:
$$x^2\equiv -x\pmod{2015}\iff (2x+1)^2\equiv 1\pmod{2015}$$
$$\iff \begin{cases}(2x+1)^2\equiv 1\pmod{5}\\(2x+1)^2\equiv 1\pmod{13}\\(2x+1)^2\equiv 1\pmod{31}\end{cases}$$
$$(2x+1)^2-1=((2x+1)+1)((2x+1)-1),$$ so by Euclid's Lemma:
$$\iff \begin{cases}2x+1\equiv \pm 1\pmod{5}\\2x+1\equiv \pm 1\pmod{13}\\2x+1\equiv \pm 1\pmod{31}\end{cases}$$
$$\iff \begin{cases}x\equiv \{-1,0\}\pmod{5}\\x\equiv \{-1,0\}\pmod{13}\\x\equiv \{-1,0\}\pmod{31}\end{cases}$$
By Chinese Remainder Theorem (CRT), this gives $8$ solutions mod $2015$.
E.g., if $x\equiv -1\pmod{5}$, $x\equiv -1\pmod{13}$, $x\equiv 0\pmod{31}$, then $x\equiv 1364\pmod{2015}$.
Etc. You should already know how to apply CRT. You'll get: $$x\equiv \{-1,0,155,650,805,1209,1364,1859\}\pmod{2015}$$