Number Theory
4.3 GCD and LCM
Greatest Common Divisor (GCD)
Now we'll focus on a more frequently used topic of interest out of Number Theory. Consider the following problem:
There are two fourth-grade classrooms at some elementary school. Class A has 24 students and Class B has 30 students. The school wants to divide the students into teams such that:
- Each team must have students from the same class.
- All teams must be equal size.
- Every student must be on exactly one team.
- Teams should have as many students as possible.
How many teams can be made? How many students are on each team?
Definition: Greatest Common Divisor (GCD)
For nonzero whole numbers $a$ and $b$, $\gcd(a,b)$ is the largest whole number dividing both $a$ and $b$.
The Intersection of Sets Method
Example: Team-size interpretation
Class A has 24 students and Class B has 30 students. Teams must be equal size, within-class only, and as large as possible. What team size works?
Show Solution
To find the largest number that divides both numbers, a good place to start is to look at the set of divisors for each number.
Factors of 24: $$D_{24}=\{1,2,3,4,6,8,12,24\}$$
Factors of 30: $$D_{30}=\{1,2,3,5,6,10,15,30\}$$
Theres no guess work here, we can see the largest number these two sets have in common is $6$.
$$D_{24}\cap D_{30}=\{1,2,3,6\}$$
Largest common factor is 6, so each team has 6 students.
Then Class A has $24\div 6=4$ teams and Class B has $30\div 6=5$ teams.
MyOpenMath: Interpreting GCD in context
Numberline Method
The GCD of two numbers is nicely visualized on a numberline. Because the GCD of two numbers divides both numbers, they can be divided evenly into the same size segments.
Prime Factorization Method
Both the numberline and the set method are nice physical models we can use to explain the idea of GCDs, but in practice they can be tedious. Especially if the numbers get large. A slightly better method might be to list the prime factors of the numbers. Then we can build the greatest divisor by taken the largest amount of shared factors possible.
Example: GCD by prime exponents
Find $\gcd(180,168)$.
Show Solution
First, we list the prime factors of each number.
$$180=2^2\cdot 3^2\cdot 5,\qquad 168=2^3\cdot 3\cdot 7.$$
Both numbers have $2$ and $3$ in common. But even better, both numbers have two $2$'s that can be used.
$$\gcd(180,168)=2^{\min(2,3)}3^{\min(2,1)}=2^2\cdot 3=12.$$
That "minimum exponent" is just counting the most we can take from both numbers.
MyOpenMath: GCD Prime Factorization method
Euclidean Algorithm
An even more efficent algorithm for finding the GCD of two numbers is the Euclidean Algorithm. The Euclidean algorithm takes advantage of the fact
$$(c|a) \land (c|b) \rightarrow c|(a-b)$$
as long as $a>b$.
In other words, if you have two whole numbers with $a>b$, whatever the $\gcd(a,b)$ might be, it divides both $a$ and $b$ by definition. That means it will also divide $a-b$. So we can simplify our expression.
$$\gcd(a,b)=\gcd(a-b,b)$$
Lets get some concrete numbers here to better understand whats going on. Lets pick $105$ and $45$.
The $\gcd(105,45)$ is the same as the $$\gcd(105-45,45)=\gcd(60,45)$$
Theres nothing stopping us from repeating the process.
$$\gcd(60-45,45)=\gcd(15,45)$$
Its also true that
$$\gcd(15,45)=\gcd(45,15)$$
(why?) Continuing the process,
$$\gcd(45,15)=\gcd(30,15)=\gcd(15,15)=\gcd(15,0)=15$$
We've simplified this problem over and over again with repeated subtraction, which is just division. So we can replace this whole process with something much simpler.
Theorem: Euclidean Algorithm
If $a>b>0$ and $a=bq+r$ with $0\le r<b$, then
$$\gcd(a,b)=\gcd(b,r).$$
Keep replacing the pair $(a,b)$ by $(b,r)$ until remainder 0. The last nonzero remainder is the GCD. Because trivially, every number divides zero. And the largest number that divides 0 and some other number will be that other number.
Example: Euclidean algorithm in action
Find $\gcd(10764,2300)$.
Show Solution
To find $\gcd(10764,2300)$ we can start by dividing the larger by the smaller and finding the remainder.
$$10764=2300(4)+1564$$
So our expression becomes $\gcd(2300,1564)$. Rinse and repeat.
$$2300=1564(1)+736$$
So now we're looking for $\gcd(1564,736)$. Again.
$$1564=736(2)+92$$
Means $\gcd(1564,736)=\gcd(736,92)$. Finally,
$$736=92(8)+0$$
$\gcd(736,92)=\gcd(92,0)$ and the last nonzero remainder is 92, so
$$\gcd(10764,2300)=92$$
Notice how quickly the numbers shrink compared to full factorization.
$$10764=92\cdot 117$$ $$2300=92\cdot 25$$
MyOpenMath: Euclidean GCD algorithm
Least Common Multiple (LCM)
The least common multiple of two numbers is similar to the GCD, but instead of finding the greatest number that divides both, we're finding the smallest number that is divisible by both. Its a turn on the question. Consider the following example:
Example
For the grand opening of a new restaurant, the owner is giving away a free drink to every 12th customer and a free dessert to every 15th customer. If Tommy wants to get both a free drink and a free dessert, what number customer should he be?
Show Solution
Well, as far as free drinks are concerned, the customer would have to be numbered one of these:
$$\{12,24,36,48,60,72,\ldots\}$$
And for free desserts the customer would have to be one of these numbers:
$$\{15,30,45,60,75,90,\ldots\}$$
We see that the first number that is in both sets is 60. Therefore, Tommy should be the 60th customer.
Definition: Least Common Multiple (LCM)
For nonzero whole numbers $a$ and $b$, $\operatorname{lcm}(a,b)$ is the smallest positive whole number divisible by both $a$ and $b$.
Multiples/Intersection Method
The solution to the previous example listed multiples and found the first overlap. This is again our set interpretation model.
$$M_{12}=\{12,24,36,48,60,\ldots\},\quad M_{15}=\{15,30,45,60,\ldots\}$$
So $\operatorname{lcm}(12,15)=60$.
Prime Factorization Method
Another model can be built using the prime factorization of both numbers, similar to the GCD. But instead of taking the minimum exponent of only the common factors, we take every prime appearing in either number, with the larger exponent.
This ensures that the number we build is divisible by both numbers. As long as we don't take any additional factors other that what is necessary to cover both numbers, we'll be sure to have the smallest such number.
Example: LCM by prime exponents
Find $\operatorname{lcm}(40,12)$.
Show Solution
Factor both:
$$40=2^3\cdot 5,\qquad 12=2^2\cdot 3.$$
To build a number divisible by $40$, we're going to need at least $2^3\cdot 5$. But to be divisble by $12$, we're also going to need a $3$ ($12$ also recuires two $2$'s but we've already got enough twos to cover that). So,
$$\operatorname{lcm}(40,12)=2^3\cdot 3\cdot 5=120$$
You can think of LCM as "enough prime ingredients to build both numbers."
MyOpenMath: LCM word problem
GCD-LCM Product Relationship
To see the connection between the GCD and LCM more visually, compare the prime factors of 24 and 30 using a Venn diagram.
The overlap contains the common prime factors $2$ and $3$, so it gives the GCD: $\gcd(24,30)=2\cdot 3=6$. The full collection of factors in both circles gives the LCM: $\operatorname{lcm}(24,30)=2^3\cdot 3\cdot 5=120$.
Multiplying the GCD and the LCM together gives the product of the original numbers.
$$\gcd(24,30)\cdot \operatorname{lcm}(24,30) = (2\cdot 3) (2\cdot 2 \cdot 2 \cdot 3 \cdot 5)$$ $$\gcd(24,30)\cdot \operatorname{lcm}(24,30) = (2^3\cdot 3)(2\cdot 3 \cdot 5)$$ $$\gcd(24,30)\cdot \operatorname{lcm}(24,30) = (24)(30)$$
This is an incredible relationship that will allow us to leverage the Euclidian Algorithm to also find the LCM of two numbers.
Theorem: GCD-LCM Product
For nonzero whole numbers $a$ and $b$,
$$\gcd(a,b)\cdot \operatorname{lcm}(a,b)=ab.$$
Example: Use GCD to get LCM quickly
Find $\operatorname{lcm}(731,952)$.
Show Solution
First compute $\gcd(731,952)$:
$$952=731(1)+221$$ $$731=221(3)+68$$ $$221=68(3)+17$$ $$68=17(4)+0$$
So $\gcd(731,952)=17$.
Now apply the product rule:
That is much faster than full prime factorization for both numbers.