Euclidean Algorithm

The Euclidean algorithm finds the greatest common divisor of two integers by repeatedly dividing and replacing the pair with the divisor and remainder. In brief: 252 = 105 × 2 + 42, 105 = 42 × 2 + 21, and 42 = 21 × 2, so GCD(252, 105) = 21.

This method avoids long divisor lists and does not require complete prime factorization. Each step makes the numbers smaller while preserving their common divisors. This guide explains the remainder process, why the last nonzero remainder gives the answer, and how the result helps simplify fractions and calculate a least common multiple.

What does the Euclidean algorithm calculate?

The algorithm calculates the greatest common divisor, abbreviated GCD. For positive integers a and b, this is the largest positive integer that divides both exactly. A pair such as 48 and 18 has common divisors 1, 2, 3 and 6, so its GCD is 6.

You could find a GCD by listing factors or comparing prime factorizations. The Euclidean algorithm instead asks what happens to the common divisors when a division leaves a remainder. Its efficiency comes from retaining the needed relationship while discarding much of the size of the original numbers.

The standard beginner method begins with the larger positive number as the dividend and the smaller as the divisor. For signed inputs, use their absolute values first, since changing a sign does not change positive divisibility. If one input is zero and the other is nonzero, their GCD is the absolute value of the nonzero input.

How does one Euclidean algorithm step work?

Divide a by b and write a = b × q + r, with quotient q and remainder r satisfying 0 ≤ r < b for positive b. Then replace the pair (a, b) with (b, r). If r is zero, stop; otherwise perform another exact quotient-and-remainder calculation.

For the pair 252 and 105, the first quotient is 2 and the remainder is 42 because 252 = 105 × 2 + 42. The next pair is therefore 105 and 42. Dividing 105 by 42 gives quotient 2 and remainder 21, so the pair becomes 42 and 21.

The final division gives remainder zero: 42 = 21 × 2 + 0. The divisor in that last division is 21, which is the GCD. Do not report the final remainder zero as the answer. Zero marks the stopping condition; the last nonzero remainder, or equivalently the final nonzero divisor, is the value you need.

1. Divide the larger positive number by the smaller.
2. Record the remainder and replace the pair with divisor and remainder.
3. Repeat while the remainder is nonzero.
4. Return the divisor of the final exact division.

Euclidean algorithm worked example with 1071 and 462

Start with 1071 ÷ 462. Two copies of 462 total 924, leaving 147. Thus 1071 = 462 × 2 + 147, and the next pair is 462 and 147. The remainder is smaller than the divisor, as required.

Three copies of 147 total 441, leaving 21 from 462. Therefore 462 = 147 × 3 + 21, and the next pair is 147 and 21. The final division is exact: 147 = 21 × 7 + 0. Hence GCD(1071, 462) = 21.

Check the answer against the original inputs: 1071 ÷ 21 = 51 and 462 ÷ 21 = 22. This establishes that 21 divides both. The algorithm’s preservation argument establishes why no larger common divisor was missed. Each table row can also be checked separately by multiplying its divisor and quotient, then adding its remainder.

Why does the Euclidean algorithm work?

Suppose a = b × q + r. Any integer d dividing both a and b also divides r, because r = a − b × q. Subtracting a multiple of a number divisible by d from another number divisible by d leaves a value still divisible by d.

Conversely, any d dividing both b and r also divides a, because a = b × q + r. The pairs (a, b) and (b, r) therefore have exactly the same common divisors. Their greatest common divisor is unchanged, which justifies every replacement rather than merely suggesting a shortcut.

At the end, the pair is (d, 0). Every positive divisor of d divides zero as well, and the greatest positive divisor of d is d itself. The algorithm also must end, because its nonzero remainders form a strictly decreasing sequence of positive integers. Such a sequence cannot continue forever below its starting value.

What happens with coprime numbers, exact division or zero?

If one positive number divides the other immediately, the algorithm ends after the first division. For 144 and 36, the equation 144 = 36 × 4 + 0 gives GCD 36. No further remainder step is needed, and attempting to divide by the zero remainder would be an error.

Coprime numbers finish with GCD 1. For 35 and 12, the chain is 35 = 12 × 2 + 11, 12 = 11 × 1 + 1, then 11 = 1 × 11 + 0. The final nonzero divisor is 1, showing that no larger positive common factor exists.

For a nonzero integer a, GCD(a, 0) is |a|. When both inputs are zero, elementary greatest-positive-divisor language has no largest divisor, since every positive integer divides zero. Many software and algebra conventions define GCD(0, 0) as 0, so state the convention if that case appears rather than applying ordinary positive-input reasoning blindly.

How do you use the algorithm for fractions and LCM?

To reduce 1071/462, find their GCD 21 and divide both parts by it. The reduced fraction is 51/22. The numerator and denominator now have GCD 1, so there is no common positive factor greater than 1 left to cancel.

For positive integers a and b, their least common multiple is (a ÷ GCD(a, b)) × b. For 252 and 105, the GCD is 21, so divide 252 by 21 to get 12, then multiply 12 × 105 = 1260. Both 252 and 105 divide this result exactly.

A geometric interpretation uses the largest square tile that fits a rectangular grid without cutting when side lengths are integer units. For a rectangle measuring 252 by 105 units, the largest permitted integer square side is 21 units. The division steps correspond to removing blocks of squares and examining the smaller leftover rectangle.

What is the algorithm’s background and which mistakes should you avoid?

The Euclidean algorithm is associated with Euclid’s treatment of common measures in the Elements. Its modern arithmetic form uses quotient and remainder notation, while a related subtraction view repeatedly removes the smaller quantity from the larger. Division compresses many such subtractions into one step.

A common mistake is carrying the quotient into the next pair instead of the remainder. In 252 = 105 × 2 + 42, the next inputs are 105 and 42, not 105 and 2. Another is keeping the original larger input at every step rather than replacing both entries consistently.

Check that each remainder is nonnegative and smaller than its divisor, that each row reconstructs its dividend, and that the final GCD divides both original numbers. Do not replace the remainder process with rounded decimal quotients. The algorithm needs exact integer division information, and the last zero should stop the process rather than become a new divisor or the reported GCD.

Frequently asked questions

Is the GCD the last remainder?

The GCD is the final nonzero divisor; when nonzero remainders occur, it is the last of them. The final zero only signals that you should stop.

Do I need prime factorization first?

Prime factorization is not needed for the Euclidean algorithm. The method uses only exact integer quotients and remainders.

What if I start with the smaller number first?

The algorithm still works if you allow an initial quotient of zero. Ordering the larger number first simply avoids that extra preliminary step.

Why does the algorithm always finish?

Every nonzero remainder is smaller than the preceding positive divisor. A strictly decreasing sequence of positive integers must eventually reach a final exact division.

Can I find the GCD of three numbers this way?

Find the GCD of the first two, then find the GCD of that result with the third. This pairwise process retains exactly the common divisors of all three inputs.