Common factors and common multiples
Factors divide a number evenly; multiples are what you get by multiplying it. Every pair of whole numbers shares at least the factor 1 and the multiple a × b, so the useful answers are the largest shared factor and the smallest shared multiple. Fractions, gear ratios, tiling, scheduling and splitting groups evenly all reduce to one or the other.
The methods
Euclid: GCF(a, b) = GCF(b, a mod b), GCF(a, 0) = a Two numbers: LCM(a, b) = a × b / GCF(a, b) More numbers: GCF(a, b, c) = GCF(GCF(a, b), c), same for LCM Primes: GCF = Π p^min(e), LCM = Π p^max(e)
Worked example
12, 18 and 30. 12 = 2² × 3, 18 = 2 × 3², 30 = 2 × 3 × 5.
GCF: primes common to all three are 2 and 3, each to its lowest power → 2 × 3 = 6. LCM: every prime to its highest power → 2² × 3² × 5 = 180.
Euclid for 18 and 12: 18 mod 12 = 6, 12 mod 6 = 0, so GCF(18, 12) = 6; then GCF(6, 30) = 6.
Notes
- Numbers up to 1,000,000,000,000 are accepted; results larger than 2⁵³ (about 9 × 10¹⁵) are flagged as approximate.
- Two numbers with GCF 1 are called relatively prime (coprime), even if neither is prime: 8 and 9.
Sources: OpenStax, Prealgebra 2e, §2.5 Prime Factorization and the Least Common Multiple; Euclid, Elements, Book VII, Proposition 2.
Frequently asked questions
What is the difference between GCF and LCM?
The greatest common factor (GCF, also called GCD or HCF) is the largest number that divides all of your numbers. The least common multiple (LCM) is the smallest number that all of them divide into. For 12 and 18, GCF = 6 and LCM = 36.
When do I use the GCF and when the LCM?
Use the GCF to simplify — reducing 12/18 to 2/3, or cutting two boards into the longest equal pieces with no waste. Use the LCM to synchronize — the least common denominator for adding fractions, or when two repeating events next happen on the same day.
How do I find the GCF and LCM from prime factorizations?
Write each number as a product of primes. The GCF multiplies each prime that appears in every number, using its smallest exponent. The LCM multiplies every prime that appears in any number, using its largest exponent. 12 = 2²·3 and 18 = 2·3²: GCF = 2·3 = 6, LCM = 2²·3² = 36.
Is there a shortcut for two numbers?
Yes: GCF(a, b) × LCM(a, b) = a × b. Once you have the GCF (for example with the Euclidean algorithm), LCM = a × b / GCF. For 12 and 18: 216 / 6 = 36. This identity does not hold for three or more numbers.