Possible values for HCF = 60

If the HCF of two numbers is h, the two numbers can be assumed as (h × a) and (h × b), where a and b are co-prime.

Here, we have (60 × 150) and X = (60 × k). How many values can k assume such that it is co-prime to 150?

B. 40

Since HCF is 60, X has to be a multiple of 60, say X = 60 × k

9000 = 60 × 150

For HCF to be 60, k & 150 must be co-prime. Also for X to be less than 9000, k < 150.

Thus, we need to find how many numbers less than 150 are co-prime to 150. This is the classic Totient function, if you are aware of it.

The number of numbers less than n and co-prime to n is given by …

$$n \times \left(1-\frac{1}{p_1}\right) \times \left(1-\frac{1}{p_2}\right) \times \left(1-\frac{1}{p_3}\right) …. $$

… where p₁, p₂, p₃, …. are prime factors of n.

In this case, 150 = 2 × 3 × 5².

Thus, k can assume \(150 \times \left(1-\frac{1}{2}\right) \times \left(1-\frac{1}{3}\right) \times \left(1-\frac{1}{5}\right) \)

i.e. \(150 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 40\)

⇒ X can also assume 40 different values.

If you did not know the above totient function, you would have to proceed as follows …

Possible values of k:

Can be any of the following prime number or even multiples of these primes: 7, 11, 13, 17, 19, 23, ….

From 1 to 150, there are 32 prime numbers, after excluding 2, 3 & 5. This is one bit that you will need to know or it will take time to count them.

Further ….

Multiples of 7: 7 × 7, 7 × 11, 7 × 13, 7 × 17, 7 × 19, that’s it, because 7 × 23 will be more than 150. So 5 possibilities.

Multiples of 11: 11 × 11, 11 × 13. Just 2 possibilities.

Multiples of 13 or higher primes, not considered in the above will be more than 150.

The tricky bit is that k can also take the value of 1 i.e. X = 60 itself and HCF of (9000, 60) is 60.

Total number of possible values of k and hence of X = 32 + 5 + 2 + 1 = 40