Chapter 6, Problem 1E

To determine

The number of integers between $1$ and $10,000$ inclusive that are not divisible by $4,5,$ or $6$.

Answer to Problem 1E

The number of integers between $1$ and $10,000$ inclusive that are not divisible by $4,5,$ or $6$ is $\underset{\_}{5,334}$.

Explanation of Solution

Suppose the set $S=\{1,2,\mathrm{...},{10}^4\}$.

Let A, B, C be the set of integers $S$ that are divisible by 4, 5, 6 respectively.

Use inclusion/exclusion to calculate $\left(\overline{A}\cap \overline{B}\cap \overline{C}\right)$ which is determine the number of integers between $1$ and $10,000$ inclusive that are not divisible by $4,5,$ or $6$.

Where $B,C$ denotes the set of integers in $S$ which are divisible by $5,6$ respectively.

Then, $\left|\overline{A}\cap \overline{B}\cap \overline{C}\right|=\left|S\right|-\left(\left|A\right|+\left|B\right|+\left|C\right|\right)+\left(\left|A\cap B\right|+\left|B\cap C\right|+\left|C\cap A\right|\right)-\left(\left|A\cap B\cap C\right|\right)$.

Where $\left|A\cap B\right|$ is the number which is factor by L.C.M of $4,5=20$, $\left|B\cap C\right|$ is the number which is factor by L.C.M of $5,6=30$, $\left|C\cap A\right|$ is the number which is factor by L.C.M of $6,4=12$ and $\left|A\cap B\cap C\right|$ is the number which is factor by L.C.M of $4,5,6=60$.

Which is define in given below table;

set	size	justification
$S$	${10}^4$	${10}^4\times 1$
$A$	2500	${10}^4=2500\times 4$
$B$	2000	${10}^4=2500\times 5$
$C$	1666	${10}^4=1666\times 6+4$
$A\cap B$	500	${10}^4=500\times 20$
$C\cap B$	333	${10}^4=333\times 30+10$
$C\cap A$	833	${10}^4=833\times 12+4$
$A\cap B\cap C$	$166$	${10}^4=166\times 60+40$

Table 1

From the table all value substitute in the first formula:

$\begin{array}{c}\left|\overline{A}\cap \overline{B}\cap \overline{C}\right|=\left|S\right|-\left(\left|A\right|+\left|B\right|+\left|C\right|\right)+\left(\left|A\cap B\right|+\left|B\cap C\right|+\left|C\cap A\right|\right)-\left(\left|A\cap B\cap C\right|\right)\\ ={10}^4-2500-2000-1666+500+333+833-166\\ =5,334\end{array}$

Since The number of integers between $1$ and $10,000$ inclusive that are not divisible by $4,5,$ or $6$ is $\underset{\_}{5,334}$.