Now, denoting the event "the number n is divisible by p" by n_{p}, consider the following sum of indicator random variables: .
The actual proof of the theorem, due to Erdős, uses sieve theory to make rigorous the above intuition.