Legendre's sieve (inclusion–exclusion count)
Statement
For and the set of primes , the count of coprime to is , where is the Möbius function; taking gives .
Why is it true?
This is the precise, quantitative version of "cross off multiples": instead of physically marking a grid, it counts survivors directly by inclusion–exclusion over which small primes divide them. It is the ancestor of every modern sieve (Brun, Selberg, the large sieve, GPY) used to attack twin primes and bounded gaps — all of them are, at bottom, smarter ways of controlling the error terms that this exact formula produces.
Proof sketch
Every integer is coprime to iff it is divisible by none of the primes . For each divisor (a squarefree product of some subset of these primes), the count of multiples of in is exactly .
By inclusion–exclusion over the events "" for : the count of divisible by at least one prime in is , alternating with the number of primes multiplied together. Each such alternating sign is exactly the Möbius function of the corresponding squarefree : , for a product of distinct primes.
So the count divisible by at least one prime in is . Subtracting this from (the term, ) gives the count coprime to : .
Finally, taking so that is exactly the primes : any coprime to all of them is either or a prime (by the theorem above, since it has no prime factor ), so , giving the stated identity.
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Alina Carmen Cojocaru, M. Ram Murty (2005). An Introduction to Sieve Methods and Their Applications
- Yitang Zhang (2014). Bounded gaps between primes · DOI:10.4007/annals.2014.179.3.7
- James Maynard (2015). Small gaps between primes · DOI:10.4007/annals.2015.181.1.7