Sieving by large integers and covering systems of congruences

An old question of Erdős asks if there exists, for each number N N , a finite set S S of integers greater than N N and residue classes r ( n ) ( mod n ) r(n)~(mod~n) for n ∈ S n∈ S whose union is Z Z . We prove that if ∑ n ∈ S 1 / n ∑ n∈ S1/n is bounded for such a covering of the integers, then the least member of S S is also bounded, thus confirming a conjecture of Erdős and Selfridge. We also prove a conjecture of Erdős and Graham, that, for each fixed number K > 1 K>1 , the complement in Z Z of any union of residue classes r ( n ) ( mod n ) r(n)~(mod~n) , for distinct n ∈ ( N , K N ] n∈ (N,KN] , has density at least d K d_K for N N sufficiently large. Here d K d_K is a positive number depending only on K K . Either of these new results implies another conjecture of Erdős and Graham, that if S S is a finite set of moduli greater than N N , with a choice for residue classes r ( n ) ( mod n ) r(n)~(mod~n) for n ∈ S n∈ S which covers Z Z , then the largest member of S S cannot be <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altt