Inclusion-Exclusion and Coprime Counting

The general principle

To count a union you add the sizes of the sets, then correct for over-counting by alternately subtracting and adding the intersections. The two-set case $|A\cup B| = |A|+|B|-|A\cap B|$ (see the related card) is just the first step of a pattern that continues for any number of sets.

For three sets: $|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|.$

In general, for $n$ sets $A_1,\dots,A_n$: $\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\varnothing \ne S \subseteq \{1,\dots,n\}} (-1)^{|S|+1}\left|\bigcap_{i\in S} A_i\right|.$

The sign alternates with the size of the intersection: single sets are added, pairwise overlaps subtracted, triple overlaps added, and so on. Equivalently, the count of elements in none of the sets is $\left|\overline{A_1}\cap\cdots\cap\overline{A_n}\right| = N - \sum |A_i| + \sum |A_i\cap A_j| - \cdots,$ where $N$ is the size of the universe. This complement form is the workhorse for counting things that avoid a list of forbidden properties.

Application: counting integers coprime to $m$

To count integers in $\{1,2,\dots,N\}$ that are coprime to $m$, factor $m$ into its distinct primes $p_1,\dots,p_k$. An integer is coprime to $m$ iff it is divisible by none of these primes, so let $A_i$ be the multiples of $p_i$. The count of multiples of a product is $|A_i\cap A_j| = \lfloor N/(p_i p_j)\rfloor$, and inclusion-exclusion gives the complement directly: $\#\{k\le N : \gcd(k,m)=1\} = N - \sum_i \Big\lfloor\tfrac{N}{p_i}\Big\rfloor + \sum_{i<j} \Big\lfloor\tfrac{N}{p_i p_j}\Big\rfloor - \cdots.$

When $N=m$ itself the floors are exact and this collapses to Euler's totient: $\varphi(m) = m\prod_{p\mid m}\left(1-\tfrac{1}{p}\right).$

Mini-example

How many of $\{1,\dots,100\}$ are coprime to $45$? Since $45 = 3^2\cdot 5$, only the primes $3$ and $5$ matter (the exponent is irrelevant for coprimality). Count multiples of $3$ or $5$ and subtract from $100$: $100 - \left(\Big\lfloor\tfrac{100}{3}\Big\rfloor + \Big\lfloor\tfrac{100}{5}\Big\rfloor - \Big\lfloor\tfrac{100}{15}\Big\rfloor\right) = 100 - (33+20-6) = 100 - 47 = 53.$

The same alternating-sum idea also counts strings avoiding patterns: for $10$-digit strings over $\{1,2,3\}$ where the left $5$ avoid a $1$ or the right $5$ avoid a $2$, take $|A\cup B| = |A|+|B|-|A\cap B| = 2\cdot 2^5 3^5 - 2^{10} = 2^6(243-16) = 2^6\cdot 227$.

Exam trick: For coprimality only the distinct prime factors of $m$ matter — drop the exponents (so $3^2\cdot 5$ behaves like $3\cdot 5$). And remember the sign rule: add odd-sized intersections, subtract even-sized ones. Forgetting the final $+|A\cap B|$ correction is the classic trap that leaves the overlap double-subtracted or double-counted.