The Euclidean algorithm finds the greatest common divisor (GCD) of two numbers with repeated division, without factoring. For 462/1071, three divisions are enough: the GCD is 21 and the fraction becomes 22/51. If you only want the result, the greatest common divisor calculator gives it instantly; this guide explains the method by hand and why it always ends at the GCD.
The idea fits in one sentence: the GCD of two numbers does not change if you replace the larger one with the remainder of dividing it by the smaller one. Repeat until the remainder is 0, and the last divisor used is the GCD.
Each line follows dividend = quotient × divisor + remainder, with the remainder smaller than the divisor. Only the divisor and the remainder carry over to the next line, not the quotient. The cross-multiplication in the check is the same one used to compare fractions, and dividing both terms by the same number is what separates simplifying from scaling up, as explained in equivalent fractions.
Why the remainder is enough
If a = q × b + r, any number that divides both a and b also divides r, because r = a − q × b. And the other way around: whatever divides both b and r also divides a. So the pairs (a, b) and (b, r) have the same common divisors, and the largest of them is the same. That is why GCD(a, b) = GCD(b, r). Since each remainder is smaller than the one before, the chain shrinks until it reaches 0.
The same idea shows up with squares. The 1071 by 462 rectangle is covered by two squares of side 462; in the strip left over, three squares of side 147 fit, and in the final strip, seven squares of side 21. The smallest square that fills everything with no gaps has side 21, the GCD.
Worked example: simplify 462/1071
You want to reduce 462/1071 to lowest terms, and you cannot spot a common divisor at a glance.
- Divide the larger number by the smaller. 1071 = 2 × 462 + 147.
- Move to the divisor and remainder pair. Now they are 462 and 147: 462 = 3 × 147 + 21.
- Repeat with the new pair. They are 147 and 21: 147 = 7 × 21 + 0. The remainder is 0, so the chain ends.
- Take the last divisor. The GCD is 21.
- Divide the numerator and denominator by 21. 462 ÷ 21 = 22 and 1071 ÷ 21 = 51.
Result: 462/1071 = 22/51.
Check: cross-multiplying, 462 × 51 = 23,562 and 1071 × 22 = 23,562, so they are equal. Also, 22 = 2 × 11 and 51 = 3 × 17 share no factors.
A second example, with five divisions
For 3600/4284, start with the larger number, 4284. The chain is:
- 4284 = 1 × 3600 + 684
- 3600 = 5 × 684 + 180
- 684 = 3 × 180 + 144
- 180 = 1 × 144 + 36
- 144 = 4 × 36 + 0
The GCD is 36, and 3600 ÷ 36 = 100 with 4284 ÷ 36 = 119, so the fraction becomes 100/119. If you start with the smaller number, the first division has quotient 0 and only swaps the pair; the result is the same, with one extra step.
Euclid or prime factors
There are two ways to find a GCD, and each one wins in a different situation.
| Method | What you do | Result | When it fits |
|---|---|---|---|
| Euclid | Divide with remainder until you reach 0 | 5 divisions, GCD 36 | Large numbers, or when you only need the GCD |
| Prime factors | Factor both and take the common ones with the smallest exponent | 2² × 3² = 36 | Small numbers, or when you also want the LCM |
With 4284 = 2² × 3² × 7 × 17 and 3600 = 2⁴ × 3² × 5², factoring means finding every prime, and one large factor makes the search longer. Euclid never looks for them. If you need the LCM as well as the GCD, prime factorization gives it directly, and the guide on the difference between GCD and LCM explains when to use each. The divisibility rules save steps when the common divisor is obvious.
A mistake that looks like an answer
The most common slip is carrying the quotient instead of the remainder, and it produces a GCD that looks reasonable.
A similar slip is stopping at a small remainder instead of waiting for 0: the GCD is the last divisor, not the first remainder that looks easy to handle. And to simplify, you must divide both terms by the GCD, not just one, or the value changes.
When to use it and where to go next
Euclid works with two integers at a time and returns only the GCD. For small fractions, such as 6/8, spotting the 2 by eye is faster. To practice with any fraction, the simplify fractions tool applies the GCD and gives the lowest-terms form. If you are curious about other ways to write a fraction, the guide on continued and Egyptian fractions uses these same divisions: the quotients in the chain are the terms of the continued fraction.