Summary
The Greatest Common Factor (GCF) of two or more integers is the largest positive integer that divides each of them without a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of each of them. These two concepts are fundamental in simplifying fractions, finding common denominators, and solving problems in number theory.
How it works
There are two main approaches:
- Euclidean algorithm — the most efficient method for finding GCF. It repeatedly divides the larger number by the smaller and takes the remainder until the remainder is zero. The last non-zero remainder is the GCF.
- Prime factorization — factor each number into primes. The GCF is the product of all shared prime factors (taken at their lowest power). The LCM is the product of all prime factors (taken at their highest power).
Once you have the GCF, you can find the LCM using the relationship between them.
The formulas
Where
Where
Worked examples
GCF of 48 and 18 using the Euclidean algorithm
Divide 48 by 18
= remainder 12
Divide 18 by 12
= remainder 6
Divide 12 by 6
= remainder 0 -- stop
Result
GCF(48, 18) = 6
LCM of 48 and 18
Use GCF from above
= 6
Apply the LCM formula
= 144
Result
LCM(48, 18) = 144
Prime factorization method for GCF and LCM of 60 and 90
Factor 60
= 2^2 * 3 * 5
Factor 90
= 2 * 3^2 * 5
GCF: take minimum powers of shared primes
= 30
LCM: take maximum powers of all primes
= 180
Result
GCF(60, 90) = 30, LCM(60, 90) = 180
Practical uses
- Simplifying fractions — divide numerator and denominator by their GCF to reduce a fraction to lowest terms (e.g., 48/18 becomes 8/3).
- Adding fractions — the LCM of the denominators gives the least common denominator, making addition straightforward.
- Scheduling — if event A repeats every 12 days and event B every 18 days, they next coincide in LCM(12, 18) = 36 days.
- Tiling and measurement — the GCF determines the largest square tile that evenly covers a rectangular floor.
Assumptions & limitations
- Positive integers only — GCF and LCM are defined for positive integers. The calculator takes absolute values of any negative inputs.
- GCF of zero — GCF(a, 0) = a by convention, since every integer divides 0. LCM(a, 0) = 0 since 0 is a multiple of everything.
- More than two numbers — the Euclidean algorithm extends naturally: GCF(a, b, c) = GCF(GCF(a, b), c), and similarly for LCM.