Nice problem. I think we can use the following lemma: if P(x) is an integer polynomial of degree less than p, where p is a given prime, such that p divides P(n) for all integers n, then each coefficient of P is a multiple of p.

um johan could u pls post the proof of the lemma for novices like us....

The problem is proposed by Mahyar Sefidgaran. It is a nice result. There are more than one approach to the problem. One can use induction ...

Johan Gunardi wrote: Nice problem. I think we can use the following lemma: if $P(x)$ is an integral polynomial of degree less than $p$, where $p$ is a given prime, such that $p$ divides $P(n)$ for all integers $n$, then each coefficient of $P$ is a multiple of $p$. Look at $\hat{P}(X) \in \mathbb{Z}_p[X]$ having as coefficients the reduced modulo $p$ coefficients of $P(X)$. Then $\hat{P}(x) \equiv 0 \pmod{p}$ for all $x \in \mathbb{Z}_p$. Since the degree of $P$ is less than $p$, the same holds true for $\hat{P}$, but then $\hat{P}$ has more distinct roots than its degree, so it must be identically null. This means all coefficients of $P$ are divisible by $p$.

Suppose that $k <p$. we use induction on $k$. for $k=1$ is known as Lagrange lemma. Now suppose we have $p^{k+1}|f(x)$ for all integer $x$. Assume we have $f(x)=(x^p-x)^{k+1} m(x)+n(x)$ now since we have $p^k |n(x)$ from induction we have $ n(x)=\sum_{i=0}^{k}(x^{p}-x)^{i}p^{k-i}A_{i}(x)$ the only thing to prove is to show that for each $i$ we have $p|A_{i}(x)$. since we have $p^{k+1}|n(x)$ we have $0\equiv \frac{n(x)}{p^k}=\sum_{i=0}^{k}(\frac{x^{p}-x}{p})^{i}A_{i}(x)$ mod$(p)$ Now put $y=\frac{x^p-x}{p}$ ( we can do it since $\frac{x^p-x}{p}$ gives all residue of $p$ and therefore $y$ is independent from $x$ ) we have: $\sum_{i=0}^{k}y^{i}A_{i}(x)\equiv 0$ mod$(p)$. Therefore $p|A_{i}(x)$ from Lagrange lemma.

in fact if u know the generalization(and its proof ) which is also a well-known result of the lemma mentioned by Johan then the problem is pretty easy : if f(x) is a polynomial in Z[x] with coefficients a_n,...a_0 and we have for some natural number m | f(x) for all x in Z and also gcd(a_n,...,a_1,a_0,m)=1 then we must have m | n!.

Suppose $v_p(f(x))=1$ then certainly $f(x)$ can be written as $pa(x)+b(x)$. Now suppose $b(x)=(x^p-x)t(x)+r(x)$ , so $deg(r(x))<p$ but not all of the coefficients of $r$ are divisible by $p$. Then just by lagrange lemma that’s absurd. Now suppose true for $f_k(x)$ where $v_p(f_k(x))=k$ thus now consider $f_{k+1}(x)=pf_k(x)+g_{k+1}(x)=p\sum_{i=0}^{k} (x^p-x)^ip^{k-i}A_i(x)+g_{k+1}(x)$ where $v_p(g_{k+1}(x))=k+1$ now so it’s enough to show $(x^p-x)^{k+1}g_{k+1}(x)$. To prove lets take help of induction, base case is from above, for $k=2$ suppose $g_2(x)=(x^p-x)m(x)$ then $v_p(x^p-x)=p$ for all $x>1$ thus so $p|m(x)$ for all $x>1$ , now so we get a situation where $x^p-x$ doesn’t divide $m(x)$ while $p$ divides $m$ for all $x>1$ and not all coefficients of $m$ are divisible by $p$ either, again that is just same as what we had done for $k=1$, thus $(x^p-x)^2|g_2(x)$ , similarly going on $(x^p-x)^{k+1}|g_{k+1}(x)$ and that’s what all we need to complete induction process, so done.