Abstract: For each prime $p\le x$, remove from the set of integers a set $I_p$ of residue classed modulo $p$, and let $S$ be the set of remaining integers. As long as $I_p$ has average 1, we are able to improve on the trivial bound of $\gg x$, and show that for some positive constant c, there are gaps in the set $S$ of size $x(\log x)^c$ as long as $x$ is large enough. As a corollary, we show that any irreducible polynomial $f$, when evaluated at the integers up to $X$, has a string of $\gg (\log X)(\log\log X)^c$ consecutive composite values, for some positive $c$ (depending only on the degree of $f$). Another corollary is that for any polynomial $f$, there is a number $G$ so that for any $k\ge G$, there are infinitely many values of $n$ for which none of the values $f(n+1),\ldots,f(n+k)$ are coprime to all the others. For $f(n)=n$, this was proved by Erdos in 1935, and currently it is known only for linear, quadratic and cubic polynomials. This is joint work with Sergei Konyagin, James Maynard, Carl Pomerance and Terence Tao.