The Euclidean algorithm finds the greatest common divisor because replacing two numbers with the smaller number and their remainder keeps exactly the same common divisors. Each nonzero remainder gets smaller, so the process must stop. The divisor in the step that produces remainder zero is the GCD.
That answer has two parts: the method preserves what we’re looking for, and it eventually reaches an easy stopping point. Both parts matter. A method that keeps the right answer but never finishes wouldn’t help you complete a calculation.
This lesson builds the proof from ordinary division and checks it with 252 and 198. You don’t need to list their prime factors first. For related integer tools and lessons, visit the number theory and systems hub.
What Does The Division Step Mean?
One step divides the larger positive integer by the smaller one and records the remainder. Write this as a = bq + r, where a is the larger number, b is the smaller number, q counts whole groups, and r is what’s left. The remainder satisfies 0 ≤ r < b.
For example, 252 = 198 × 1 + 54. One whole group of 198 fits into 252, with 54 left over. The remainder is less than 198 because another whole group cannot fit.
The next step uses 198 and 54 instead of 252 and 198. Then you divide again and continue with the new pair. In each pair, the smaller number becomes the next number to divide, while the remainder becomes the next divisor.
Here, divisor has two related uses that can cause confusion. The divisor in a division step is the number you’re dividing by; a common divisor is a positive integer that divides both numbers exactly. The proof asks which common divisors survive when the pair changes.
Barrus and Clark’s Euclidean algorithm lesson on Mathematics LibreTexts presents this remainder process and its GCD rule. The key identity is gcd(a, b) = gcd(b, r). The explanation below shows why both sides have the same possible common divisors.
Why Do The Common Divisors Stay The Same?
Every common divisor of a and b also divides r, and every common divisor of b and r also divides a. Those two directions show that no common divisor disappears or joins the list. Since the lists match, their greatest members match too.
Start with a positive integer d that divides both a and b exactly. Since d divides b, it also divides bq, which is just q whole copies of b. Subtracting bq from a leaves r, so d divides r exactly.
We can spell that out with whole numbers. If a = dm and b = dn, then r = a − bq = d(m − nq). The quantity in parentheses is an integer, so r is a whole multiple of d.
Try a candidate divisor of 9 in the first example. Both 252 and 198 are multiples of 9, so their difference, 54, must be one too. A candidate such as 7 fails because it doesn’t divide 198, even though it divides 252.
Now reverse the direction: suppose d divides b and r. Write b = dn and r = dk. The original division equation gives a = bq + r = d(nq + k), so d also divides a.
Why do we need the reverse direction? Showing that old common divisors survive doesn’t rule out a new, larger common divisor appearing. The reverse check proves that anything dividing the new pair already divided the old pair.
How Does The Proof Work For 252 And 198?
For 252 and 198, repeated division gives remainders 54, 36, 18, and 0. Each new pair has the same common divisors as the pair before it. That lets us carry the original GCD through the calculation without finding every factor of either starting number.
| Division equation | Next pair |
|---|---|
| 252 = 198 × 1 + 54 | 198, 54 |
| 198 = 54 × 3 + 36 | 54, 36 |
| 54 = 36 × 1 + 18 | 36, 18 |
| 36 = 18 × 2 + 0 | 18, 0 |
The first change can be checked without letters. Any number that divides 252 and 198 also divides their difference, 54. Any number that divides 198 and 54 also divides their sum, 252.
The next change uses subtraction of three copies: 198 − 3 × 54 = 36. A common divisor of 198 and 54 divides that remainder. Going backward uses addition: 3 × 54 + 36 = 198.
The GCD therefore stays equal through this chain: gcd(252, 198) = gcd(198, 54) = gcd(54, 36) = gcd(36, 18) = gcd(18, 0). At the end, the answer is 18. The smaller numbers made the problem easier without changing its answer.
You can verify that 18 divides the starting numbers: 252 = 18 × 14 and 198 = 18 × 11. That checks that 18 is a common divisor. The proof of preservation and the stopping rule explain why it’s the greatest one.
Why Must The Algorithm Stop?
The algorithm must stop because every new nonzero remainder is a smaller positive integer than the current divisor. Positive integers cannot keep falling forever while staying positive. Eventually the remainder is zero, and that exact division ends the process.
Look at the divisors in our example: 198, 54, 36, and 18. Each one is smaller than the previous divisor. We don’t need to guess how far to continue; the remainder itself tells us whether another step is needed.
The rule r < b is essential here. If a remainder equaled or exceeded b, another copy of b would still fit. Ordinary integer division removes all those whole copies first, leaving a remainder from zero up to b − 1.
The drawing shows the order of the remainders, not a measured graph of their sizes. Some calculations end in fewer steps than this example, and others take more. The proof only needs each positive remainder to be smaller than the divisor before it.
Why Is The Last Nonzero Number The GCD?
When a division has remainder zero, the current divisor divides the current dividend exactly. It’s the greatest common divisor of that final pair because no positive divisor of the smaller number can exceed that number. Every earlier pair shares the same GCD, so the result also belongs to the starting pair.
Here, 36 = 18 × 2 + 0. The number 18 divides both 36 and 18, and no common divisor can be greater than 18. That finishes the proof for the original numbers 252 and 198.
Don’t take the final remainder, zero, as the answer. Zero cannot divide a positive integer, since multiplying zero by any integer still gives zero. Instead, take the divisor in the row that produced remainder zero.
If the very first division is exact, the smaller starting number is already the answer. For 84 and 21, the equation is 84 = 21 × 4 + 0. There is no positive remainder to record, but the final nonzero divisor is 21.
Equal positive inputs end the same way. For 21 and 21, divide to get 21 = 21 × 1 + 0, and the GCD is 21. If the inputs arrive in the opposite order, swap them first; swapping doesn’t change which numbers divide both.
What Happens With One, Zero, And Negative Inputs?
A final divisor of 1 means the starting numbers are coprime: their only positive common divisor is 1. Zero and negative inputs need simple setup rules before division. Use absolute values for negatives, and handle a zero input directly instead of trying to divide by zero.
For 35 and 12, the equations are 35 = 12 × 2 + 11, 12 = 11 × 1 + 1, and 11 = 1 × 11 + 0. The remainder sequence is 11, 1, 0. The GCD is 1, even though neither starting number is 1.
For any nonzero integer a, gcd(a, 0) = |a|. Every positive divisor of a also divides zero because zero is that divisor times zero. The greatest one is the absolute value of a.
When both inputs are zero, gcd(0, 0) is conventionally set to 0 in many mathematical and computing settings. But zero and zero have no greatest positive common divisor: every positive integer divides both. Keep that convention separate from the usual greatest-positive-divisor definition.
Negative signs don’t change positive common divisors. Thus gcd(−252, 198) = gcd(252, 198) = 18. Taking absolute values first keeps the remainder steps consistent with the nonnegative remainder rule used in this proof.
How Can You Use And Check The Result?
Use the GCD to remove the largest shared integer factor from a fraction or to check a common grouping size. For 252/198, divide both terms by 18 to get 14/11. No common factor greater than 1 remains, because it would imply a larger shared factor in the original terms.
You can compare your hand calculation with the GCD and LCM calculator. For a single remainder step, the modulo calculator connects division to its leftover. Use the same positive integer inputs when checking the steps shown here.
The proof applies to integers, not to an unrestricted search for decimal divisors. Measurements such as 2.52 meters and 1.98 meters can be expressed as 252 centimeters and 198 centimeters first. The integer GCD is then 18 centimeters in that common unit.
Rescaling requires a shared unit and exact values. If the measurements were rounded, the result describes their recorded values rather than proving an exact shared length in the objects. Always state the unit when translating an integer answer back to measurements.
GCD and greatest common factor, or GCF, name the same quantity here. The GCF and LCM product relationship explains a separate connection using factor structure. This proof rests instead on a shared-divisor rule: taking the remainder keeps the same common divisors, and shrinking remainders lead to exact division.