Polynomials Whose Value Is Always an Integer

结果恒为整数的多项式 苏剑林 · 2014-12-04 · Mathematics number theory difference

While doing elementary number theory last night, I ran into this problem:

Prove that
$$\frac{1}{3}x^3+\frac{1}{5}x^5+\frac{7}{15}x$$
is always an integer, where $x$ is an integer.

More generally, one can show that

$$\sum_{p\in\mathbb{P}}\frac{1}{p}x^p + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)x$$

is always an integer, where $\mathbb{P}$ is a finite set of primes — and there are many more problems of this "always-an-integer" flavor. To prove that such expressions always take integer values, one approach is congruence analysis, showing that the numerator is always divisible by the denominator. But a neater, and usually simpler, method is to give the result a meaning that forces it to be an integer — whether that meaning is computational or operational. more

For example, to show that ${n\choose k}=\frac{n !}{(n-k)! k!}$ is always an integer (suppose for now we only know the expression on the right-hand side, without knowing what it means), it suffices to show that it equals the number of ways to choose $k$ things out of $n$, since a binomial coefficient is necessarily an integer. This is giving the expression an operational meaning. Another example is showing that $\frac{n(n+1)}{2}$ is always an integer: one can simply note that one of $n,n+1$ must be even, hence the expression is always an integer; or one can show that $\frac{n(n+1)}{2}=1+2+\dots+n$, where the right-hand side is the sum of the first $n$ terms of a sequence of integers, so the sum is automatically an integer. In other words, one way to prove that a polynomial's value is always an integer is to express it as the sum of the first $n$ terms of some integer sequence.

The question now is: how do we find such an integer sequence? Simply take differences! For instance, $f(x)=\frac{1}{3}x^3+\frac{1}{5}x^5+\frac{7}{15}x$, $f(0)=0$, and

$$f(x)-f(x-1)=x^4-2 x^3+3 x^2-2 x+1$$

The right-hand side of this equation is a polynomial with integer coefficients, so its value is automatically an integer. And since

$$f(x)=\sum_{t=1}^{x}\left(t^4-2 t^3+3 t^2-2 t+1\right)$$

it follows that $f(x)$ is always an integer. Admittedly, this particular problem isn't too bad to handle via congruence analysis either — but for the problem below, congruence analysis would get quite messy.

Let

$$f(x)=\sum_{p\in\mathbb{P}}\frac{1}{p}x^p + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)x$$

It suffices to note that

$$\begin{aligned}f(x)-f(x-1)=&\sum_{p\in\mathbb{P}}\frac{1}{p}x^p + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)x\\ &-\sum_{p\in\mathbb{P}}\frac{1}{p}(x-1)^p - \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)(x-1)\\ =&\sum_{p\in\mathbb{P}}\frac{1}{p}\left[ x^p -(x-1)^p \right] + \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)\\ =&\sum_{p\in\mathbb{P}}\frac{1}{p}\left[\sum_{k=1}^{p-1} {p\choose k} (-1)^{p-k+1} x^k \right] +\sum_{p\in\mathbb{P}}\frac{1}{p}+ \left(1-\sum_{p\in\mathbb{P}}\frac{1}{p}\right)\\ =&\sum_{p\in\mathbb{P}}\left[\sum_{k=1}^{p-1} \frac{1}{p}{p\choose k} (-1)^{p-k+1} x^k \right] +1 \end{aligned}$$

Note that $p$ is prime, so $p\left|{p\choose k}\right.$, and hence the final expression is a polynomial with integer coefficients. Therefore $f(n)$ is the sum of the first $n$ terms of an integer sequence, which means $f(x)$ is always an integer.