Minimum number of Roots of a Polynomial Modulo n

Question

Consider over Z/nZ

$$ x^2+x = 0 $$

(a) Find an n such that the equation has at least 4 solutions.

(b) Find an n such that the equation has at least 8 solutions.

Could someone help me out here? I'm not sure how to approach this at all.

Answer 1

Hint: If $n$ is prime, $\mathbb Z / n \mathbb Z$ is a field and therefore $0=x^2+x = x(x+1)$ has only two solutions. So you are looking for an $n$ that is not prime.

We know that $n\geq 4$ so we can have at least 4 elements at all. Lets try now $n=5$ since $n=4$ obviously does not work.

If you just try the following for $x = 0,1,2,3,4,5,...$ you will get

$$x^2+x \equiv 0,2,1,2,0,(0,2,1,2,0,0,2,1,2,0,...) \mod 5.$$

So we have two solutions. Therefore $n=10$ could be a good candidate becuase $k \equiv 0 \mod 5 \iff k \equiv 0,5 \mod 5$. Lets try:

$$x^2+x \equiv 0,2,6,2,0,0,2,6,2,0,... \mod 10$$ and there we have the answer to the first question.

But as soon as you try, you will also notice that $n=6$ is an even simpler solution.