find a quadratic polynomial p ( x ) and a number n such that p ( x ) and a number $n \pmod n $ has at least 2015 roots?

Question

I understand what the question is asking for, but I don't know how to prove my answer. Let's say I took an equation of the form: $x^2+ 6x+ 8 \equiv0 \pmod {15}$. The first four roots are $1,8,11,13\dots$ and this can continue infinitely. How do I prove that this quadratic polynomial has at least $2015$?

Answer 1

Hint: Show that if $n$ is the product of $k$ distinct primes, then the congruence $x^2-1\equiv 0\pmod{n}$ has $2^k$ solutions.

If you want a simpler but much less interesting approach, use the congruence $x^2\equiv 0\pmod{2^k}$ where $k$ is large.

Remark: It is not clearly stated, but I believe that you are expected to consider two solutions $x$ and $x'$ which are congruent modulo $n$ as the same solution. So in your example the only roots (up to congruence modulo $15$) are the ones you gave.