What is the cardinality of the set of integers defined below? X = {n | 1 <= n <= 123, n is not divisible by either 2, 3, or 5} A. 30 B. 33 C. 37 D. 44

GATE 2006 · Discrete Mathematics · Set Theory · medium

Answer: The cardinality of X is 33.

1. Count multiples of each prime and their LCMs: |div2| = floor(123/2) = 61; |div3| = floor(123/3) = 41; |div5| = floor(123/5) = 24; |div6| = floor(123/6) = 20; |div10| = floor(123/10) = 12; |div15| = floor(123/15) = 8; |div30| = floor(123/30) = 4.
2. Apply inclusion-exclusion and take complement: |A ∪ B ∪ C| = 61 + 41 + 24 - 20 - 12 - 8 + 4 = 90. |X| = 123 - 90 = 33.