2

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!

ExtraSpecial
  • 77

2 Answers2

3

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

John Omielan
  • 47,976
  • I was just wondering $f(n)=70+n^2$ is nothing special here. The same argument is valid for any number $f(n)=n^2$. – Yadati Kiran Mar 09 '19 at 05:57
  • @YadatiKiran Yes, basically the same argument would be valid for other numbers, but you would of course get different results. In this case, however, an important aspect to consider is that the resulting number, i.e., $281$, is a prime number. – John Omielan Mar 09 '19 at 06:00
  • @YadatiKiran Actually, I've realized that the resulting number being prime is actually not particularly important, so please disregard that part of my comment. – John Omielan Mar 09 '19 at 06:19
  • Infact you will always arrive at gcd to be $1$. So there is nothing special about it at all. Could have just calculated $\gcd(n^2,(n+1)^2)$. – Yadati Kiran Mar 09 '19 at 06:31
  • @YadatiKiran No, you won't always arrive at a gcd of $1$. For example, if $n = 140$, then both $70 + 140^2$ and $70 + 141^2$ are divisible by $281$. Also, note that $\gcd\left(n^2, \left(n+1\right)^2\right) = 1$ for all $n$ because $n$ and $n+1$ have no common factors. Also, you can't always say that $\gcd\left(n^2, \left(n+1\right)^2\right) = \gcd\left(70 + n^2, 70 + \left(n+1\right)^2\right)$. For example, with $n = 140$, the first gcd is $1$ while the second one is $281$. – John Omielan Mar 09 '19 at 07:13
  • My bad! You are right. I didn't see that. – Yadati Kiran Mar 09 '19 at 07:35
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=?$

lab bhattacharjee
  • 274,582