Integers not divisible by 2, 5, or 7

CAT 2020 Slot 3 · Quantitative Ability · Hard · Number theory

How many of the integers 1,2,…,1201, 2, \dots, 120, are divisible by none of 2, 5 and 7?

  1. A.

    41

  2. B.

    42

  3. C.

    40

  4. D.

    43

Answer

A

Explanation

Using Principle of Inclusion-Exclusion for n=120n = 120: AA: divisible by 2   ⟹  ∣A∣=60\implies |A| = 60 BB: divisible by 5   ⟹  ∣B∣=24\implies |B| = 24 CC: divisible by 7   ⟹  ∣C∣=17\implies |C| = 17

∣A∩B∣=⌊120/10⌋=12|A \cap B| = \lfloor 120/10 \rfloor = 12 ∣B∩C∣=⌊120/35⌋=3|B \cap C| = \lfloor 120/35 \rfloor = 3 ∣A∩C∣=⌊120/14⌋=8|A \cap C| = \lfloor 120/14 \rfloor = 8 ∣A∩B∩C∣=⌊120/70⌋=1|A \cap B \cap C| = \lfloor 120/70 \rfloor = 1

Total divisible by at least one = 60+24+17−(12+3+8)+1=101−23+1=7960 + 24 + 17 - (12 + 3 + 8) + 1 = 101 - 23 + 1 = 79. Number of integers divisible by none = 120−79=41120 - 79 = 41.

Related Number theory questions

Practise this under exam conditions

Sign in to solve it with a live timer, the on-screen CAT calculator, and streak and accuracy tracking across every question you attempt.

Solve in the workspace