Contest math problem on divisibility and congruence

Question

Show that, if 13 divides $n^2$ + $3n$ + $51$ then 169 divides $21n^2$ + $89n$ + $44$

We have 13 $|$ $n^2$ + 3n + 51

Using some congruency rules, this becomes:

13 $|$ $n^2$ + $3n$ - $1$

Or 13 divides $n(n+3)$ + 1

At this point, I was feeling kinda lazy, so I just listed the factors of 13, added 1 to each and saw which one can be broken down into two numbers such that one is 3 less than the other instead of trying to look for a more elegant solution

I quite quickly arrived at n = 5 (5 × 5 + 3 = 40 = 39 + 1)

I plugged n = 5 into the other equation, and got something that's divisible by 169

Now, how do I do the final thing, which is to prove either that no other such value of n can be found, or if it can be found, it would satisfy the other condition as well?

Never mind, found it

Answer 1

Use $$n^2+3n+51=n^2+3n-40+91\equiv(n+8)(n-5)(mod13).$$ Also, $$21\cdot(-8)^2+89\cdot(-8)+44=4\cdot169$$ and $$21\cdot5^2+89\cdot5+44=6\cdot169.$$

For example, if $n=13k-8$, where $k$ is an integer number, so $$21n^2+89n+44=169(21k^2-19k+4).$$ Can you end it now?

Also, we can use $$21n^2+89n+44=(7n+4)(3n+11),$$ which gives a short proof.

Answer 2

Hint $\,f_n = 21n^2\!+89n\!+\!44 = \overbrace{21\color{#c00}{(n\!-\!5)^2}\! +23\cdot \color{#c00}{13(n\!-\!5)}\!+ 6\cdot\color{#c00}{13^2}}^{\textstyle\text{Taylor expand at}\,\ n=5}$
therefore we immediately conclude that $\,\color{#c00}{13\mid n\!-\!5}^{\phantom{|^{|^|}}}\!\!\Rightarrow\,13^2\mid f_n,\,$ since

$\!\!\bmod 13\!:\ 0\equiv n^2\!+3n+51 \equiv (n\!-\!5)^2\,\Rightarrow\, \color{#c00}{n\!-\!5\equiv 0}$