3.1.1 GCD and LCM

How finding the Greatest Common Divisor (or GCD) is taught in classes usually involves prime factorizing the two numbers and then comparing powers of exponents. However, this is not the most efficient way of doing it during a number sense competition. One of the quickest way of doing it is by employing Euclid’s Algorithm who’s method won’t be proven here (if explanation is necessary, just Google to find the proof).

The following outlines the procedure:

1. Arrange the numbers so that $n_1 < n_2$ then find the remainder when $n_2$ is divided by $n_1$ and call it $r_1$.
2. Now divide $n_1$ by $r_1$ and get a remainder of $r_2$.
3. Continue the procedure until any of the remainders are 0 and the number you are dividing by is the GCD or when you notice what the GCD of any pair of numbers is.

Let’s illustrate with some examples:

Problem: GCD(36, 60) Solution: Well, when 60 is divided by 36 it leaves a remainder of 24. So, GCD(36, 60) = GCD(24, 36). Continuing the procedure, when 36 is divided by 24 it leaves a remainder of 12. So, GCD(36, 60) = GCD(24, 36) = GCD(12, 24), which from here you can tell the GCD is 12. You could also have stopped after the first step when you notice that the GCD(24, 36) is 12, and you wouldn’t have to continue the procedure.

Problem: GCD(108, 140) Solution: GCD(108, 140) → GCD(32, 108) → GCD(12, 32) → GCD(8, 12) → GCD(4, 8) = 4

If at any point in that process you notice what the GCD of the two numbers is by observation, you can cut down on the amount of steps in computation.

For computing the LCM between two numbers $a$ and $b$, I use the formula:

$$\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$$

So to find what the LCM is, we must first compute the GCD. Using a prior example, let’s calculate the LCM(36, 60):

$$\text{LCM}(36, 60) = \frac{36 \times 60}{12} = 3 \times 60 = 180$$

The procedure is simple enough, let’s do one more example.

Problem: Find the LCM of 44 and 84. Solution: GCD(44, 84) = GCD(40, 44) = GCD(4, 40) = 4 ⇒ LCM(44, 84) = $\frac{44 \times 84}{4} = 11 \times 84 = 924$

It should be noted that there are some questions concerning the GCD of more than two numbers (usually not ever more than three). The following outlines the procedure which should be followed:

1. Find the GCD of two of the numbers.
2. Find the LCM of those two numbers by using the GCD and the above formula.
3. Calculate the GCD of the LCM of those two numbers and the third number.

It should be noted that usually one of the numbers is a multiple of another, thus leaving less required calculations (because the LCM between two numbers which are multiples of each other is just the larger of the two numbers).

The following are some more practice problems for finding GCDs and LCMs using this method:

Problem Set 3.1.1