challenge problem from class

[qaz]

show that the polynomial g(x)=(x^2 -5) (x^2-41)(x^2-205) has a solution modulo any integer n∈ℕ.

[matt grime]

you mean root; if there is a solution it should come from considering quadratic residues, i imagine.

[qaz]

ok, but i am stil stuck i dont know where to go from here...we dont have a good book for this class and it wasnt explained well at all.

[Hurkyl]

Have you done anything? (whether successful or not)

Sometimes starting small helps. What has to be true for some number m to be a root of g, mod n? What has to be true if no such m exists?

[matt grime]

Have you also noticed something important about 205?

What do you konw about Legendre's Symbol? I'm sure there are lots of useful resources out there, try Wolfram.

[qaz]

ok, i know that 205 can be written as the following: (205/n)=(5/n)(41/n), which reduces to =(-1)(-1)=1. so there are either 2 cases for this problem, (5/n)=1 or (41/n)=1.

[matt grime]

that is possibly correct in spirit, but needs better explanation: at least one of 5,41 or 41*205 must be a quadratic residue mod n for each n because...