GATE CSE 1995 | Question: 25b

Question

Determine the number of positive integers $(\leq 720)$ which are not divisible by any of $2,3$ or $5.$

Answer 1

Numbers divisible by $5 = \left\lfloor\frac{720}{5}\right\rfloor = 144.$

Numbers divisible by $2 = \left\lfloor\frac{720}{2}\right\rfloor = 360.$

Numbers divisible by $3 = \left\lfloor\frac{720}{3}\right\rfloor = 240.$

Numbers divisible by either $5,2$ or $3 = 144 + 360 + 240$
$\qquad \qquad -$ Numbers divisible by $2$ and $3$
$\qquad \qquad-$ Numbers divisible by $2$ and $5$
$\qquad \qquad-$  Numbers divisible by $3$ and $5$
$\qquad \qquad+$ Numbers divisible by $2,3$ and $5.$

Since, all $2,3,5$ are prime numbers,

• Numbers divisible by $2$ and $3=$ Numbers divisible by $(2\times 3) = \left\lfloor\frac{720}{6}\right\rfloor = 120$
• Numbers divisible by $2$ and $5=$ Numbers divisible by $(2 \times 5) = \left\lfloor\frac{720}{10}\right\rfloor = 72$
• Numbers divisible by $3$ and $5=$ Numbers divisible by $(3 \times 5) = \left\lfloor\frac{720}{15}\right\rfloor = 48$
• Numbers divisible by $2,3$ and $5=$ Numbers divisible by $(2 \times 3 \times 5) = \left\lfloor\frac{720}{30}\right\rfloor = 24$

So, numbers divisible by either $5,2$ or $3$ $= 144+360 + 240 - 120 - 72 -48 + 24 = 528.$

So, numbers which are not divisible by any of $2,3$ or $5 = 720 -528 = 192.$

Correct Answer: 192.

Comments

@belliot

actually the numbers divisible by both a,b=numbers divisible by Least common multiple of(a,b).

for example,numbers divisible by 2={2,4,6,8,10,12,14,16,18,20,22,24,26,28......}

and numbers divisible by 4={4,8,12,16,20,24,28....}.

Now the numbers divisible by both 2,4

=intersection of {2,4,6,8,10,12,14,16,18,20,22,24,26,28......} and {4,8,12,16,20,24,28....}.

={4,8,12,16,20..}

=Numbers divisible by 4

=numbers divisible by l.c.m of 2,4

But if the numbers a,b are co prime, their l.c.m is nothing but their product i.e., a*b.

Here 2,3 are co prime so their l.c.m is 2*3=6. same thing applies for 2,5 and 3,5.

Hope this clarifies your doubt..

@Arjun sir ,i think it is better to add this point.

---

@Arjun

One small correction. The peach colored circle in the venn diagram needs to have 48 instead of 44.

---

@ chirudeepnamini
Awesome explanation

Answer 2

An idea of probability can be used here. Let $p, ~ q,~ r$ be the probability of having a number divisible by $2, ~3, ~5$ respectively.

If we notice from the set of natural numbers $\mathbb{N}=\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,\cdots,\infty\}$, we observe that any one of every $2$ consecutive numbers is divisible by $2$. Again, any one of every $3$ consecutive numbers is divisible by $3$. The same goes for $5$. Therefore $$p = \frac{1}{2}\\q = \frac{1}{3}\\r = \frac{1}{5}$$

 

Now the complement of these probabilities are $p', ~ q', ~ r'$ meaning that the probabilities of having a number NOT divisible by $2,~3,~5$ respectively. Therefore, $$p' =1- \frac{1}{2}=\frac{1}{2}\\q' =1- \frac{1}{3}=\frac{2}{3}\\r' =1- \frac{1}{5}=\frac{4}{5}$$

So the probability of having a number NOT divisible by 2 or 3 or 5 is $\mathrm{P}= p'\times q'\times r'$. [It can be thought of De Morgan's law, $(p \vee q \vee r)'=p' \wedge q' \wedge r'$ ]

$$ \therefore \mathrm{P}=p' \times q' \times r' =\frac{1}{2} \times \frac{2}{3} \times \frac{4}{5}= \frac{4}{15}$$

The number of positive integers out of the first 720 positive integers NOT divisible by 2 or 3 or 5 is $ \left[ 720 \mathrm{P} \right]=\left[ 720\times \frac{4}{15} \right]=192$.

 

So the answer is $192$.

Comments

@rajankakaniya @techbd123

I wrongly calculated using (1/3 + 1/5 + 1/7)*500.

it should not be like this,

it is like  either only div by 3/5/7 or div by all(3/5/7)

which can be written as  (1- div by none). 

---

@Deepak Poonia

@Sachin Mittal 1

 

sir why i can’t apply this probability method on below gate problem  ??

https://gateoverflow.in/118330/gate-cse-2017-set-1-question-47

---

How do we know when to add, or multiply the probabilities of events?

→ When we are considering mutually exclusive events (things that cannot happen at the same time), there we add the probabilities.

→ Whereas, when we are considering mutually inclusive events (two or more different events that can happen at the same time), there we multiply the probabilities. The key here is that events are independent (i.e., the happening of an event does not affect the other).

src: https://math.stackexchange.com/questions/184115/in-need-of-tips-suggestions-when-to-add-or-multiply-probabilities