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.

*Proof.* Let

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.