Thread: Number of solutions for x^2+x=0 mod n

1. Number of solutions for x^2+x=0 mod n

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

2. Originally Posted by vincisonfire
(3)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".
I think that is just the chinese remainder theorem, isn't it? If gcd(a,b)=1 then for each solution of x^2+x = 0 mod a and each solution of x^2+x = 0 mod b there is a solution of x^2+x = 0 mod ab, and all solutions arise in that way.