Consider the first 100 natural numbers. How many of them are not divisible by any one of 2, 3, 5, 7 and 9 ?
- (a) 20
- (b) 21
- (c) 22 ✓ UPSC's answer
- (d) 23
Why the answer is (c)
• Note that 9 is a multiple of 3, so any number divisible by 9 is also divisible by 3. Thus, the condition 'not divisible by 2, 3, 5, 7, and 9' is equivalent to 'not divisible by 2, 3, 5, or 7'.
• We use the Principle of Inclusion-Exclusion to count numbers in {1, ..., 100} divisible by at least one of 2, 3, 5, 7.
• Count of multiples: |A2|=50, |A3|=33, |A5|=20, |A7|=14.
• Count of pairwise intersections: |A2∩A3|=16, |A2∩A5|=10, |A2∩A7|=7, |A3∩A5|=6, |A3∩A7|=4, |A5∩A7|=2. Sum = 45.
• Count of triple intersections: |A2∩A3∩A5|=3, |A2∩A3∩A7|=2, |A2∩A5∩A7|=1, |A3∩A5∩A7|=0. Sum = 6.
• Count of quadruple intersection: |A2∩A3∩A5∩A7|=0.
• Total divisible = (50+33+20+14) - 45 + 6 - 0 = 117 - 45 + 6 = 78. Numbers not divisible = 100 - 78 = 22.
Why the other options are wrong
- (a) 20
- The calculation yields 22, not 20, as the inclusion-exclusion sum of multiples is 78.
- (b) 21
- The calculation yields 22, not 21, as the inclusion-exclusion sum of multiples is 78.
- (d) 23
- The calculation yields 22, not 23, as the inclusion-exclusion sum of multiples is 78.
Asked in the CSAT Paper II of the UPSC Civil Services Preliminary Examination 2025, held on 25 May 2025. Question and answer key: Union Public Service Commission. Explanation: UPSC Answer Check.