How does one prove that $n^2 +5n + 16$ is not divisible by $169$ for any integer $n$

discrete mathematicsdivisibilityelementary-number-theorymodular arithmetic

How does one prove that $n^2 +5n + 16$ is not divisible by $169$ for any integer $n$?

THOUGHTS:

This is equivalent to say that
$$
n^2 +5n + 16=0\pmod{169}
$$
has no solutions. One can also observe that $169=13^2$. And of course one cannot expect to prove this case by case since $\mathbb{Z}$ is not a finite set.
But I really don't know how to proceed from here. Can any one help?

Best Answer

This is one of my favorite elementary number theory problems.

Hint: $$f(n)=n^2+5n+16=(n^2+5n-36)+52$$

$f(n)=(n+9)(n-4)+52$. Assume that there is some $n$ such that $13\mid f(n)$. Then $13\mid n+9$ or $13\mid n-4$. But if one of those is true, then the other is as well, since $9\equiv-4\pmod{13}$. In other words, if $13\mid f(n)$ then $169\mid n^2+5n-36$. But if this is true, then $f(n)\equiv52\pmod{169}$.

Related Question