Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 38 · Getting Started

Greatest Common Factor and Least Common Multiple

Find the greatest common factor (GCF) and least common multiple (LCM) by listing, by prime factors and with Euclid's method, with runnable code.

Two numbers often share factors and multiples. The greatest common factor (GCF, also called the greatest common divisor, GCD or HCF) is the largest number that divides both. The least common multiple (LCM) is the smallest positive number that both divide into. You will use the GCF to simplify fractions and the LCM to add them.

Greatest common factor

Take 18 and 24.

  • Factors of 18: 1, 2, 3, 6, 9, 18
  • Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

The common factors are 1, 2, 3, 6. The largest is 6, so GCF(18, 24) = 6.

A real-life use: you have 18 red and 24 blue beads and want identical bags with nothing left over. The largest number of bags is the GCF, 6, each holding 3 red and 4 blue beads.

Least common multiple

  • Multiples of 4: 4, 8, 12, 16, 20, 24, ...
  • Multiples of 6: 6, 12, 18, 24, ...

The common multiples are 12, 24, 36, .... The smallest is 12, so LCM(4, 6) = 12. Use: one bus leaves every 4 minutes and another every 6; if both leave together now, they leave together again after 12 minutes.

Using prime factorizations

Listing gets slow for big numbers. Prime factorization is faster:

  • GCF: multiply the primes the numbers have in common, using the smaller power of each.
  • LCM: multiply every prime that appears, using the larger power of each.

Example: 36 = 2² × 3² and 48 = 2⁴ × 3.

  • GCF: smaller powers: 2² × 3¹ = 4 × 3 = 12.
  • LCM: larger powers: 2⁴ × 3² = 16 × 9 = 144.

Check the relationship: GCF × LCM = 12 × 144 = 1,728 = 36 × 48. For any two positive whole numbers, GCF × LCM = product of the numbers. This gives a quick way to find the LCM once you know the GCF: LCM = (a × b) / GCF.

Python GCF and LCM by listing

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Euclid's algorithm

More than 2,000 years ago, Euclid noticed that the GCF of two numbers does not change if you replace the larger number by its remainder when divided by the smaller. Repeat until the remainder is zero; the last non-zero number is the GCF.

Example: GCF(252, 105).

  1. 252 ÷ 105 = 2 remainder 42
  2. 105 ÷ 42 = 2 remainder 21
  3. 42 ÷ 21 = 2 remainder 0

The last non-zero remainder is 21, so GCF(252, 105) = 21.

Python Euclid's algorithm with steps shown

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Simplifying a fraction with the GCF

A fraction is in simplest form when the top and bottom share no factor except 1. To simplify, divide both by their GCF.

18/24: the GCF is 6, so 18/24 = (18 ÷ 6)/(24 ÷ 6) = 3/4.

Dividing top and bottom by the same non-zero number does not change the value of the fraction. That is why 18/24 and 3/4 are called equivalent fractions.

Python Simplify fractions

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here the standard library function gcd does the same job as our own Euclid code. Writing it yourself first shows you what the library does.

Do not confuse the two ideas. The GCF is never larger than the smaller number; the LCM is never smaller than the larger number.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the GCF of 30 and 45?

    30 = 2×3×5 and 45 = 3×3×5. The shared primes are 3 and 5, so the GCF is 3 × 5 = 15.
  2. 2. What is the LCM of 6 and 8?

    Multiples of 8: 8, 16, 24. The number 24 is the first that 6 also divides into. Equivalent check: (6×8)/GCF = 48/2 = 24.
  3. 3. Simplify 42/56.

    GCF(42, 56) = 14. Dividing top and bottom by 14 gives 3/4. The other options are equivalent but not in simplest form.
  4. 4. Two lights blink every 9 s and every 12 s and start together. After how many seconds do they blink together again?

    That is LCM(9, 12). 9 = 3² and 12 = 2² × 3, so the LCM is 2² × 3² = 36.

Summary

  • GCF: the largest number that divides both; LCM: the smallest positive number both divide into.
  • With prime factors, take the smaller powers for the GCF and the larger powers for the LCM.
  • GCF × LCM = a × b for two positive whole numbers.
  • Euclid's algorithm finds the GCF by repeated remainders.
  • Divide top and bottom by the GCF to simplify a fraction.

Next: Expressions and Operations