Lesson 7: Greatest Common Divisor

Property

The greatest common factor or GCF of two whole numbers is the largest factor of both numbers. To find the GCF using prime factorization, multiply together all the prime factors that appear in the factorization of both numbers.

Examples

• To find the GCF of 20 and 30, list their factors. Factors of 20 are {1, 2, 4, 5, 10, 20} and factors of 30 are {1, 2, 3, 5, 6, 10, 15, 30}. The largest factor in both lists is 10.
• Find the GCF of 42 and 56 using prime factorization. We have $42 = 2 \times 3 \times 7$ and $56 = 2 \times 2 \times 2 \times 7$. The common factors are one 2 and one 7. So, the $\text{GCF} = 2 \times 7 = 14$.
• Let's find the GCF of 18 and 45. The prime factorizations are $18 = 2 \times 3 \times 3$ and $45 = 3 \times 3 \times 5$. The common prime factors are two 3s. Therefore, the $\text{GCF} = 3 \times 3 = 9$.

Explanation

The GCF is the largest number that divides into two or more numbers without leaving a remainder. It's like finding the biggest identical group you can make from different sets of items. This is very useful for simplifying fractions.

Property

Two integers $a$ and $b$ are relatively prime (or coprime) if and only if $\gcd(a, b) = 1$. When numbers are relatively prime, their least common multiple equals their product:

Examples

Property

For positive integers $a$, $b$, and $n$:

Examples