Let denote the set of the non-negative integers. For a subset , we can define the ‘counting function’
i.e. is the number of elements in that are at most . Then we can define the (asymptotic) density of as
when this limit exists.
For example, the set of the even (resp. odd) numbers has density . More generally, any arithmetic progression has density . Another example is the set of prime numbers, which has density by the prime number theorem. From this it also follows that the set of composite numbers has density .
Theorem. If a finite union of arithmetic progressions of positive integers has density , then it contains all sufficiently large positive integers.
be a finite union of arithmetic progressions such that . Note that (this is the main trick) we can write:
for some , where is the least common multiple of .
Why can we do this? Consider for example . We can write this as
And this idea works for any finite union of arithmetic progressions.
It is then clear that has to be a complete set of residues modulo , because otherwise would have density strictly less than . Therefore has to contain all positive integers .
We get the following nice corollary:
Corollary. The set of all composite numbers cannot be expressed as a finite union of arithmetic progressions of positive integers.
Proof. Otherwise by the above theorem all sufficiently large positive integers would be composite, contradicting the fact that there are infinitely many primes.