Fibonacci-Factors Polynomial

Let $f(x)= \sum \limits_{k=0}^{n} a_k x^k$ . From definition, we have $f(u_{n+1}) \equiv 0 \pmod{u_n}$ $\implies f(u_{n} + u_{n-1}) \equiv 0 \pmod{u_n}$ $\implies \sum \limits_{k=0}^{n} a_k(u_n + u_{n-1})^k \equiv 0 \pmod{u_n}$ $\implies \sum \limits_{k=0}^{n} a_k \left ( \sum \limits_{m=0}^{k} \binom{k}{m}(u_n)^m (u_{n-1})^{k-m} \right ) \equiv 0 \pmod{u_n}$ Where the last step follows from the binomial expansion of each of the terms. Since we are considering the expression modulo $u_n$ , we can ignore all terms which contain a positive power of $u_n$ . In general, from the expansion of $(u_n+u_{n-1})^k$ , the only term that gets selected is $\binom{k}{0} u_{n-1}= u_{n-1}$ . Continuing, $\sum \limits_{k=0}^{n} a_k (u_{n-1})^k \equiv 0 \pmod{u_n}$ Notice that this is simply $f(u_{n-1})$ , so $f(u_{n-1}) \equiv 0 \pmod{u_n}$ . Substituting $n+1$ in place of $n$ , we find out that $u_{n+1} \mid f(u_n)$ .

Now, if $n$ is even, $\gcd (n+1, n-1)= 1$ , so $\gcd (u_{n+1}, u_{n-1})= u_{\gcd (n+1, n-1)}= u_1 = 1$ If $n$ is odd, $\gcd (n+1, n-1)= 2$ , so $\gcd (u_{n+1}, u_{n-1}) = u_{\gcd (n+1, n-1)} = u_2= 1$ Either way $u_{n+1}$ and $u_{n-1}$ are always coprime. Since both of them divide $f(u_n)$ , it immediately follows that $u_{n+1}u_{n-1} \mid f(u_n)$ .

It is known that for all $n \in \mathbb{N}$ , $u_{n+1}u_{n-1}= (u_n)^2 + (-1)^n$ . The proof is trivial by induction.

We then conclude that $(u_n)^2+(-1)^n \mid f(u_n)$ . If $n$ is even, $(u_n)^2+1 \mid f(u_n)$ . If $n$ is odd, $(u_n)^2-1 \mid f(u_n)$ .

We claim that $x^2+1 \mid f(x)$ . To prove this, we note that when $f(x)$ is divided by $x^2+1$ , we shall get a polynomial $P(x)$ which is either linear or constant. If it is constant, it must be $0$ , which immediately follows by plugging $x= u_n$ for any even $n$ . If it is linear, note that $P(u_n) \equiv 0 \pmod{((u_n)^2+1)}$ for all even $n$ . However, since $P(u_n)$ is a linear and $(u_n)^2+1$ is a quadratic in $u_n$ , for some sufficiently large $n$ , $(u_n)^2+1>P(u_n)$ , a contradiction.

Similarly, we find out $x^2 - 1 \mid f(x)$ . Noting that $\gcd (x^2 + 1, x^2-1)= 1$ , we combine them into $x^4-1 \mid f(x)$ . The value of $f(x)$ which returns the smallest possible positive integer value of $x$ is given by $x^4-1$ . Our desired answer is $4^4-1= \boxed{255}$ .

A few clarifications

• We used the identity $\gcd (u_a, u_b)= u_{\gcd (a,b)} \ \forall \ (a, b) \in \mathbb{N}^2$ when we showed that $u_{n+1}$ and $u_{n-1}$ are always coprime. The proof can be found here . $$

• In order to make the proof short, I skipped the proof of the identity $u_{n+1}u_{n-1}= (u_n)^2 + (-1)^n$ . This can be proved by induction. For the case case, we note that $u_3u_1= 2 \times 1 = (u_2)^2 + (-1)^2$ , so our proposition is true for $n=2$ . Assume it is true for $n=k$ , so that $u_{k+1}u_{k-1}= (u_k)^2+(-1)^k$ . Then, note that $u_k u_{k+2} = u_k (u_k + u_{k+1})= (u_k)^2 + u_k u_{k+1} = u_{k+1}u_{k+1} + u_ku_{k+1} -(-1)^n$ $= u_{k+1}(u_k + u_{k+1}) + (-1)^{k+1} = u_{k+1}u_{k+3} + (-1)^{k+1}$ This completes our induction step, and hence our assumption is true for all $n \in \mathbb{N}$ $$

• Here's why we can choose a $n$ such that $(u_n)^2+1$ is greater than $P(x)$ for all linear polynomials $P(x)$ . Let $P(x)= mx+c$ . We can simply solve the inequality $x^2 + 1 > mx+c$ $\implies x > \frac{1}{2} \left ( \sqrt{4c+m^2-4} + m \right )$ We can simply choose any $n$ such that $u_n$ exceeds this value. In general, any higher degree polynomial with positive coefficients grows faster than any lower degree polynomial with positive coefficients.

Lemma 1: $u_{n-1}u_{n+1} = u_n^2 + (-1)^n$ for all integers $n > 1$ .

Proof: Proceed by induction. As the base case, let $n = 2$ , so that $u_{n-1}u_{n+1} = u_1u_3 = 1\cdot 2 = 2 = 1^2 + (-1)^2 = u_2^2 + (-1)^2 = u_n^2 + (-1)^n$ .

Assume for the inductive step that $u_{n-1}u_{n+1} = u_n^2 + (-1)^n$ . Then $u_nu_{n+2} = u_n(u_{n+1}+u_n)$ $= u_nu_{n+1} + u_n^2$ $= u_nu_{n+1} + u_{n-1}u_{n+1} - (-1)^n$ $= u_{n+1}(u_n + u_{n-1}) + (-1)^{n+1}$ $= u_{n+1}^2 + (-1)^{n+1}$ . $\blacksquare$

Lemma 2: $u_{n-1}$ and $u_{n+1}$ are relatively prime.

Proof: Suppose that a natural number divides $u_{n-1}$ and $u_{n+1}$ . Then it divides $u_{n+1} - u_{n-1} = u_n$ , and as a consequence of the recursion divides all Fibonacci numbers including $u_1 = 1$ . $\blacksquare$

We know that $u_n | f(u_{n+1})$ for all n, so $f(u_{n-1}) \equiv f(u_n + u_{n-1}) = f(u_{n+1}) \equiv 0 \mod u_n$ thus $u_n | f(u_{n-1})$ for all n, so $u_{n-1} | f(u_n)$ and $u_{n+1} | f(u_n)$ therefore $u_{n-1}u_{n+1} | f(u_n)$ by Lemma 2. and $u_n^2 + 1 | f(u_n)$ for even n $u_n^2 - 1 | f(u_n)$ for odd n by Lemma 1. If we divide $f(x)$ by $x^2 + 1$ , we get a remainder $r(x)$ of degree at most 1. Then $0 \equiv f(u_n) \equiv r(u_n) \mod u_n^2 + 1$ for even n, but $u_n^2 + 1$ is quadratic in $u_n$ and therefore outgrows $r(u_n)$ which is linear at most. Thus, $r(x) = 0$ and so $x^2 + 1$ divides $f(x)$ . Similarly, $x^2 - 1$ divides $f(x)$ . Hence, $4^2 + 1 = 17$ and $4^2 - 1 = 15$ divide $f(4)$ , so $255 | f(4)$ . The least positive multiple of $255$ is $\boxed{255}$ , which is achieved by letting $f(x) = x^4 - 1$ .