Problem on Principle of Inclusion-Exclusion

Question

How many integers $1, 2,....., 11000$ are invertible modulo $880$?

$880$ can be rewritten as $2^4\cdot5\cdot11$.

So I am supposed to find the number of integers in this range that have $2$, $5$ or $11$ as a divisor and then subtract that value from $11000$.

So If I divide $11000$ by each of $2$, $5$ and $11$, I get cardinalities of $5500$, $2200$, and $1000$ respectively. But how exactly am I supposed to find how many integers there are that have both $2$ and $5$ as a divisor, $2$ and $11$ as a divisor, and $5$ and $11$ as a divisor? How am I supposed to find the amount of integers that have all three numbers as a divisor?

Any help?

Answer 1

The inclusion-exclusion principle states that $$\#(A\cup B)=\#(A)+\#(B)-\#(A\cap B)$$

Generalizing this, we also find that $$\#(A\cup B \cup C)=\#(A)+\#(B)+\#(C)-\#(A\cap B) - \#(A\cap C)-\#(B\cap C)+\#(A\cap B\cap C)$$

So, if we let $A,B,C$ be the sets of all integers in $[0,11000]$ divisible by $2$, $5$, and $11$, respectively, the number of invertible elements modulo $880$ is simply the quantity $11000-\#(A\cup B \cup C)$. So, all we need to know is the value of each term in the above formula. But $\#(A\cap B)$ is the number of integers in $[0,11000]$ divisible by $2$ and $5$, i.e. divisible by $2\cdot 5=10$. Similarly, you can find out the meanings of the other terms and plug them into the formula to get your result.

Answer 2

Denote the set of integers which are divisible by $n$ in the range $\{1,2,\cdots,11000\}$ by $N(n)$. We wish to find $|N(2)\cup N(5)\cup N(11)|$. We can use inclusion exclusion.

$$|N(2)\cup N(5)\cup N(11)|=|N(2)|+|N(5)|+|N(11)|-|N(2)\cap N(5)|-|N(2)\cap N(11)|-|N(5)\cap N(11)|+|N(2)\cap N(5)\cap N(11)|$$

As stated in the comments, to find the size of the intersections, you need to find out how many integers are divisible by multiple numbers. If a number is divisible by $x$ and is divisible by $y$, and $x$ and $y$ are coprime (as they are in this example, $2$,$5$,$11$), then the number is divisible by $xy$. Use this to find the size of the set.