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

Printable View

• Oct 8th 2008, 02:44 AM
vincisonfire
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!
• Oct 9th 2008, 05:12 AM
Opalg
Quote:

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.
• Oct 9th 2008, 11:52 AM
vincisonfire
Reply
Your right. The fact is we are gonna see this theorem in class in a month or so. I checked it out and found an easy solution for n such that there is 2^n solutions. Thank you though.