Home › Number theory

How many numbers are divisible by two given numbers

The rule: an intersection of divisibility sets uses the LCM

A number belongs to both divisibility sets precisely when it is a multiple of $lcm (a, b)$ . In an integer interval from $L$ to $U$ , the count is $⌊ U / m ⌋ - ⌊(L - 1) / m ⌋$ , where $m = lcm (a, b)$ .

Problem

Let $A$ be the set of two-digit numbers divisible by $3$ , and let $B$ be the set of two-digit numbers divisible by $7$ . How many numbers are in $A \cap B$ ?

Answer

There are

4

two-digit numbers divisible by both

3

and

7

21

42

63

and

84

The list and the interval-counting formula give the same result.

Step-by-step solution

Turn the intersection into one divisibility condition

The numbers in $A \cap B$ must be divisible by both $3$ and $7$ . Because the two numbers are prime and distinct,

lcm (3, 7) = 3 \cdot 7 = 21

So the question is equivalent to counting the two-digit multiples of $21$ .

List or count the multiples

The relevant multiples are

21, 42, 63, 84

The next one is $105$ , which is no longer a two-digit number. Thus there are $4$ numbers.

The interval formula confirms the count for $10 \leq n \leq 99$ :

⌊ \frac{99}{21} ⌋ - ⌊ \frac{9}{21} ⌋ = 4 - 0 = 4

How to check yourself

Do not count multiples of $3$ and multiples of $7$ separately and add them. The intersection asks for numbers satisfying both conditions, so the LCM is the single step that combines them.

Add to Chrome - solve your own

Screenshot any problem on your screen and get the steps. Chrome on a computer; free.