Polynomials vanishing modulo some integer $n$ 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$.
 A: For a monic $q(t)$ vanishing mod $n$, the degree is at least the minimal $m=m(n)$ with $n|m!$. This follows from a description of all such polynomials given by Singmaster here :
$$q(t)=r(t)S_m(t)+\sum_{k=0}^{m-1}a_k\frac{n}{gcd(k!,n)}S_k(t)$$
where $S_k(t)=(t+1)(t+2)...(t+k)$ and $r(t),a_k$ are arbitrary.
A: I thought I'd write out the bounds we can get from the pigeonhole principle. Let's say that I am working with the primes $\leq P$, with polynomials of degree $D$ and I want the largest coefficient to be at most $K$.
If $(K+1)^{D+1} > \prod_{p \leq P} p^p$, then this is possible by the pigeonhole principle: Just look at all polynomials of degree $D$ with coefficients in $[-K/2, K/2]$. Two of them must agree mod $p$ for all $p \leq P$; subtract them and win. We have $\prod_{p \leq P} p^p = \exp(P^2/2 + O(P^2/\log P))$, so this gives us roughly $K \approx \exp(P^2/(2D))$. If $D<P$, then we get a better bound by just using the pigeonhole for primes $\leq D$, and multiplying by $\prod_{D<p\leq P} p = \exp(P-D + O(P/\log P))$; the resulting bound is $K \approx \exp(D^2/(2D) + P-D) \approx \exp(P-D/2)$.
I'll point out that $\prod_{p \leq P} (t^{p-1} - 1)$ is probably worse than we would get by using pigeonhole with $D = \sum_{p \leq P} p-1 \approx P^2/(2 \log P)$. Pigeonhole gives $K \approx \exp(\log P) \approx P$. Multiplying out those binomials produces $2^{P/\log P}$ terms, of $P^2/(2 \log P)$ different different degrees, so some degree has at least $2^{P/(\log P)}/P^2$ terms contirbuting to it. There is no reason to expect better then square root cancellation, so we probably get about $\sqrt{2^{P/(\log P)}}/P$, much worse than $P$.
Editing note: I've removed some other computations which, after conversation with Andreas below, are clearly a dead end. That means the comments may not make much sense.
A: As stated the answer is negative. Denote $N=lcm \{p_i-1|1\leq i \leq k\}$. Then $t^{N+1}-t$ is always divisible by $n$. But it may appear that $\sum (p_i-1)=N+N/2+\dots+N/k$, so it may be much greater than $N$. 
But some another reasonable bound on degree/norm may hold. 
