It is well-known that a polynomial $q \in \mathbb Z[t]$ vanishes modulo $p$ only if it lies in the ideal $J_p$ generated by $p$ and $t^p-t$. This means that either the degree is large (at least $p$) or the coefficients are large (divisible by $p$).
Is there anything useful like this that one can say if a polynomial vanishes modulo $n$? For example, let $n=p_1 \cdots p_k$, where $p_1<\dots<p_k$ are different primes. (For me, this could be the list of all primes less than some number $x$ for example.) It is clear that if $q(t)$ vanishes modulo $n$, then $$q(t) \in J_{p_1} \cap \cdots \cap J_{p_k} = J_{p_1} \cdots J_{p_k}.$$ Examples are $q(t)=t\prod_{i=1}^k (t^{p_i-1}-1)$ or $q(t)=p_1 \cdots p_l$ or anything in the ideal generated by polynomials divisible for each $1 \leq i \leq k$ by either $p_i$ or $t^{p_i}-t$.
Question: Is it true that again either the degree must necessarily be large or some coefficient (or let's say that sum of absolute values of coefficients) must be large? Here, large could mean for example comparable with $\sum_{i} p_i$ or $n$.
It is easy to see that any polynomial $q(t) \in \mathbb Z[t]$ that vanishes modulo $n$ is such that $q(t)/n$ maps $\mathbb Z$ to $\mathbb Z$, and hence $$q(t) = \sum_{i} n a_i \binom{t}{i},$$ for some $a_i \in \mathbb Z$ - but I do not see how this helps. I also tried to apply Chebotarev density theorem (which together with the error analysis of Lagarias-Odlyzko gives a way to produce small primes modulo which a polynomial has to have a root), but the estimates are too coarse and do not seem to make efficient use of the assumptions on the polynomial.
EDIT: Motivated by a discussion with David Speyer below, let me formulate a more precise question:
Question: Let $f \in \mathbb Z[t]$ be a monic polynomial of degree $d$ that vanishes modulo all primes $\leq P$. Is it true that $d \log \|f\|_{\infty}$ cannot be much smaller than $P^2$?
Here, $\|f\|_{\infty}$ denotes the maximum of the absolute value of the coefficients of $f$.