How does one prove that $n^2 +5n + 16$ is not divisible by $169$ for any integer $n$? 
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?
 A: 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}$.


A: Suppose it is, then also $$13\mid n^2+5n+16$$ so $$13\mid (n^2+5n+16)-13n=n^2-8n+16$$
so $$ 13\mid n-4\implies 169\mid (n-4)^2 = n^2-8n+16$$
So $$169 \mid  (n^2+5n+16)-(n^2-8n+16)= 13n\implies 13\mid n$$  But then from 1.st relation we get $$13\mid 16$$ a contradiction!
A: Let's try to complete the square.  Equivalences below are $\bmod 169$.
$x^2+5x+16\equiv 0$
$4x^2+20x+64\equiv 0$
$4x^2+20x+25=(2x+5)^2\equiv 25-64=-39$
We need to find a quantity whose square is $\equiv -39$.  Unfortunately this is a multiple of $13$  and the only square multiples of $13$ are also multiples of $169$ --therefore $\equiv 0\not\equiv -39$.  And we're having a bad day.
A: Let $n\in \Bbb Z$ be so that $n^2+5n+16$ is divisible by $13$. Then working modulo $13$ we have
$$
\begin{aligned}
n^2+5n+16
&\equiv n^2 + 18n + 81 \\
&= (n+9)^2 \qquad\text{ modulo }13\ .
\end{aligned}
$$
So $n$ is of the form $n=4+13k$, we substitute and get (computation in $\Bbb Z$):
$$
\begin{aligned}
n^2+5n+16
&= (13k +4)^2 + 5(13k+4) + 16 \\
&= 169k^2+169k+52\ .
\end{aligned}
$$
This is $52$ modulo $13^2$.
A: It's just as easy to prove a more general result (which is much more useful). The OP is special case
$\ \ a,b\,=\,n\!-\!4,\,n\ $ below $\,\Rightarrow \ p^2\mid n^2+(p\!-\!8)\,n+16\iff p = 2\mid n,\ $ so $\ p\neq 13\ \color{#c00}\checkmark $
Lemma $ $ If $\,p\,$ is $\rm\color{#c00}{prime}$ then $\,p^2\mid a^2\!+pb\iff p\mid a,b\,\smash[]{\overset{\  \rm\color{#0a0}U}\iff}\, p\mid (a,b) $
Proof $\,\ \ (\Leftarrow)\,\ $ Clear. $\,\ \ (\Rightarrow)\  $ $\ p^2\mid a^2\! + pb\,\Rightarrow\, p\mid a^2\color{#c00}{\Rightarrow}\, p\mid a\,$ $\Rightarrow\,p^2\mid a^2\Rightarrow p^2\mid pb\,\Rightarrow\,p\mid b$ 
The equivalence $\rm\color{#0a0}U$ is a special case of the GCD Universal Property.
Remark $ $ The Lemma is also true for for ${\rm\color{#c00}{squarefree}}\,p\,$ since they are precisely the integers satisfying the above middle inference: $\ p\mid a^2\Rightarrow\,p\mid a,\,$ for all integers $\,a.$
