Greatest common factor (GCF) & Least common multiple (LCM)

Greatest common factor (GCF)

The greatest common factor (GCF) of a pair of numbers is the largest number that can be divided into both numbers. To find the greatest common factor of two numbers, find the factors of each, identify the factors that are shared, and select the greatest common factor among them. Note that the GCF considers all factors, not just prime factors.

Here’s a table showing the factors of 148 and 212.

The numbers 148 and 212 share the bolded factors: 1, 2, and 4. The greatest common factor (GCF) is the biggest number shared: 4.

There is no shortcut to finding the greatest common factor of any two numbers - you’ll always have to list all the factors (a.k.a. divisors) of the two numbers and determine the largest shared factor. Let’s try a question.

What is the greatest common factor of $x^2{y}^{3}z$ and $x^3{y}^2{z}^5$, given that $x$, $y$, and $z$ are all different prime numbers?

A. $xy{z}^4$
B. $x^6{y}^6{z}^5$
C. $x^5{y}^5{z}^6$
D. $x^2{y}^{2}z$
E. $xyz$

This question might seem difficult and unrelated to what we’ve just walked through, but it’s a great example of how every seemingly complicated GRE question can always be simplified to a core technique you’ve learned. Although we haven’t explicitly factored a variable number, the steps are the same as if you were given a normal integer.

Try solving this question on your own, and then keep reading for our explanation.

The GCF of $x^2{y}^{3}z$ and $x^3{y}^2{z}^5$ is their biggest shared factor, i.e. the biggest number that is part of both numbers.

We can see that both numbers have $x^2$ as a part of them; let’s pull this out:

• $x^2{y}^{3}z=x^2(y^{3}z)$
• $x^3{y}^2{z}^5=x^2(x{y}^2{z}^5)$

This means $x^2$ will be part of our GCF. Are there other common factors in the remaining parts of these numbers, $y^{3}z$ and $x{y}^2{z}^5$?

Yes, we can use the same logic to pull out the shared $y^2$:

• $y^{3}z=y^2(yz)$
• $x{y}^2{z}^5=y^2(x{z}^5)$

How about $z$, is that also a common factor? Yes, $z$ is also shared between the two:

• $yz=z(y)$
• $x{z}^5=z(x{z}^4)$

And now we’re left with $y$ and $x{z}^4$. The question told us that $x$, $y$, and $z$ are all different prime numbers, which means they have no more shared factors. To wrap things up, we just need to multiply together all the shared factors we’ve found ($x^2$, $y^2$, $z$) to get the greatest common factor (GCF).

$$\text{GCF}(x^2{y}^{3}z,x^3{y}^2{z}^5)=x^2{y}^{2}z$$

Least common multiple (LCM)

The least common multiple (LCM) of two numbers is essentially the opposite of the greatest common factor (GCF). Whereas the GCF is the greatest shared part of the two numbers, the LCM is the smallest number that is still a shared multiple of both. Finding the least common multiple can be useful when adding or subtracting fractions with different denominators.

To find the least common multiple of a set of numbers, you need to prime factor them, collect the greatest number of prime factors for each number in the prime factorization, and multiply them together. Here’s an example of finding the LCM of $9$ and $78$.

First, let’s prime factor these numbers:

• $9=3\ast 3$
• $78=2\ast 3\ast 13$

Next, let’s collect the greatest number of prime factors for each number in the prime factorization. This part sounds complicated but it’s straightforward. Instead of listing the original numbers, we’ll build the list from the prime factors:

• $2$ - One $2$ needed (zero 2s in 9, one 2 in 78)
• $3$ - Two $3$s needed (two 3s in 9, one 3 in 78)
• $13$ - One $13$ needed (zero 13s in 9, one 13 in 78)

And now we multiply them together:

$$\text{LCM}(9,78)=2\ast 3\ast 3\ast 13=234$$

Let’s see how this comes into play in a real question.

Solve for $x$.

$2/5+13/10+12/45=x/30$

You can use the LCM to help you solve this question. Give it some thought and try to answer it.

There are almost always multiple ways to solve a math equation. The “naive” approach to solving this question, which will indeed work, is to multiply all the bottom numbers so that you can add them up. However, this would mean we need to multiply by $5\ast 10\ast 45\ast 30=67500$, which is quite big and difficult to work with. You might have intuitively realized that we don’t need to go that high - and that’s the same concept of the LCM at play.

What’s the LCM of the denominators $5$, $10$, $30$, and $45$?

We can find it by prime factoring:

• $5=5$
• $10=2\ast 5$
• $30=2\ast 3\ast 5$
• $45=3\ast 3\ast 5$

Collecting the greatest quantity of each prime factor per number gives us the following:

• 1x $2$ (from 10 or 30)
• 2x $3$ (from 45)
• 1x $5$ (they all have one 5)

Multiplying these together gives:

$$\text{LCM}(5,10,30,45)=2\ast 3\ast 3\ast 5=90$$

If we make the denominators of each fraction $90$, we’ll be able to add them all up. We can do this by multiplying each part by $1/1$ scaled by the number that will result in $90$.

For instance, $90/5=18$, so we’ll multiply $2/5$ by $18/18$ to get $36/90$. The number $2/5$ is equal to $36/90$. We multiplied by $1$ in a different form ($18/18=1$), changing the representation of the number, but not the actual value.

$$\begin{array}{rl}2/5+13/10+12/45& =x/30\\ 2/5\ast (18/18)+13/10\ast (9/9)+12/45\ast (2/2)& =x/30\ast (3/3)\\ 36/90+117/90+24/90& =3x/90\\ 177/90& =3x/90\\ 177& =3x\\ 59& =x\end{array}$$

Although you can solve this specific question without using the LCM method, it’s important to understand how it works and to practice it. The GRE test writers craft questions that require these techniques; e.g. they might use numbers that are too large to be multiplied together naively with the calculator.