GCF and LCM calculator
Enter two positive integers to calculate their GCF and LCM.
- Greatest common factor (GCF)
- 6
- Least common multiple (LCM)
- 36
How GCF and LCM are calculated
The GCF is calculated with the Euclidean algorithm. The LCM is derived from the GCF by dividing the product of both numbers by their GCF.
The Euclidean algorithm repeatedly divides the larger number by the smaller one and replaces the larger with the remainder, until the remainder reaches 0; the last nonzero divisor is the GCF. It's the same method used by scientific calculators and computer algebra systems.
GCF(a, b) = GCF(b, a mod b), until the remainder is 0
In practice, the GCF is used to simplify fractions and to split items into equal groups with nothing left over (for example, splitting 12 pencils and 18 erasers into the largest possible number of identical bags). The LCM is used to sync periodic events, like finding when two buses that pass every 12 and 18 minutes will arrive together again.
LCM(a, b) = (a × b) ÷ GCF(a, b)
Worked example
GCF(12, 18) = 6 and LCM(12, 18) = 36. With the Euclidean algorithm: 18 = 1×12 + 6, then 12 = 2×6 + 0, so the GCF is 6.
Frequently asked questions
- What is the GCF?
- The greatest common factor (GCF) is the largest number that divides two or more numbers exactly.
- What is the LCM?
- The least common multiple (LCM) is the smallest number that is a multiple of two or more numbers at once.
- What are the GCF and LCM used for?
- They're used to simplify fractions (GCF) and to add or subtract fractions with different denominators (LCM), among other applications.
- Does this work with decimal numbers?
- No. The GCF and LCM are defined for positive whole numbers.
- How does the Euclidean algorithm work step by step?
- Divide the larger number by the smaller one and note the remainder; repeat the process with the divisor and that remainder, until the remainder is 0. The last divisor used is the GCF.
- Can the GCF of two numbers be larger than the smaller one?
- No, the GCF can never exceed the smaller of the two numbers, since it must divide it exactly.