For any positive integer $n$, let $f(n) = 70 + n^2$ and $g(n)$ be the HCF of $f(n)$ and $f(n+1)$ find the highest possible value of $g(n)$.

Question

For any positive integer $n$, let $f(n) = 70 + n^2$ and $g(n)$ be the HCF of $f(n)$ and $f(n+1)$ find the highest possible value of $g(n)$.

This question is from HKIMO prelims 2006. I didn't quite understand what was happening when I went through the solution.

So far all I've gotten is:

$g(n) = (70+n^2, 70+(n+1)^2)$

$g(n) = (70+n^2, 2n+1)$

Not sure what to do from here -_-

Thank you!

Answer 1

$g(n)$ divides $2n+1$

Also divides $2(70+n^2)-n(2n+1)=140-n$

and consequently divides $2(140-n)+2n+1=?$

Answer 2

Using your

$$g(n) = (70+n^2, 2n+1) \tag{1}\label{eq1}$$

note $2n + 1$ is odd, so can multiply $70 + n^2$ by $4$ to $280 + 4n^2$, but with it still giving the same HCF. However, note that $2n \equiv -1 \pmod{2n + 1}$, so $4n^2 \equiv 1 \pmod{2n + 1}$. Thus,

$$280 + 4n^2 \equiv 281 \pmod{2n + 1} \tag{2}\label{eq2}$$

I trust you can finish the rest yourself now.

In general, if the $70$ is replaced by a positive integral constant $c$, then you'll get that $2n + 1 | 4c + 1$, so $g(n) | 4c + 1$, which means that $g(n) \le 4c + 1$. To show it reaches this potential maximum, note that at $n = 2c$, you get $f(2c) = c + (2c)^2 = c + 4c^2 = c(4c + 1)$ and $f(2c + 1) = c + (2c + 1)^2 = 4c^2 + 5c + 1 = (4c + 1)(c + 1)$. This shows that $g(2c) \ge 4c + 1$, so it must be $4c + 1$.