(3) Consider the polynomial x^2 + x = 0 over Z/nZ.

(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.

I found (but didn't proove) this :

let a" be the number of solutions of x^2+x = 0 mod a and b" be the number of solutions of x^2+x = 0 mod b. Let Then if gcd(a,b)=1 number of solutions of x^2+x = 0 mod ab is a"*b".

So far, for all values for which I tested it, it works. From that I can easily find the answer but I would like to know how to proove it.

Thanks for your help!