TheCATExam
Sign in

CAT 2020 Slot 3 — QA Question 25

DivisibilityMedium

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

Answer & solution

Correct answer: 41

  • A

    42

  • 41

  • C

    40

  • D

    43

Solution

Medium

Count the integers from 11 to 120120 that are divisible by at least one of 2,5,72,5,7 using inclusion–exclusion, then subtract from 120120. Here n(d)=⌊120/d⌋n(d)=\left\lfloor 120/d\right\rfloor is the count of multiples of dd.

1

Single multiples. Count multiples of each of 2,5,72,5,7 up to 120120.

n(2)=⌊120/2⌋=60n(5)=⌊120/5⌋=24n(7)=⌊120/7⌋=17\begin{aligned} &n(2)=\left\lfloor 120/2\right\rfloor = 60\\ &n(5)=\left\lfloor 120/5\right\rfloor = 24\\ &n(7)=\left\lfloor 120/7\right\rfloor = 17 \end{aligned}
2

Pairwise multiples. Count multiples of each product of two of them.

n(10)=⌊120/10⌋=12n(35)=⌊120/35⌋=3n(14)=⌊120/14⌋=8\begin{aligned} &n(10)=\left\lfloor 120/10\right\rfloor = 12\\ &n(35)=\left\lfloor 120/35\right\rfloor = 3\\ &n(14)=\left\lfloor 120/14\right\rfloor = 8 \end{aligned}
3

Triple multiples. Count multiples of 2⋅5⋅7=702\cdot5\cdot7=70.

n(70)=⌊120/70⌋=1\begin{aligned} &n(70)=\left\lfloor 120/70\right\rfloor = 1 \end{aligned}
4

Inclusion–exclusion. Combine to get how many are divisible by at least one of 2,5,72,5,7.

n(2∪5∪7)=n(2)+n(5)+n(7)−n(10)−n(35)−n(14)+n(70)⇒ =60+24+17−12−3−8+1(steps 1–3)⇒ =79\begin{aligned} &n(2\cup5\cup7) = n(2)+n(5)+n(7) - n(10)-n(35)-n(14) + n(70)\\ &\Rightarrow\ = 60+24+17 - 12-3-8 + 1 \quad\text{(steps 1–3)}\\ &\Rightarrow\ = 79 \end{aligned}
5

Take the complement. Divisible by none == total −- divisible by at least one.

answer=120−79(from step 4)⇒ answer=41\begin{aligned} &\text{answer} = 120 - 79 \quad\text{(from step 4)}\\ &\Rightarrow\ \text{answer} = 41 \end{aligned}
41\boxed{41}

Related Divisibility questions

See all Number Theory questions →
CAT 2020 Slot 3 QA Q25 — Divisibility solution | TheCATExam