Sieving by large integers and covering systems of congruences

An old question of Erdos asks if there exists, for each number $N$, a finite set $S$ of integers greater than $N$ and residue classes $r(n)~({\rm mod}~n)$ for $n\in S$ whose union is $\mathbb{Z}$. We prove that if $\sum_{n\in S}1/n$ is bounded for such a covering of the integers, then the least member of $S$ is also bounded, thus confirming a conjecture of Erdos and Selfridge. We also prove a conjecture of Erdos and Graham, that, for each fixed number $K>1$, the complement in $\mathbb{Z}$ of any union of residue classes $r(n)~({\rm mod}~n)$, for distinct $n\in(N,KN]$, has density at least $d_K$ for $N$ sufficiently large. Here $d_K$ is a positive number depending only on $K$. Either of these new results implies another conjecture of Erdos and Graham, that if $S$ is a finite set of moduli greater than $N$, with a choice for residue classes $r(n)~({\rm mod}~n)$ for $n\in S$ which covers $\mathbb{Z}$, then the largest member of $S$ cannot be $O(N)$. We further obtain stronger forms of these results and establish other information, including an improvement of a related theorem of Haight.