Number of Integers using Inclusion-Exclusion Let $n \in \mathbb{N}$ and let $p_1 , p_2 , ... , p_k$ be distinct primes.
How can I show in general that the amount of integers that are not divisible by any $p_i$ is
$$n - \sum_{1 \leq i \leq k} \lfloor \frac{n}{p_i} \rfloor + \sum_{1 \leq i, j \leq k} \lfloor \frac{n}{p_{i}p_{j}} \rfloor - ... + (-1)^{k} \lfloor \frac{n}{p_{1}p_{2}...p_{k}} \rfloor $$
For example, from 1 to 100, there are $100 - (50+33+20) + (16+10+6) - 3 = 26$ integers that are not divisible by 2, 3 or 5.
Can anyone check my progress please?
This is my current progress.
Let $A_{i}$ be the set of integers from 1 to n that are divisible by $p_{i}$.
Then by PIE,
The amount of integers indivisible by any p is
$n - \sum |A_i| + \sum |A_{i} \cap A_{j}| - ... + (-1)^k |A_{1} \cap A_{2} \cap ... \cap A_{k}|$
Then I'm lost here.
 A: You are very close, since you the PIE expression you have looks almost exactly like the alternating sum of fractions you want. To complete the proof, you only need to explain why it is true that$$|A_{i(1)}\cap \dots \cap A_{i(k)}|=\left\lfloor\frac{n}{p_{i(1)}\cdots p_{i(k)}}\right\rfloor,$$
for any $\{i(1),\dots,i(k)\}\subseteq \{1\dots,k\}$. There are two pieces two this puzzle:

*

*Argue why $A_{i(1)}\cap \dots \cap A_{i(k)}$, the set of integers divisible by each of $p_{i(1)},\dots,p_{i(k)}$, is also equal to the set of integers divisible by the product $p_{i(1)}\times \dots \times p_{i(k)}$. This is a number theory principle, which is easiest seen by considering prime factorizations. If $p$ and $q$ are primes which are both factors of some integer $s$, then the product $pq$ is also a factor of $s$.


*Argue why, for any $m$, the number of integers in $\{1,\dots,n\}$ which are multiples of $m$ is $\lfloor n/m\rfloor$. This is is not too hard to see if you look at some examples. Basically, the multiples of $m$ in the range $\{1,\dots,n\}$ are of the form $m\cdot r$, where $r$ must satisfy $m\cdot r\le n$, or $r\le n/m$. Since $r$ is a positive integer less than or equal to $n/m$, the number for choices for $r$ is the largest integer less than or equal to $n/m$, which by definition is $\lfloor n/m\rfloor$.
