Two of the most basic functions in number theory are the LCM (least common multiple) and GCD/GCF (greatest common denominator/factor) functions. They are opposites of each other, but not in the same way as addition and subtraction, multiplication and division, etc. What do these functions actually mean, and how can we use repetitive methods to evaluate expressions using LCM and GCD?
Greatest Common Denominator (GCD)
First let’s look at the Greatest Common Denominator function. Written as gcd(a, b), the GCD function determines the largest number by which a and b are both divisible. For instance, the GCD of 6 and 8 is 2 because 3, 4, 5, and 6 cannot be divided evenly into both 6 and 8.
Evaluate the GCD of the following pairs of numbers: 3 and 6, 15 and 20, 8 and 20, 3 and 5.
As evidenced by the last problem above, a special case occurs when the two numbers are relatively prime. In familiar terms, this means there are no numbers that can be divided into both a and b except 1. For instance, 7 and 12 are relatively prime and so their GCD is 1.
GCD: A concrete example
Mr. and Mrs. Allman, proud new homeowners, are in the rare position to choose the decor on the house they will inhabit for years to come. They roam the barren rooms with the stolid contractor Mr. Baxter, animatedly conjecturing about the new Jacuzzi, the new modern skylights, etc. But for now, Mr. Baxter brings their attention to a more mundane issue: the kitchen flooring.
“This here kitchen is 24 by 30 feet,” says Mr. Baxter in his stolidly guttural voice. “I need to know the biggest size of tiles I could cover it with.”
Mr. Allman, who happens to teach mathematics at a nearby high school, speaks up. “We could use the greatest common factor function—” Mrs. Allman gently cuts him off. Mathematics has no place in the kitchen.
No, no, let Mr. Allman speak. The GCD of 24 feet by 30 feet would in fact give Mr. Baxter the size of the largest square tile that fits (or divides) evenly into the room dimensions. A little computation tells us that the GCD returns a value of 6 feet.
Mr. Baxter grunts. “Okay, I’ll look into it,” he says grudgingly. “Me, I’ve never seen a 6-foot kitchen tile, but I’ll look into it.”
Find the largest square tile that will fit into a room with these dimensions: 9′ x 12′, 25′ x 24′, 18′ x 30′.
GCD: Two methods for finding it
So far, the only way we’ve considered is by guessing and checking—I think 2 is the GCD; no, wait, 4 is also a factor, so is 6. But what about when we hit numbers with many factors, such as gcd(420, 440)?
Note: Many will find it terrifying that I use the word “algorithm” in the following paragraphs. Please do not fear! An algorithm is simply a series of steps that can be repeated until you get the answer. The below methods are really not that complicated, and I’ve tried to explain them as best I can using that limited medium we call English.
1. The secret lies in prime factorization. To find the prime factors of a number is to find its base code, the series of ingredients from which a number is made. In fact, every integer can be written as the product of prime factors. If we find the prime factorization of 420, we find that
When we prime factorize 440, we find that
The trick to finding the GCD is for each prime number we see, putting the term with the smaller power into the answer. If a prime factor isn’t in both numbers, we can’t accept it because there’s no way it will divide evenly into both numbers. For instance, we’ll take 2 squared and reject 2 cubed. We won’t take 3 because it’s not in 440’s factorization. We’ll also take 5, but not 7 or 11. Multiplying all these factors together, we get a final GCD of 20.
2. The second algorithm is a classic one used frequently by computers, but it can help you, too. Given gcd(240, 440), first determine the larger number—obviously 440. Now subtract the smaller number, 240, from this: 200. Then repeat given the difference and the smaller number: gcd(200, 240). We then arrive at gcd(40, 200), then gcd(160, 40), then gcd(120, 40), gcd(80, 40), gcd(40,40). Stop! We can’t go any further. The GCD of 240 and 440 is irrevocably 40.
In symbols, this method can be expressed much more simply. Given that a is a smaller number than b, we can declare that gcd(a, b) = gcd(b – a, a). When a = b, we have our GCD.
How can we explain this method’s captivating simplicity and consistency? To do this we need to return to Mr. and Mrs. Allman, standing in the floorless kitchen, the sound of Mr. Baxter’s boots echoing on the concrete as he searches for 6-foot tiles.
“That was a fascinating application of math, dear,” says Mrs. Allman. “How on earth could you know that 6 feet is the right number?”
“Well, honey,” says Mr. Allman, falling into the lingo of his algebra class, “look at the shape of this floor: 24 feet by 30 feet. A square tile will of course fit into a square space, right?”
“Whatever you say, sweetie,” says Mrs. Allman dreamily.
“Yes, well.” Mr. Allman clears his throat and straightens his glasses. “If a square tile can fit into the a square space, we can remove a square space from the room and focus our attention on the remaining part: only 24 feet by 6 feet. Then we can remove another square space, and another, and another, and all we have left is a 6 by 6 square. And there’s the answer!” Mr. Allman seems to stand up straighter at that moment, as though the answer itself has reinforced his posture.
“That’s simply wonderful, dear,” said Mrs. Allman. “How much did you say the Jacuzzi would cost?”
Returning to the pristine world of mathematics, Mr. Allman has showed that the GCD can be found by removing square sections of a rectangle. The final square section remaining is the long-awaited answer.
Practice using both methods described above by calculating gcd(261, 378) and gcd(144, 162).
In the next post, we’ll discuss the lowest common multiple and its similarity to the GCD. If you have any questions, please leave a comment below.