The short answer
The Euclidean algorithm finds the GCF of two numbers by repeated division: divide the larger by the smaller, replace the larger with the remainder, and repeat until the remainder hits 0 — the last nonzero remainder is the GCF. For 48 and 18: 48÷18 leaves remainder 12, 18÷12 leaves remainder 6, 12÷6 leaves remainder 0, so the GCF is 6. This finds the answer in a handful of steps, even for very large numbers, without ever listing every factor.
Key takeaways
- The Euclidean algorithm finds a GCF in a small number of steps no matter how large the numbers are — no need to list every factor first.
- For any two numbers, GCF × LCM equals the product of the two numbers — a quick way to sanity-check one result once you have the other.
- Both GCF and LCM extend to three or more numbers by combining them two at a time, not by applying a formula to all of them at once.
- GCF and HCF (highest common factor) name the same value — the difference is regional terminology, not mathematics.
The Euclidean algorithm step by step
| Step | Division | Remainder |
|---|---|---|
| 1 | 48 ÷ 18 = 2 | 12 |
| 2 | 18 ÷ 12 = 1 | 6 |
| 3 | 12 ÷ 6 = 2 | 0 (stop) |
The last nonzero remainder — 6 — is the GCF. Each step replaces the pair of numbers with a smaller pair that shares the same GCF, so the algorithm always converges quickly, typically in far fewer steps than either number's size would suggest.
The GCF-LCM relationship
GCF(a, b) × LCM(a, b) = a × b
Once you know the GCF of two numbers, you can find the LCM without a separate calculation: LCM = (a × b) ÷ GCF. This shortcut only applies to exactly two numbers — for three or more, GCF and LCM each need to be built up by combining numbers two at a time.
Worked example: GCF and LCM of 48 and 18
GCF(48, 18) = 6 (from the Euclidean algorithm above)
LCM(48, 18) = (48 × 18) ÷ 6 = 864 ÷ 6 = 144
Both answers can be double-checked with prime factorization: 48 = 2⁴ × 3 and 18 = 2 × 3². The GCF takes the lowest power of each shared prime (2¹ × 3¹ = 6), while the LCM takes the highest power of every prime involved (2⁴ × 3² = 144) — matching the Euclidean and formula-based results exactly.
Common mistakes to avoid
- Applying the Euclidean algorithm to three or more numbers directly — instead, find GCF(a, b) first, then find GCF of that result with c, and so on.
- Assuming GCF × LCM = a × b extends to three or more numbers — that identity is only guaranteed for exactly two.
- Mixing up which one a word problem actually needs — GCF is for splitting into equal groups, LCM is for finding when repeating events line up.
- Stopping the Euclidean algorithm early because a remainder looks "small enough" — keep dividing until the remainder is exactly 0.
Related calculators
- Least Common Multiple Calculator — get a dedicated LCM tool with its own step-by-step method.
- Common Factor Calculator — see every shared factor, not just the greatest one.
- Factor Calculator — list every factor of a single number.
- Fraction Calculator — put the GCF to work simplifying a fraction directly.