Since exists. Let .
Complete the square:
(again and exist since ).
So a solution exists (i.e. divides this polynomial for some ) , where is the Legendre symbol.
Pretty messy huh?
Not only the above tells you what primes divide the quadratic in n but it also tells you how to find the n's!
For example, take it must be that is a square modulo 13, but:
we've a solution for each n s.t. , and choosing n=3 we indeed get
And with and etc.