# 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?

• It probably helps that $169=13^2$ – G Tony Jacobs Oct 15 at 19:20
• The only root mod $13$ is $4$, so you only have to check a few values $\pmod {169}$. – lulu Oct 15 at 19:21

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}$$.

• I don't understand this hint – Aqua Oct 15 at 19:25
• @Aqua You can factor the quadratic expression. Then show that if the entire expression is divisible by 13, then it cannot be divisible by 169. – Matthew Daly Oct 15 at 19:27
• $(n+9)(n-4)+52$. So, $13\mid(n+9)(n-4)$, which means that $13|n+9$ or $13|n-4$. But if it divides either, it divides both, so $169\mid n^2+5n-36$, a contradiction. – Don Thousand Oct 15 at 19:27

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!

• Wow, that's cute. – Don Thousand Oct 15 at 19:24
• @Don Actually we can prove much more just as simply - see my answer. – Bill Dubuque Oct 16 at 1:30

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.

• Found a downvote. What is wrong here? – Oscar Lanzi Oct 18 at 8:12
• Done, thank you. – Oscar Lanzi Nov 7 at 1:51

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$$.

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.$$

• What does $a,b=n-4,n$ mean? Is that a convenient way to write $a,b\in\{n-4,n\}$ or $a=n-4, b=n$? – Jack Nov 7 at 1:54
• @Jack $\,a,b = k,n\,$ means $\,a =k,\, b = n\ \$ – Bill Dubuque Nov 7 at 2:16