Find an n such that the equation $x^2+x=0$ in mod n has 4 solutions So this is my question and I also have to do it so it has 8 solutions, my problem is that I don't really understand how to approach the problem at all.  Any type of help would be appreciated thanks
 A: Hint: try to show that if $n$ is a product of $r$ distinct primes, then $x^2+x=0$ has $2^r$ solutions mod $n$.
A: Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_2}
$
let $j$ be a solution, then $n$ divides $j(j+1)$, since these numbers are relatively prime, we must send all of the factors of $p$ in $n$ to either one of these numbers. So basically for each prime $p$ in $n$ we need to "select" whether $j$ or $j+1$ is going to be divisible by $p$
So each "selection" is going to give us a system of modular equations by the chinese remainder theorem.
$x\equiv s_1 \bmod p_1^{\alpha_1}$
$x\equiv s_2 \bmod p_2^{\alpha_2}$
$x\equiv s_k\bmod  p_k^{\alpha_k}$
Where $s_i$ is either $0$ or $-1$ (0 if that prime goes to $j$ and $-1$ if it goes to $j+1$). By the chinese remainder theorem each of these systems of modular equations has exactly one solution mod $n$
since there are $k$ primes and each prime must be sent to either $j$ or $j+1$ there are $2^k$ assignations and each one gives a unique solution.
Since we want $4$ solutions the answer is those numbers which have exactly two distinct prime numbers in their canonical factorization.
