# Given a prime number a of the form 29 (mod 40) or 40k + 29. Show that the prime a cannot divide any integer of the form n^2 + 10.

Not sure how to approach this problem. First idea was proof by contradiction. Assume a divides n^2 + 10 and proceed from there. I couldn't reach a substantial conclusion from this approach.

• This would appear to be a question about Quadratic Reciprocity. – lulu Apr 21 at 14:20
• @lulu, I wonder whether there is an elementary solution that does not use QR. – lhf Apr 21 at 14:51
• @lhf Yes, I'd like to see that too – Vincent Apr 22 at 12:37

$$a\mid n^2+10$$ for some $$n$$ is equivalent to $$-10$$ being a quadratic residue modulo $$a$$. Now $$\left(\frac{-10}a\right)=\left(\frac{-1}a\right)\left(\frac{2}a\right)\left(\frac{5}a\right)$$ and if $$a\equiv29\bmod40$$ the following hold true (check e.g. Wikipedia for confirmation): $$\left(\frac{-1}a\right)=+1\qquad\left(\frac2a\right)=-1\qquad\left(\frac5a\right)=+1$$ Thus $$\left(\frac{-10}a\right)=-1$$, i.e. $$-10$$ is not a quadratic residue modulo $$a$$, and the question claim follows.