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

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