5.2: Greatest Common Factors and Least Common Multiples

Last updated
Save as PDF

Page ID: 185694

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\dsum}{\displaystyle\sum\limits} $

$ \newcommand{\dint}{\displaystyle\int\limits} $

$ \newcommand{\dlim}{\displaystyle\lim\limits} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$\newcommand{\longvect}{\overrightarrow}$

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Consider the following scenarios for the Wonder, Play, Grow. These concrete situations help us think about the content for this section.

Wonder, Play, Grow

Pick One! Problem Solve with some of your peers.

Scenario 1: Two buses stop at the same bus station—one every 12 minutes, another every 15 minutes. If they both arrive at the station at noon, when will they next arrive together?
Scenario 2: You’re tiling a rectangular floor that’s 8 feet by 12 feet with square tiles. What’s the largest size square tile you can use without cutting any tiles?

🧠Let's Listen to Learn❤️

Greatest Common Factor (GCF)

Knowing how to find the GCF is not just a procedural skill; it fosters a deeper understanding of number relationships, provides essential tools for working with fractions, and lays crucial groundwork for future algebraic concepts. As a future elementary school teacher, understanding the significance of the GCF will enable you to teach it more effectively, emphasizing the underlying concepts and its practical applications (Feike, Schwingendorf, and Gregg, 2018).

Definition: Greatest Common Factor

The Greatest Common Factor is the largest whole number that divides evenly two or more nonzero whole numbers. The greatest common factor of a and b will be denoted by GCF(a,b).

Note: By definition, GCF(a, a) = a.

Three ways for finding GCF(a,b) are presented. The first one uses sets, the second one uses prime factorizations, and the third one uses the division algorithm.

Set Intersection Method

In this method we list all of the factors of each number, then list the common factors and choose the largest one.

Example $\PageIndex{1}$

Find the GCF of 54 and 60, GCF(54, 60).

Answer

Step 1: List all the Factors, starting with 2

54 → 2, 3, 6, 9, 18, 27, 54

60 → 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Step 2: Circle the Common factors

$clipboard_e33ba049a7c99d1ff15aecbdf03a224b8.png$

Step 3: Choose the Greatest circled pair

Answer: GCF (54, 60) = 6

Prime Factorization Method

In this method we list the prime factors, then multiply the common prime factors.

Example $\PageIndex{2}$

Find the GCF of 54 and 60, GCF(54, 60).

Answer

Step 1: Find the Prime Factorization

60 → 2 x 2 x 3 x 5 = 2² x 3 x 5

54 → 2 x 3 x 3 x 3 = 2 x 3³

Step 2: Find the common prime factors

Notice that the prime factorizations of 36 and 54 both have one 2 and two 3s in common. So, we simply multiply these common prime factors to find the greatest common factor.

Step 3: Multiply the common prime factors

That is, GCF(54, 60) = 2 x 3 = 6

Wonder, Play, Grow

Task 1: Work with your peers to find the Greatest Common Factor (GCF). Be sure to try both approaches.

40 and 90
75 and 25
168 and 85
90, 120, and 150

Task 2: Let's start to think about another way to find the GCF. Can you think of any? 🤔

We will let math educator Dr. Howie Hua explain another method in this video called the Euclidean Algorithm.

https://youtu.be/rOnw1CJZBaI?si=yxa_nnk_FUsa0tQl

What do you think? We will try it in the example below.

The Euclidean Algorithm

In order to apply the Euclidean Algorithm we need the results of the following theorem. Thus, to find the GCF of any two numbers, this theorem can be applied repeatedly until a remainder of zero is obtained. The final divisor that leads to the zero remainder is the GCF of the two numbers. This is Dr. Howie Hua does in his video, without writing it out in this format.

Theorem $\PageIndex{1}$

If a and b are whole numbers with a ≥ b and a = bq + r, where r < b, then GCF(a, b) = GCF(r, b).

How to use the Euclidean Algorithm to find the greatest common factor of two numbers:

Write the GCF of the two numbers in parentheses (remember the order of the numbers is irrelevant). The smaller of the two numbers will be one of the numbers in the next parentheses. To get the other number, divide the larger number by the smaller number, and put the remainder in parentheses. If the the smaller number is a factor of the larger number, that means it will divide evenly, so there will be no remainder. That means the remainder is 0. Remember to put the remainder in the parentheses, not the quotient! If one of the new numbers in the parentheses is zero, the other number is the GCF; if one the new numbers is 1, 1 is the GCF. Otherwise, repeat the process until one of the two numbers is 0 or 1. An example is shown below.

Example $\PageIndex{3}$

GCF(546, 390)	= GCF(390, 156)	(390 is smaller than 546, $546 \div 390$ = 1 r 156)
	= GCF(156, 78)	(156 is smaller than 390, $390 \div 156$ = 2 r 78)
	= GCF(78, 0)	(78 is smaller than 156, $156 \div 78$ = 2 r 0)
	= 78	Put the remainder (0), NOT 2, in the parentheses!
		78 is the GCF(78, 78); The answer is a number!

Check: First, make sure 78 is a factor of 546 and 390: $546 = 78 \cdot 7$ and $390 = 78 \cdot 5$. Second, check to make sure the other factors of each (7 and 5) are relatively prime. If so, then 78 is not only a factor of 546 and 390, but is in fact the greatest common factor of each since they have no other common factors (because 7 and 5 have no common factors

CAUTION: THE MOST COMMON MISTAKE PEOPLE MAKE WHEN USING THE EUCLIDEAN ALGORITHM IS ON THE LAST STEP, WHEN THE SMALLER NUMBER DIVIDES EVENLY INTO THE LARGER NUMBER, WHICH MEANS THE REMAINDER IS ZERO. IT DOESN'T MATTER WHAT THE QUOTIENT IS – IT'S THE REMAINDER THAT MATTERS – 0 GOES IN THE PARENTHESES!!! Also, zero is not a factor of any number except zero, so the GCF can't be zero. On the other hand, every number is a factor of zero. So, when zero is one of the numbers in parentheses, the other number is the GCF. REMEMBER TO ALWAYS CHECK YOUR Answer!!!

One More Method - Just For Fun 😄😊🥳✨

Since every common factor of a and b is also a common factor of b and a − b, the pairs (a, b) and (a − b, b) have the same common factors. So GCF(a, b) and GCF(a − b, b) must also be the same.

Theorem $\PageIndex{2}$

If a and b are whole numbers, with a ≥ b, then GCF(a, b) = GCF(a − b, b).

Let's see what you think about this method.

Example $\PageIndex{4}$

Find the GCF(546, 390).

Answer: GCF(546, 390) = GCF(390, 156) = GCF(234, 156) = GCF(156, 78) = GCF(78, 78) = 78

Think About and Discuss

Consider all of the ways in which we can find the GCF. When would you use one method over the others? Discuss with your peers before trying the following two problems.

Decide on a method for each before finding the GCF.

i) GCF(24, 42)

ii) GCF (504, 600)

iii) GCF(30, 48, 144)

Math Fact

If two numbers have no factors in common, they are called relatively prime. In other words, if GCF(a, b) = 1, then a and b are relatively prime. The numbers, a and b, might both be prime, both be composite, or one might be prime and the other composite.

4 and 15 are relatively prime, although neither is prime. Can you think of others?

Least Common Multiples

Just as with the procedures for finding the GCF, the concept of the Least Common Multiple (LCM) is about understanding fundamental number relationships, gaining essential skills for working with fractions, and building a crucial foundation for future mathematical studies, including algebra (Feike et al., 2018). As a future elementary teacher, being able to explain the "why" behind the LCM and its applications will empower your students to see mathematics as a connected and meaningful subject. In Scenario 1 of the Wonder, Play, Grow activity we saw a concrete example where finding the LCM can help you solve a real world problem. Now we will take a look at the procedures for finding the LCM.

Definition: Multiples

When a whole number is multiplied by other whole numbers, with the exception of Multiples zero, the resulting products are called multiples of the given whole number.


Multiples of 2	Multiples of 3	Multiples of 8	Multiples of 10
2·1=2	3·1=3	8·1=8	10·1=10
2·2=4	3·2=6	8·2=16	10·2=20
2·3=6	3·3=9	8·3=24	10·3=30
2·4=8	3·4=12	8·4=32	10·4=40
2·5=10	3·5=15	8·5=40	10·5=50
…	…	…	…

Common Multiples

There will be times when we are given two or more whole numbers and we will need to know if there are any multiples that are common to each of them. If there are, we will need to know what they are. For example, some of the multiples that are common to 2 and 3 are 6, 12, and 18. We can visualize common multiples using the number line.
Notice that the common multiples can be divided by both whole numbers.

$A horizontal line numbered from zero to eighteen. Multiples of two and three are marked with dark circles, and are connected through arcs. Six, twelve and eighteen are labeled as$

The Least Common Multiple (LCM)

Notice that in our number line visualization of common multiples (above) the first common multiple is also the smallest, or least common multiple, abbreviated by LCM.

As with the GCFs, there are multiple ways for finding LCM(a,b): we will start with the set intersection method and the prime factorization method.

Definition: Least Common Multiple (LCM)

The least common multiple of a and b, denoted by LCM(a,b), is the smallest nonzero whole number that is a multiple of both a and b.

Set Intersection Method - In this method list the nonzero multiples of each number until a first common multiple appears. This number is the LCM(a,b).

Example $\PageIndex{5}$

Find the LCM of 54 and 30

Solution

Step 1: List the Multiples

54 → 54, 108, 162, 216, 270, 324,…

30 → 30, 60, 90, 120, 150, 180, 210, 240, 270, 300,…

Step 2: Circle the Common multiple(s)

Step 3: Choose the Least common multiple = 270

Prime Factorization Method - To find the LCM using this method we first find the prime factorization of each number. Then take each of the primes that are factors of either of the given numbers. The LCM is the product of these primes, each raised to the greatest power of the prime that occurs in either of the prime factorizations

STEPS:

Write the prime factorization of each number, using exponents on repeated factors.
Write each base that appears in each of the prime factorizations.
To each base, attach the largest exponent that appears on it in the prime factorizations.
The LCM is the product of the numbers found in step 3.

Example $\PageIndex{6}$

Find the LCM(9,12).

Step 1: 9 = 3 · 3 = $3^2$
12 = 2 · 6 = 2 · 2 · 3 = $2^2$ · 3

Step 2: The bases that appear in the prime factorizations are 2 and 3.

Step 3: The largest exponents appearing on 2 and 3 in the prime factorizations are, respectively, 2 and 2 (or 2² from 12, and 3² from 9).

Step 4: The LCM is the product of these numbers. LCM =2² · 3² =4 · 9=36

Thus, 36 is the smallest number that both 9 and 12 divide into without remainders.

Example $\PageIndex{7}$

Find the LCM(90,630).

Answer

Step 1: 90 = 2 · 45 = 2 · 3 · 15 = 2 · 3 · 3 · 5 = 2 · $3^2$ · 5
630 = 2 · 315 = 2 · 3 · 205 = 2 · 3 · 3 · 35 = 2 · 3 · 3 · 5 · 7 = 2 · $3^2$ · 5 · 7

Step 2: The bases that appear in the prime factorizations are 2, 3, 5, and 7.

Step 3: The largest exponents that appear on 2, 3, 5, and 7 are, respectively, 1, 2, 1, and 1.

$2^1$ from either 90 or 630
$3^2$ from either 90 or 630
$5^1$ from either 90 or 630
$7^1$ from 630

Step 4: The LCM is the product of these numbers. LCM =2 · 3² · 5 · 7 = 2 · 9 · 5 · 7 = 630

Thus, 630 is the smallest number that both 90 and 630 divide into with no remainders.

Wonder, Play, Grow

A visual way to see the LCM and GCF of two numbers is with a Venn-diagram. Below is a Venn-diagram containing the factors of 45 and 60. Take a look at the visual as see how we can use it to determine the LCM(45, 60) and GCF(45, 60).

45 = 3 x 3 x 5 = 3² x 5

60 = 2 x 2 x 3 x 5 = 2² x 3 x 5

$A Venn diagram showing the prime factorizations of 45 and 60. The left circle is labeled "factors of 45" and contains the factor 3. The right circle is labeled "factors of 60" and contains 2 2 2 2 . The overlapping section between the two circles contains the common prime factors 3 ⋅ 5 3⋅5. An arrow points to the intersection, labeled "common factors.$

Work with peers to find the LCM(45, 60) and GCF(45, 60) using the Venn-diagram. Once you see how it works, make your own diagram to find the following: LCM(24, 54) and GCF(24, 54).

🧠Let's Listen to Learn❤️

Some Cool Number Theory

The "coolness" of number theory stems from its blend of accessible yet challenging problems, its rich historical and even mystical past, the surprising patterns it unveils, and its unexpected importance in the modern world (Devlin, 2012). It demonstrates that even seemingly simple questions about numbers can lead to profound and fascinating mathematical inquiries. Here are some things related to what we are learning.

After inspiring your students, some of them ask you the following questions, what do you say?

How are GCF and LCM related?

Theorem $\PageIndex{3}$

Let a and b be any two whole numbers. Then GCF(a, b) x LCM(a, b) = ab.

How many primes numbers are there?

Theorem $\PageIndex{4}$

There is an infinite number of primes.

Is there is a way to predict how many factors a number has?

Theorem $\PageIndex{5}$

Suppose that a counting number n is expressed as a product of distinct primes with their respective exponents, say n = (p1ⁿ¹)(p2ⁿ²)...(pm^nm). Then the number of factors of n is the product (n1+1)(n2+1)....(nm+1).

eg. The number 12 = 2 x 2 x 3 = (2²)(3¹), so the number of factors 12 has is (2+1)(1+1) = 6 factors. We know that 1, 2, 3, 4, 6, and 12 are factors of 12, so it confirms the theorem.

Example $\PageIndex{8}$

Find the number of factors for 144.

Answer: 144 = 2⁴ x 3². So, the number of factors of 144 is (4 + 1)(2 + 1) = 15.

Are there any other cool ways to find the GCF and LCM? Dr. Howie Hua may have an answer.

https://youtu.be/Js5ATEh-498?si=QKQTt1CzofObitS1

Search

Text Color

Text Size

Margin Size

Font Type

Definition: Greatest Common Factor

Example \(\PageIndex{1}\)

Example \(\PageIndex{2}\)

Theorem \(\PageIndex{1}\)

Example \(\PageIndex{3}\)

Theorem \(\PageIndex{2}\)

Example \(\PageIndex{4}\)

Think About and Discuss

Math Fact

Least Common Multiples

Definition: Multiples

Common Multiples

$A horizontal line numbered from zero to eighteen. Multiples of two and three are marked with dark circles, and are connected through arcs. Six, twelve and eighteen are labeled as$

The Least Common Multiple (LCM)

Definition: Least Common Multiple (LCM)

Example \(\PageIndex{5}\)

Example \(\PageIndex{6}\)

Example \(\PageIndex{7}\)

Some Cool Number Theory

Theorem \(\PageIndex{3}\)

Theorem \(\PageIndex{4}\)

Theorem \(\PageIndex{5}\)

Example \(\PageIndex{8}\)

GCF(546, 390)	= GCF(390, 156)	(390 is smaller than 546, \(546 \div 390\) = 1 r 156)
	= GCF(156, 78)	(156 is smaller than 390, \(390 \div 156\) = 2 r 78)
	= GCF(78, 0)	(78 is smaller than 156, \(156 \div 78\) = 2 r 0)
	= 78	Put the remainder (0), NOT 2, in the parentheses!
		78 is the GCF(78, 78); The answer is a number!