GCF and LCM: Number Theory You Use

Two Concepts That Unlock Fraction Arithmetic

Every time you add fractions, you need a common denominator. Every time you simplify a fraction, you need the greatest common factor. These two operations, finding the GCF and the LCM, underlie a huge portion of arithmetic, yet most people learn the procedures without understanding why they work. The Euclidean algorithm, one of the oldest algorithms in mathematics (documented around 300 BCE by Euclid), finds the GCF of two numbers using only subtraction and remainders. It reaches the correct answer in at most log steps, even for numbers with hundreds of digits.

This guide covers both the visual prime-factorization method and the Euclidean algorithm. You'll see exactly where GCF and LCM appear in real problems: simplifying 84/120, scheduling two events that repeat on different cycles, and cutting ribbon into equal pieces with no waste. The relationship GCF(a, b) × LCM(a, b) = a × b turns out to be the fastest path to the LCM once you have the GCF.

Neither concept requires a calculator for most everyday numbers, but both reward the effort of understanding rather than memorizing steps.

The Basics: GCF and LCM Defined

The Greatest Common Factor (GCF) of two numbers is the largest positive integer that divides both without a remainder. The GCF of 12 and 18 is 6, because 6 divides 12 (12/6 = 2) and divides 18 (18/6 = 3), and no number larger than 6 does both. Other names for GCF: greatest common divisor (GCD), highest common factor (HCF).

The Least Common Multiple (LCM) of two numbers is the smallest positive integer that both numbers divide into without a remainder. The LCM of 4 and 6 is 12, because 12 is the smallest number that 4 (12/4 = 3) and 6 (12/6 = 2) both divide evenly. The LCM of two numbers is always at least as large as the larger of the two numbers.

The key relationship: for any two positive integers a and b, GCF(a, b) × LCM(a, b) = a × b. For 4 and 6: GCF = 2, LCM = 12, and 2 × 12 = 24 = 4 × 6. Use this to find the LCM as soon as you have the GCF: LCM = (a × b) / GCF.

Three Methods for Finding GCF and LCM

Method 1: Prime Factorization. Break both numbers into their prime factors, then read off the GCF and LCM from the factor lists.

Find the GCF and LCM of 60 and 84.

• 60 = 2² × 3 × 5
• 84 = 2² × 3 × 7
• GCF = product of shared primes at their lowest exponent = 2² × 3 = 12
• LCM = product of all primes at their highest exponent = 2² × 3 × 5 × 7 = 420

Check: 12 × 420 = 5040 = 60 × 84. Confirmed.

Method 2: Euclidean Algorithm (fastest for large numbers). Divide the larger number by the smaller, take the remainder, and repeat until the remainder is 0. The last nonzero remainder is the GCF.

GCF of 252 and 105:

• 252 ÷ 105 = 2 remainder 42
• 105 ÷ 42 = 2 remainder 21
• 42 ÷ 21 = 2 remainder 0
• GCF = 21

Then LCM = (252 × 105) / 21 = 26460 / 21 = 1260. Three steps versus fully factoring both 252-digit numbers.

Method 3: Listing factors (works for small numbers). List all factors of each number, identify those that appear in both lists, and pick the largest. For 12 and 18: factors of 12 are 1, 2, 3, 4, 6, 12; factors of 18 are 1, 2, 3, 6, 9, 18. Common factors: 1, 2, 3, 6. GCF = 6. This method becomes impractical above ~100.

Common Misconceptions

• The GCF must be prime. The GCF can be any positive integer. GCF(24, 36) = 12, which factors into 2² × 3. It needs to be the largest number that divides both.
• LCM is always the product of the two numbers. 4 × 6 = 24, but LCM(4, 6) = 12. When two numbers share common factors, their LCM is smaller than their product by exactly the GCF.
• GCF and LCM only apply to two numbers at a time. Both extend to three or more numbers. GCF(12, 18, 24): factor each, take the lowest power of shared primes. 12 = 2²×3, 18 = 2×3², 24 = 2³×3. GCF = 2×3 = 6. LCM uses the highest powers: 2³×3² = 72.
• Consecutive integers always have a GCF of 1. Any two consecutive integers are coprime, their GCF is always 1. GCF(17, 18) = 1. This follows because any common factor would have to divide their difference, which is 1.