Hidden Fibonacci Numbers

Note that $f(x) - x^2 - 4$ vanishes at $1,2,3$ . Thus $f(x) \; = \; x^2 + 4 + g(x)(x-1)(x-2)(x-3)$ for some $g(x) \in \mathbb{Z}[x]$ . Thus $f(21) = 445 + 6840g(21)$ , and so $f(21) \equiv 445 \pmod{6840}$ . Thus the smallest possible positive value of $f(21)$ is $\boxed{445}$ , achieved by choosing $g(x) = 0$ .

Let $y = f(21).$ We know that $y$ must be an integer because $f$ has integer coefficients. Since $f$ has integer coefficients, $a - b|f(a) - f(b)$ for all integers $a, b.$ Letting $a = 21$ and $b = 1, 2, 3,$ we have

$\begin{aligned} 20|&y - 5 \\ 19|&y - 8 \\ 18|&y - 13. \end{aligned}$

Putting this into modular arithmetic yields this system of congruences:

$\begin{aligned} y &\equiv 5 \! \! \! \! \pmod{20} \\ y &\equiv 8 \! \! \! \! \pmod{19} \\ y &\equiv 13 \! \! \! \! \pmod{18}. \end{aligned}$

From these congruences, we see that we can write $y$ in the forms $20l + 5, 19m + 8,$ and $18n + 13,$ where $l, m, n$ are all non-negative integers. Equating the first two forms and taking modulo 19 yields

$\begin{aligned} 20l + 5 &= 19m + 8 \\ 20l &= 19m + 3 \\ l &\equiv 3 \! \! \! \! \pmod{19}. \end{aligned}$

Thus, we can write $l$ in the form $19l' + 3,$ where $l'$ is some non-negative integer. Substituting this back into our original expression yields $y = 20(19l' + 3) + 5 = 20(19)l' + 65.$

Now, we equate this form with $18n + 13$ and take the entire thing modulo 18:

$\begin{aligned} 20(19)l' + 65 &= 18n + 13 \\ 20(19)l' &= 18n - 52 \\ 2(1)l' &\equiv -52 \! \! \! \! \pmod{18} \\ 2l' &\equiv 2 \! \! \! \! \pmod{18} \\ l' &\equiv 1 \! \! \! \! \pmod{9}. \end{aligned}$

Thus, we can write $l'$ in the form $9k + 1,$ where $k$ is some non-negative integer. Substituting this in to our expression yields $y = 20(19)(9k + 1) + 65 = 3420k + 445.$ Therefore, the smallest possible value of $y$ is $\boxed{445}$ .

To complete the proof, we must show that there exists such an $f$ that satisfies all these conditions. Indeed, the function $f(x) = x^2 + 4$ satisfies the conditions, and we are done.

[This is not a complete solution. I just want to point out that there is a much shorter approach, which applies to the generalized problem.]

Hint: The only polynomials with integer coefficients that satisfy $f(1) = 0$ are of the form $f(x) = g(x) \times (x-1)$ , where $g(x)$ is a polynomial with integer coefficients.

Hint: The only polynomials with integer coefficients that satisfy $f(1) = 0, f(2) = 0 , f(3) = 0$ are of the form $f(x) = g(x) \times (x-1)(x-2)(x-3)$ , where $g(x)$ is a polynomial with integer coefficients.

Hint: Hence classify all polynomials that satisfy the conditions of the problem.

Hint: Hence, determine the minimum possible positive value of $f(n)$ .

The polynomial of least degree that passes through 3 points not on the same line is a quadratic. Therefore fitting these points onto a quadratic and then evaluating at 21 should give the minimum value at x = 21.

$f(x) = ax^2 + bx + c$

$5 = a(1)^2 + b(1) + c$

$8 = a(2)^2 + b(2) + c$

$13 = a(3)^2 * b(3) + c$

This is a system of three variables, and can be represented with the following augmented matrix A:

$A = \begin{bmatrix} 1 & 1 & 1 & 5 \\ 4 & 2 & 1 & 8 \\ 9 & 3 & 1 & 13 \end{bmatrix}$

This matrix, when in reduced row echelon form produces the following values for a, b, and c:

$rref(A) = \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 4 \end{bmatrix}$

$a = 1, b = 0, c = 4$

Therefore the quadratic is:

$f(x) = x^2 + 4$

Evaluating at $x = 21$ , $f(21) = 445$ .

We can use Lagrange interpolation on the points $(1,5)$ , $(2,8)$ and $(3,13)$ and find the polynomial of the least degree that passes through these points. Interpolating these $3$ points gives: $(5 \cdot \frac{x-2}{1-2} \cdot \frac{x-3}{1-3}) + (8 \cdot \frac{x-1}{2-1} \cdot \frac{x-3}{2-3}) + (13 \cdot \frac{x-1}{3-1} \cdot \frac{x-2}{3-2})$ $\Rightarrow (5 \cdot (x-2)(-1) \cdot (x-3)(-0.5)) + (8 \cdot (x-1)(1) \cdot (x-3)(-1)) + (13 \cdot {x-1}(0.5) \cdot (x-2)(1))$ $\Rightarrow (-5x+10)(-0.5x+1.5) + (8x-8)(-x+3) + (6.5x-6.5)(x-2)$ $\Rightarrow 2.5x^2 - 7.5x - 5x + 15 + -8x^2 + 24x + 8x - 24 + 6.5x^2 - 13x - 6.5x + 13$ $\Rightarrow (2.5 - 8 + 6.5)x^2 + (-7.5 - 5 + 24 + 8 - 13 - 6.5)x + (15 - 24 + 13)$ $\Rightarrow (1)x^2 - (0)x + (4)$ $\Rightarrow x^2 + 4$

Since this polynomial is of the lowest degree possible, the function grows slower than other positive-valued higher degree polynomials, so for a value like $f(21)$ it is likely that the value will be minimised.

In this case only, our guess was correct: $f(21)$ is $21^2 + 4$ or $445$ , and checking that it satisfies the conditions, $(1)x^2 - (0)x + (4)$ has integer coefficients, and $f(1) = 1^2 + 4 = 5; f(2) = 2^2+4 = 8; f(3) = 3^2 + 14$ .

(or you could just observe that $5-4 = 1; 8-4 = 4; 13 -4 = 9$ and guess if $x^2 + 4$ is the polynomial that has the minimum value of $f(21)$ . Since the polynomial is of degree 2, you have a pretty good chance of just guessing the answer within $3$ tries)

I just used a generic 2nd order polynomial eq and implemented the initial conditions to solve: ax^2+bx+c = f(x)

Meaning: a+b+c = 5, 4a+2b+c = 8, 9a+3b+c = 13.

Solving this system of eqs gives a = 1, b = 0, c = 4, so f(x) = x^2+4. Plug 21 in and you get 445.

I don't know though why a 2nd order polynomial was best for this though... could you not fit something higher order that has downward inflection before 21?

I have directly solved by seeing a general pattern of n^2+2n+5 that is formed in the numbers 5, 8 and13.