Solutions to Number theory questions - LCM HCF

Have given below solutions to the questions on Number Theory LCM, HCF. The questions can be found here.

Solutions sent it at the yahoogroups were more or less spot on, so I am just replicating that here

1. How many pairs of integers (x,y) exist such that the product of x, y and HCF (x,y) = 1080?

We need to find ordered pairs (x, y) such that xy*HCF(x, y) = 1080.

Let x = ha and y = hb where h = HCF(x, y) => HCF(a, b) = 1.

So h^3(ab) = 1080 = (2^3)(3^3)(5).

We need to write 1080 as a product of a perfect cube and another number.

Four cases:

I h = 1, ab = 1080 and b are co-prime. We gave 4 pairs of 8 ordered pairs (1,1080), (8, 135), (27,40) and (5,216) (Essentially we are finding co-prime a,b such that a*b = 1080)

II h = 2, We need to find number of ways of writing (3^3) * (5) as a product of two coprime numbers. This can be done in two ways - 1 and (3^3) * (5) , (3^3) and (5)

number of pairs = 2, number of ordered pairs = 4

III - h = 3, number of pairs = 2, number of ordered pairs = 4

IV - h = 6, number of pairs = 1, number of ordered pairs = 2

Hence total pairs of (x, y) = 9, total number of ordered pairs = 18.

The pairs are (1,1080), (8, 135), (27,40), (5,216), (2,270), (10, 54), (3,120), (24,15) and (6,30),

2. Find the smallest number that leaves a remainder of 4 on division by5, 5 on division by 6, 6 on division by 7, 7 on division by 8 and 8 on division by 9?

LCM(5, 6, 7, 8, 9) - 1 = 2519.

3. There are three numbers a,b, c such that HCF (a,b) = l, HCF(b,c) =m and HCF (c,a) = n. HCF(l,m) = HCF(l,n) = HCF(n,m) =1. Find LCM of a,b,c. (The answer can be "This cannot be determined").

a is a multiple of l and n. Also HCF (l,n) =1; => a has to be a multiple of ln, similarly b has to be a multiple of lm and c has to be a multiple of mn.

We can assume, a = lnx, b = lmy, c = mnz.

Now given that HCF(a, b) = l, that means HCF(nx, my) = 1. This implies HCF(x, y) = 1 and HCF(m, x) = HCF(n, y) = 1.

Similarly it can also be shown that HCF(y, z) = HCF(z, x) = 1 and others also.

So in general it can be written any two of the set {l, m, n, x, y, z} are co-prime.

Now LCM(a, b, c) = LCM(lnx, lmy, mnz) = lmnxyz = abc/lmn.

Quiet obviously, it is a reasonable assumption that a question in CAT will not be as tough as the last one here. However, it is a good question to get an idea of the properties of LCM and HCF.