Integer-valued Polynomials

It can be shown that the polynomial $n^4 + 4n^3 + 2n^2 + 5n$ is a multiple of $6$ for every integer $n$. It can also be shown that $6$ is the largest integer satisfying this property.

Define $M(a, b, c)$ as the maximum $m$ such that $n^4 + an^3 + bn^2 + cn$ is a multiple of $m$ for all integers $n$. For example, $M(4, 2, 5) = 6$.

Also, define $S(N)$ as the sum of $M(a, b, c)$ for all $0 \lt a, b, c \leq N$.

We can verify that $S(10) = 1972$ and $S(10000) = 2024258331114$.

Let $F_k$ be the Fibonacci sequence:
$F_0 = 0$, $F_1 = 1$ and
$F_k = F_{k-1} + F_{k-2}$ for $k \geq 2$.

Find the last $9$ digits of $\sum S(F_k)$ for $2 \leq k \leq 1234567890123$.

This mathematics problem is quite complex and seems to be taken from a high-level contest or curriculum, it requires in-depth understanding of polynomial divisibility, maximum values, and sequence sums. It’s a combination of algebra, number theory and recursion.

First off, let’s start with how we can determine if the polynomial $n^4 + an^3 + bn^2 + cn$ is a multiple of $m$ for all integers $n$. If $m$ is a divisor of the polynomial for all integers, then it must also be a divisor for all of its resultants. Specifically, if the polynomial is repeatedly differentiated, $m$ must divide the 4th derivative, which is just 24.

With that, we note that $m$ can be any divisor of 24, i.e., possible values are 1, 2, 3, 4, 6, 8, 12, and 24. We begin by assuming $m$ is 24, then check if it holds for all coefficients a, b, and c. If not, we move down to 12, and so on until we reach the maximum m value that holds for all three coefficients.

For the $S(N)$ definition, notice that any $S(F_k)$ is going to have repeated sums of some value $M(a,b,c)$. In efficient terms, precalculate all $M(a,b,c)$ for $1 <= a, b, c <= F_{k_}$ max where $k_ max = 1234567890123$. Then, when summing $S(F_k)$ it'll be easy to just pull the precalculated sums. As for the Fibonacci sequence involved, it's utilized by mapping the values generated by Fib($k$) as the upper limits of the $M(a,b,c)$ function. It's one of the reasons the problem gets computationally large, as the Fibonacci sequence grows exponentially. Finally, to get the last 9 digits of the sum, it is a common method in number theory to use modulo operation. In this case, we keep summing while taking modulo $10^9$ to ensure we only keep the last 9 digits. Actually solving this problem, however, is beyond the scope of human computation and would require programming in addition to these mathematical insights. This explanation also assumes a strong background in these topics and may skip over some of the underlying principles of number theory, polynomial calculus, and sequence summation. If there is part of this problem that you would like more detail on, please don't hesitate to ask.

More Answers: