Integer-valued polynomials

vess

Let $n$ be a positive integer. Determine all positive integers $m \in \mathbb{N}$ for which there exists an integer polynomial
$f(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 \in \mathbb{Z}[x]$
such that $a_n \neq 0$ , $\mathrm{gcd} \, (a_0,a_1,\ldots,a_n,m) = 1$ , and $f(k)$ is divisible by $m$ for all integers $k \in \mathbb{N}$ .

**Posted:** Thu May 27, 2004 4:28 am

harazi

A beautiful problem!!!!!!!!! I think m must divide n!. In this case the polinomial $f(X)=X(X-1)(X-2)...(X-n+1)$ solves the problem.

Now, suppose we have such a polynomial and take a prime p which divides m.
We have $p| a_0+a_1\cdot k+...+a_n\cdot k^n$ for any $k=\overline{1,n+1}$ . Consider this in $\mathbb{Z}_p$ as a linear system in $a_0,...,a_n$ . The determinant, which is a Vandermonde one must be 0 in $\mathbb{Z}_p$ . This means that p must divide a number of the form i-j, so p is at most n.
Now take any prime p smaller than n and suppose that its exponent in m is more than the exponent in n!. We have obviously $\frac{f(X)}{m}=b_0+b_1\cdot X+...+b_n\cdot\frac{x(x-1)...(x-n+1)}{n!}$ for certain $b_0,...,b_n$ . We easily deduce now that $b_i$ are integers, thus we can write $\frac{f(X)}{m}=\frac{c_0+...+c_n\cdot x^n}{n!}$ for certain $c_i$ integers. But since $a_i=\frac{m}{n!}\cdot c_i$ we must have $p|a_i$ and of course p|m. This is a contradiction.

**Posted:** Thu May 27, 2004 5:09 am

zhaobin

I don't understand $harazi's$ solution.can anyone explain it better?

**Posted:** Mon Feb 21, 2005 2:23 am

ZetaX

I don't think $m|n$ for sure: $m=2 , n=3, f(x)=x^3+x^2$ .

**Posted:** Sun Feb 05, 2006 6:42 am

_________________
The one and only place to get next year's IMO problems already now!

keira_khtn

He meant $m$ devides $(n!)$ . Very nice solution ! However, I dont think Vandermonde's matrix is acceptable in a TST. Therefore, how could you deduce $p$ can't exceed $n$ without resorting to it, Harazi! Shocked

**Posted:** Tue Mar 03, 2009 5:52 pm

_________________
Utada Hikaru