$Project Greater Ed Logo$

Using Prime Factorizations to Find GCD’s and LCM’s

Discrete Mathematics Greatest Common Factors, Least Common Multiples, and Coprimality Using Prime Factorizations to Find GCD’s and LCM’s

Recall that we defined the Greatest Common Divisor of two integers $a$ and $b$ to be the greatest positive integer that divides both $a$ and $b$. Similarly, we defined the Least Common Multiple of $a$ and $b$ to be the smallest integer that both $a$ and $b$ divide.

In turns out that we can use prime factorizations of our integers $a$ and $b$ to find GCD’s and LCM’s.

Finding GCD’s Using Factorizations

Let $a$ and $b$ be positive integers. We can find the GCD of $a$ and $b$ by first factoring $a$ and $b$, then seeing what prime factors $a$ and $b$ have in common. The product of the prime factors that $a$ and $b$ have in common form your GCD of $a$ and $b$.

Example Supporting Why This Works

Let $a=60$ and $b=24$. Clearly, $gcd(60,24)=12$. Let’s use the method described in the box above to show that this is correct.

Note that $a=60=2^2\cdot 3\cdot 5$ and $b=24=2^3\cdot 3$. Notice that both the prime factorizations of these two numbers have, at most, factors $2^2$ and $3$ in common. So, the greatest common divisor of $a$ and $b$ must be $2^2\cdot 3$, which is exactly $12$.

Notice that the above indicates that the greatest common divisor of two numbers $a$ and $b$ is exactly the product of the greatest power of primes that both $a$ and $b$ have in common.

For Least Common Multiples, we use a similar method.

Finding LCM’s Using Factorizations

Let $a$ and $b$ be positive integers. We can find the Least Common Multiple of $a$ and $b$ by finding the greatest prime power factors of $a$ or $b$ and then multiplying them.

Example Supporting Why This Works

Suppose we have $a=24$ and $b=50$. Note that $a=24=2^3\cdot 3$ and $b=50=2\cdot 5^2$. The least common multiple of $a$ and $b$ is the product of the greatest power of each prime you see in these factorizations. Thus, $lcm(24,50)=2^3\cdot 3\cdot 5^2=600$.

This all works out because LCM is the smallest integer $n$ where $a$ and $b$ BOTH divide $n$. So, every factor of $a$ and $b$ must also be a factor of the LCM. Hence, in the above example, we know that the LCM of $a=24$ and $b=50$ must have a factor of $2^3$ and $3$ because $a$ has these factors. It also needs to have a factor of $5^2$ because $b$ has that as a factor. The factor of $2$ in $b$ is already “accounted for” in the factor $2^2$ in $a$. So, the LCM is the product of prime powers that “accounts for” every prime power factor in each of $a$ and $b$.

Theorem

Let $n,m\in\mathbb{N}$. Then $n\cdot m=gcd(n,m)\cdot lcm(n,m)$.

$gcd(12,30)=2\cdot 3=6$

$lcm(12,30)=2^2\cdot 3\cdot 5$

$a=12=2^2\cdot 3$

$b=30=2\cdot 3\cdot 5$

GCD is the product of the greatest prime powers that are found in BOTH factorizations. Hence, $gcd(12,30)=2\cdot 3=6$.

LCM is the product of the greatest prime powers found in either $a$ OR $b$. Hence, $lcm(12,30)=2^2\cdot 3\cdot 5$.

$gcd(13,49)=1$

$lcm(13,49)=7^2\cdot 13=637$

$a=13=13$

$b=49=7^2$

GCD is the product of the greatest prime powers that are found in BOTH factorizations. Hence, $gcd(13,49)=13\cdot 7^2=1$, since there are no common prime factors.

LCM is the product of the greatest prime powers found in either $a$ OR $b$. Hence, $lcm(13,49)=13\cdot 7^2=637$.

$gcd(55,125)=5$

$lcm(55,125)=5^3\cdot 11$

$a=55=5\cdot 11$

$b=125=5^3$

GCD is the product of the greatest prime powers that are found in BOTH factorizations. Hence, $gcd(55,125)=5$, since the only prime factor these numbers have in common is $5$.

LCM is the product of the greatest prime powers found in either $a$ OR $b$. Hence, $lcm(55,125)=5^3\cdot 11=1375$.

$gcd(120,30)=2\cdot 3\cdot 5= 30$

$lcm(120,30)=2^3\cdot 3\cdot 5=120$

$a=120=2^3\cdot 3\cdot 5$

$b=30=2\cdot 3\cdot 5$

GCD is the product of the greatest prime powers that are found in BOTH factorizations. Hence, $gcd(120,30)=2\cdot 3\cdot 5$.

LCM is the product of the greatest prime powers found in either $a$ OR $b$. Hence, $lcm(120,30)=2^3\cdot 3\cdot 5=120$.

Note that this sort of situation happens when $a|b$ or $b|a$.

$gcd(p_1^2\cdot p_2\cdot p_3^3\ ,\ p_1^3\cdot p_2^2\cdot p_4)=p_1^2\cdot p_2$

$lcm(p_1^2\cdot p_2\cdot p_3^3\ ,\ p_1^3\cdot p_2^2\cdot p_4)=p_1^3\cdot p_2^2\cdot p_3^3\cdot p_4$

GCD is the product of the greatest prime powers that are found in BOTH factorizations. We are already given the factorizations for $a$ and $b$. Hence, $gcd(p_1^2\cdot p_2\cdot p_3^3\ ,\ p_1^3\cdot p_2^2\cdot p_4)=p_1^2\cdot p_2$

LCM is the product of the greatest prime powers found in either $a$ OR $b$. Hence, $lcm(p_1^2\cdot p_2\cdot p_3^3\ ,\ p_1^3\cdot p_2^2\cdot p_4)=p_1^3\cdot p_2^2\cdot p_3^3\cdot p_4$

Previous Topic

Back to Lesson

Next Lesson