Question

How many positive integers less than\(1,000,000\) are

a) divisible by \(2\),\(3\), or \(5\)?

b) not divisible by \(7\),\(11\), or \(13\)?

c) divisible by \(3\) but not by \(7\)?

Short answer

There are \(999,999\)positive integers less than 1,000,000.

(a)\(733,333\) integers are divisible by \(2\),\(3\) or \(5\).

(b)\(719,280\) integers are not divisible by \(7\),\(11\) or 13.

(c)\(285,714\) integers are divisible by \(3\) but not by \(7\).

Step-by-step solution

In the problem given

Positive integers less than \(1,000,000\).

The definition and the formula for the given problem

Division rule If a finite set\(A\)is the union of pairwise disjoint subsets with\(d\)elements each, then\(n = \frac{{|A|}}{d}\)

Note: If |A| not divisible by\(d\), then\(n = \frac{{|A|}}{d}\)

Principle of inclusion-exclusion

\(\left| {{A_1} \cup {A_2} \cup \ldots \cup {A_n}} \right| = \sum\limits_{1 \le i \le n} {\left| {{A_i}} \right|} - \sum\limits_{1 \le i < j \le n} {\left| {{A_i} \cap {A_j}} \right|} + \sum\limits_{1 \le i < j < k \le n} {\left| {{A_i} \cap {A_j} \cap {A_k}} \right|} - \ldots + {( - 1)^{n + 1}}\left| {{A_1} \cap {A_2} \cap \ldots \cap {A_n}} \right|\)

Determining the sum in expanded form

(a) Let \(A = \)Positive integer less than \(1,000,000\)

\({A_1} = \)Divisible by \(2\)

\({A_2} = \)Divisible by 3

\({A_3} = \)Divisible by \(5\)

There are \(999,999\)positive integers less than \(1,000,000\)

\(|A| = 999,999\)

Every 2nd element in the list positive integers is divisible by \(2\).

Using the division rule:

\(\begin{array}{c}\left| {{A_1}} \right| = |A|/d\\ = 999,999/2\\ = 499,999\end{array}\)

Similarly, we obtain:

\(\begin{array}{c}\left| {{A_2}} \right| = |A|/d\\ = 999,999/3\\ = 333,333\\\left| {{A_3}} \right| = |A|/d\\ = 999,999/5\\ = 199,999\\\left| {{A_1} \cap {A_2}} \right| = |A|/d\\ = 999,999/(2.3)\\ = 999,999/77\\ = 166,666\\\left| {{A_1} \cap {A_3}} \right| = |A|/d\\ = 999,999/(2.5)\\ = 999,999/91\\ = 99,999\\\left| {{A_2} \cap {A_3}} \right| = |A|/d\\ = 999,999/(3.5)\\ = 999,999/143\\ = 66,666\\\left| {{A_1} \cap {A_2} \cap {A_3}} \right| = |A|/d\\ = 999,999/(2.3.5)\\ = 999,999/1001\\ = 33,333\end{array}\)

Use the principle of inclusion-exclusion:\(\begin{array}{c}\left| {{A_1} \cup {A_2} \cup {A_3}} \right| = \left| {{A_1}} \right| + \left| {{A_2}} \right| + \left| {{A_3}} \right| - \left| {{A_1} \cap {A_2}} \right| - \left| {{A_1} \cap {A_3}} \right| - \left| {{A_2} \cap {A_3}} \right| + \left| {{A_1} \cap {A_2} \cap {A_3}} \right|\\ = 499,999 + 333,333 + 199,999 - 166,666 - 99,999 - 66,666 + 33,333\\ = 733,333\end{array}\)

Thus \(733,333\) integers are divisible by \(2\),\(3\) or \(5\).

Determining integer not divisible by \(7\),\(11\), and \(13\).

(b) Let \(A = \)Positive integer less than \(1,000,000\)

\({A_1} = \)Divisible by \(7\)

\({A_2} = \)Divisible by \(11\)

\({A_3} = \)Divisible by \(13\)

There are \(999,999\)positive integers less than \(1,000,000\)

\(|A| = 999,999\)

Every 7th element in the list positive integers is divisible by \(7\).

Using the division rule:

\(\begin{array}{c}\left| {{A_1}} \right| = |A|/d\\ = 999,999/7\\ = 142,857\end{array}\)

Similarly, we obtain:

\(\begin{array}{c}\left| {{A_2}} \right| = |A|/d\\ = 999,999/11\\ = 90,909\\\left| {{A_3}} \right| = |A|/d\\ = 999,999/13\\ = 76,923\\\left| {{A_1} \cap {A_2}} \right| = |A|/d\\ = 999,999/(7 \cdot 11)\\ = 999,999/77\\ = 12,987\\\left| {{A_1} \cap {A_3}} \right| = |A|/d\\ = 999,999/(7 \cdot 13)\\ = 999,999/91\\ = 10,989\\\left| {{A_2} \cap {A_3}} \right| = |A|/d\\ = 999,999/(11 \cdot 13)\\ = 999,999/143\\ = 6993\\\left| {{A_1} \cap {A_2} \cap {A_3}} \right| = |A|/d\\ = 999,999/(7 \cdot 11 \cdot 13)\\ = 999,999/1001\\ = 999\end{array}\)

Use the principle of inclusion-exclusion:\(\begin{array}{c}\left| {{A_1} \cup {A_2} \cup {A_3}} \right| = \left| {{A_1}} \right| + \left| {{A_2}} \right| + \left| {{A_3}} \right| - \left| {{A_1} \cap {A_2}} \right| - \left| {{A_1} \cap {A_3}} \right| - \left| {{A_2} \cap {A_3}} \right| + \left| {{A_1} \cap {A_2} \cap {A_3}} \right|\\ = 142,857 + 90,909 + 76,923 - 12,987 - 10,989 - 6993 + 999\\ = 280,719\end{array}\)

Thus 280,719 of the \(999,999\)integers are divisible by \(7\),11 or \(13\).

\(\begin{array}{c}\left| {{{\left( {{A_1} \cup {A_2} \cup {A_3}} \right)}^c}} \right| = |A| - \left| {{A_1} \cup {A_2} \cup {A_3}} \right|\\ = 999,999 - 280,719\\ = 719,280\end{array}\)

Thus \(719,280\) integers are not divisible by \(7\),\(11\) or \(13\).

Determining integer divisible by \(3\) and but not by \(7\)

(c) Let\(A = \)Positive integer less than \(1,000,000\)

\({A_1} = \)Divisible by \(3\)

\({A_2} = \)Divisible by \(7\)

There are \(999,999\)positive integers less than \(1,000,000\)

\(|A| = 999,999\)

Every \(3\)rd element in the list positive integers is divisible by \(3\).

Using the division rule:

\(\begin{array}{c}\left| {{A_1}} \right| = |A|/d\\ = 999,999/3\\ = 333,333\end{array}\)

Similarly, we obtain:

\(\begin{array}{c}\left| {{A_1} \cap {A_2}} \right| = |A|/d\\ = 999,999/(3 \cdot 7)\\ = 999,999/21\\ = 47,619\end{array}\)

Integers divisible by \(3\) but not by \(7\) are the positive integers divisible by \(3\) without the positive integers divisible by both \(3\) and \(7\).

\(\begin{array}{c}\left| {{A_1} \cap A_2^c} \right| = \left| {{A_1}} \right| - \left| {{A_1} \cap {A_2}} \right|\\ = 333,333 - 47,619\\ = 285,714\end{array}\)

Thus \(285,714\) integers are divisible by \(3\) but not by \(7\).