Say for instance that I have a set of positive even integers A = {2, 4, 6, 8, … 2000}.
How would I find the number of elements in this set that are divisible by some integer?
For instance, I understand that if, say, between 0 and 2000 there are (2000-2)/3 = 666 numbers divisible by 3, then somehow the inclusion-exclusion principle might apply to exclude odd numbers from this count, I am just not sure how.
Best Answer
Suppose we want to find how many of the even integers from $2$ to $2000$ are divisible by $m$. It is convenient to divide into two cases: (i) $m$ even and (ii) $m$ odd.
(i) If $m$ is even, say $m=2n$, we want to find the number of integers from $1$ to $1000$ that are divisible by $n$. You know how to do that.
(ii) Now let $m$ be odd. Then $m$ divides $2k$ if and only if $m$ divides $k$. So we want to find the number of integers between $1$ and $1000$ that are divisible by $m$. Again, you know how to do that.