Polynomials with non integral results for multiples of 10

As challenge problem, my teacher challenged us to find a polynomial $f(x)$ that would return an integer for all positive integral values of $x$ except for some (possibly not all) $x$ divisible by $10$. For example, we could have some polynomial $g(x)$ in which $g(1)=1$, but $g(10)=0.1$ and $g(20)=2$. (I'm just making up numbers here.) I've been bashing my head at this, and have tried raising $x$ to the fourth power to eliminate the units digits down to $0,1,5,6$, but have had no such luck. Is this an impossible problem? If not, could I maybe see an example of a such polynomial, and why it would work?

A general answer is something like this:

(i) For every prime power $p^k$ there exists a polynomial $f(x)$ such that for every $a\in\mathbb{Z}$, $f(a)$ is an integer if and only if $p^k$ does not divide $a$. For instance, $f(x)=\frac1p \cdot \frac{(x+1)(x+2)\ldots(x+p^k-1)}{(p^k-1)!}$ is such a polynomial.

(ii) If $m$ is a positive integer with at least two distinct prime factors, and $f(x)$ is a polynomial with the property that $f(a)$ is an integer whenever $m$ does not divide $a$, then $f(a)$ is integer for all integers $a$.

To prove (ii) it is sufficient to prove that $f(0)$ is an integer. Let $p$ and $q$ be two distinct prime divisors of $m$. From Lagrange's interpolation we know that $f$ has rational coefficients; take a positive integer $M$ such that $g(x)=Mf(x)$ has integer coefficients.

Then there are some positive integers $M_1$ and $M_2$ such that $M_1M_2=M$, $M_1$ and $M_2$ are coprime, $M_1$ is coprime with $p$ and $M_2$ is coprime with $q$. None of $M_1$ and $M_2$ is divisble by $m$, so $f(M_1)$ and $f(M_2)$ are integers. Hence, $$ Mf(0) = g(0) \equiv g(M_1) = Mf(M_1) \equiv 0 \pmod{M_1} $$ and similarly $$ Mf(0) \equiv Mf(M_2) \equiv 0 \pmod{M_2}. $$ Since $M_1$ and $M_2$ are coprime, we get $Mf(0) \equiv 0 \pmod{M}$, so $f(0)$ is an integer.

See also the 2nd problem of RMM2011 at http://rmms.lbi.ro/rmm2011/_dwl/Sols2011D1.pdf

Let me characterize your problem as follows. Let $S \subset \{0, 1, \cdots, 9\}$. We want to see if there is a $f(x) \in \mathbb Q[x]$ such that $f(a) \in \mathbb Z$ if and only if $a \equiv a' \pmod{10}$ for some $a' \in S$.

My conclusion is, such $f(x)$ exists if and only if $S$ satisfies the follows: There is a $S_2 \subset \{0,1\}$ and $S_5 \subset\{0,1,2,3,4\}$ such that $a \in S \Leftrightarrow a \pmod2 \in S_2$ and $a \pmod5 \in S_5$.

For instance, $S = \{1,2,3,4,5,6,7,8,9\}$ is not admissible but $S = \{1,2,3,4,6,7,8,9\}$ is (pick $f(x) = \frac15(x^4-1)$).

For the only if part, suppose $f(x) \in \mathbb Q[x]$ and $F(x) = \alpha_f f(x) \in \mathbb Z[x]$ where $\alpha_f$ is the least positive integer such that $\alpha_f f(x)$ has integral coefficients. For $p = 2$ or $5$ and $m \in \mathbb N$, $F(a) \pmod{p^m}$ is periodic on $a$ with period dividing $p^m$ (because $F(a+p^m) \equiv F(a) \pmod{p^m}$). This means that "whether the $p$-adic valuation $v_p(f(a)) \geq 0$" is periodic on $a$ with the period being $p^{m_p}$ for some $m_p \in \mathbb N_{\geq 0}$. This enforces the only if part.

For the if part, suppose we have an admissible $S$ and the corresponding $S_2$ and $S_5$ are given. We can construct as follows:

Let $F_2(x) = \prod_{a \in S_2}(x-a)$ and $F_5(x) = \prod_{a \in S_5}(x-a)$. From the Chinese Remainder Theorem, there exists a $F(x) \in \mathbb Z[x]$ such that $F(x) \equiv F_5(x) \pmod 5$ and $F(x) \equiv F_2(x) \pmod 2$.Then $f(x) = \frac{1}{10}F(x)$ is what we desired.

Edit (generalizations): Thanks to user141614's insightful example on the $p^m$ case, we can get a more general result when 10 is replaced by $N$ with factorization $N = p_1^{v_1}p_2^{v_2}\cdots p_r^{v_r}$:

Claim: Let $S \subset \{0,1, \cdots, N-1\}$ be a collection of congruence classes modulo $N$. Then there exists a $f(x) \in \mathbb Q[x]$ such that $f(n) \in \mathbb Z \Leftrightarrow n \pmod N \in S$, if and only $S$ satisfies the following condition:

There exists $S_1 \in \{0, 1, \cdots, p_1^{v_1}-1\}, \cdots, S_r \in \{0, 1, \cdots, p_r^{v_r}-1\}$ such that $n \in S \Leftrightarrow > n\pmod{p_i^{v_i}}\in S_i$ for all $1 \leq i \leq r$.

The only if part again follows from the following fact:

For any $f(x) \in \mathbb Q[x]$, "whether the $p_i$-adic valuation $v_{p_i}(f(n)) \geq 0$" is periodic on $n$ with period $p_i^{s_i}$ for some $0 \leq s_i \leq v_i$.

For the if part, we can use the Chinese Remainder Theorem again for the construction. Suppose we have $S$ and $S_i, \cdots, S_r$ defined as above. user141614's post teaches us that $\binom{n}{p_i^{v_i}-1}$ is divisible by $p_i$ if and only if $p_i^{v_i} \ | \ n$. (This can be proved using the closed form formula of $v_p(m!)$).

For each $1 \leq i \leq r$, we can let $u(x) = \prod_{i=0}^{p_i^{v_i}-2}(x-i)$ and $F_{p_i}(x) = \sum_{a \not\in S_i}u(x-a)$. Then we know that $p_i^{1+v_{p_i}((p_i^{v_i}-1)!)} \ | \ F_{p_i}(n) \Leftrightarrow n \pmod{p_i^{v_i}} \in S_i$.

By Chinese Remainder Theorem, there is a $F(x) \in \mathbb Q[x]$ such that $F(x) \equiv F_{p_i}(x) \pmod{p_i^{1+v_{p_i}((p_i^{v_i}-1)!)}}$. Then $f(x) = \mathscr N^{-1}F(x)$ is what we desired, where

$$ \mathscr N = N \cdot \prod_{i=1}^r p_i^{v_{p_i}((p_i^{v_i}-1)!)}. $$