Dual GCD and LCM

Today's question is more about understanding mathematic concepts and formulas rather than solving a question with a definite answer. Even with that, it's very good.

LCM(a, b) = 120 and GCD(a, b) = 4. Find all possible a and b.

Let's do it in two ways: by definition and by a well known formula.

First, let's go by the definition. The LCM of two numbers is the smallest number that both numbers divide. A good way to find it is completely factoring two numbers and taking the highest degree of each factor. That means the highest degree of factors in a and b are:
120 = 2³ * 3 * 5 = 2 * 2 * 2 * 3 * 5

This means the two numbers can be made up of any combination of factors you want, which gives 5!/3! = 20 possibilities for each number, a and b. However, the GCD is also limiting us.

The GCD is the biggest number that divides both numbers (when dividing each number by this number, there is no remainder). To find it, you take the lowest degree of each factor of each number and multiply them. This means that both numbers cannot have 3 twos in their factorized form, and they cannot have both 3 and 5 as factors. However, each of them must have 2 * 2 as a factor. Using the GCD and LCM, we can finally find a and b:

a = 2 * 2 = 4
b = 2 * 2 * 2 * 3 * 5 = 120

a = 2 * 2 * 2 = 8
b = 2 * 2 * 3 * 5 = 60

a = 2 * 2 * 3 = 12
b = 2 * 2 * 2 * 5 = 40

a = 2 * 2 * 5 = 20
b = 2 * 2 * 2 * 3 = 24

Any other pair is just a mirror of the previous pair, so these are the four possibilities for a and b (as said, they can be reversed).

Now, let's use the formula. There is a well known formula saying that GCD(a, b) * LCM(a, b) = a * b. The boundries of a and b in this situation are the GCD (if a number is below it, the GCD must be smaller) and the LCM (if a number is above it, the LCM must be bigger). Now let's find the pairs using some trial and error:

a = 4
b = 120
Works

a = 8
b = 60
Works too

a = 16
b = 30
The product is correct, but the GCD of these numbers isn't 4 (30 is not divisible by 4). This pair is rejected.

a = 12
b = 40
Works

a = 24
b = 20
Works as well

a = 48
b = 10
Fails, 10 is not divisible by 4

a = 20
b = 24
Already proven to work

a = 40
b = 12
Another duplicate

a = 80
b = 6
Fails - 6 is not divisible by 4

a = 120
b = 4
Duplicate

As you can see, the two methods give the same answer. Whatever method you choose, you will get the same answer. Take what you're comfortable with, and you will succeed. That's the motto of Super Math Tips.

Enjoy,
Nadav

nadavs