3
$\begingroup$

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?

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

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

$\endgroup$
  • 1
    $\begingroup$ I don't understand this hint $\endgroup$ – Aqua Oct 15 at 19:25
  • 1
    $\begingroup$ @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. $\endgroup$ – Matthew Daly Oct 15 at 19:27
  • 4
    $\begingroup$ $(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. $\endgroup$ – Don Thousand Oct 15 at 19:27
9
$\begingroup$

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!

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

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.

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Jack Nov 7 at 1:54
  • 1
    $\begingroup$ @Jack $\,a,b = k,n\,$ means $\,a =k,\, b = n\ \ $ $\endgroup$ – Bill Dubuque Nov 7 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.