[ Fundamental Theorem of Arithmetic. Prime Factorization ] Classical Combinatorics (Miscellaneous)

How many integers from 1 to 16500 exist that

a) are not divisible by 5;

b) are not divisible by 5 or 3;

c) are not divisible by 5, 3, or 11?
a) Let's divide all numbers into $16500: 5=3300$ sequences of five consecutive numbers. In each sequence, one number is divisible by 5, and 4 are not. Therefore, there are $4 \cdot 3300=13200$ numbers that are not divisible by 5.

b) 3300 numbers are divisible by 5. Similarly, $16500: 3=5500$ numbers are divisible by 3. Among them, $16500: 15=1100$ numbers are divisible by 15, which means they are divisible by both 5 and 3. These numbers were counted twice. In total, $3300+5500-1100=$ 7700 numbers are divisible by 5 or 3, and $16500-7700=8800$ numbers are not divisible by either.

c) $16500: 11=1500$ numbers are divisible by 11, $16500: 55=300$ numbers are divisible by both 5 and 11, $16500: 33=$ 500 numbers are divisible by both 3 and 11, and $300: 3=100$ numbers are divisible by 3, 5, and 11.

By the principle of inclusion-exclusion, a total of $5500+3300+1500-1100-500-300+$ $100=8500$ numbers are divisible by 3, 5, or 11, and $16500-8500=8000$ numbers are not divisible by any of these numbers.

## Answer

a) 13200;
b) 8800;
c) 8000 numbers.