The Euclidean algorithm is a fast method for finding the greatest common divisor of two whole numbers. The greatest common divisor, or GCD, is the largest positive integer that divides both numbers with no remainder. This matters in simplifying fractions, comparing ratios, solving number theory problems, and working with modular arithmetic.
Instead of listing all factors, the algorithm uses repeated division to shrink the problem step by step.
Understanding Math: The Euclidean Algorithm
The important idea behind the method is that common divisors survive when whole groups are removed. Suppose one number contains several complete copies of a smaller number, plus a leftover part. Any number that divides both original numbers must divide that leftover too.
This is because it divides the large number and each complete copy being removed. The reverse is true as well. A number that divides the smaller number and the leftover can rebuild the original large number.
So the shared divisors do not change when the large number is replaced by the leftover. This is the reason the algorithm works, not just a rule to memorise.
Consider finding the greatest common divisor of four hundred fourteen and one hundred fifty six. Two full groups of one hundred fifty six fit into four hundred fourteen, leaving one hundred two. Next, one group of one hundred two leaves fifty four from one hundred fifty six.
Removing fifty four from one hundred two leaves forty eight. Removing forty eight from fifty four leaves six. Finally, forty eight contains an exact number of groups of six.
The answer is six. Notice that the numbers become smaller quickly, even though the starting values were fairly large. The quotients tell how many groups were removed, but the remainders carry the key information.
This process has a practical meaning when objects must be split into equal largest-sized groups. If a rectangular display is four hundred fourteen centimetres by one hundred fifty six centimetres, squares with side length six centimetres are the largest equal squares that can tile it without gaps. In fractions, the same result gives the biggest number that can divide the top and bottom.
A fraction with four hundred fourteen over one hundred fifty six reduces by dividing both parts by six. The method is useful whenever a shared measuring unit is needed, such as cutting equal lengths of material or organising repeating patterns.
When practising, write each division clearly and check that every remainder is smaller than the number used for division. A remainder that is equal to or larger than that number means the division step is wrong. Put the larger positive number first, though swapping the two inputs does not change the final result.
If one input is zero, the nonzero input is the answer. Negative inputs are usually handled by ignoring their signs. When the result is one, the numbers are called coprime.
They share no positive factor except one. This matters later in fraction work, modular arithmetic, and the extended Euclidean algorithm, which can express the result using combinations of the original numbers.
Key Facts
- For positive integers a and b with a > b, divide: a = bq + r, where 0 <= r < b.
- The Euclidean algorithm replaces gcd(a, b) with gcd(b, r).
- Repeat division until the remainder is 0.
- The last nonzero remainder is the greatest common divisor.
- Worked example: 252 = 105(2) + 42, 105 = 42(2) + 21, 42 = 21(2) + 0, so gcd(252, 105) = 21.
- Key identity: gcd(a, b) = gcd(b, a mod b).
Vocabulary
- Greatest Common Divisor
- The greatest common divisor is the largest positive integer that divides two or more integers exactly.
- Remainder
- The remainder is the amount left over after dividing one integer by another.
- Quotient
- The quotient is the whole-number result in a division step before considering the remainder.
- Divisor
- A divisor is a number that divides another number with no remainder.
- Modulo
- Modulo is an operation that gives the remainder after integer division, written as a mod b.
Common Mistakes to Avoid
- Stopping when the remainder is 0 and reporting 0 as the GCD is wrong. The GCD is the last nonzero remainder, not the final zero.
- Dividing the smaller number by the larger number first without reorganizing the problem can create confusion. Start with the larger number divided by the smaller number, or swap the order since gcd(a, b) = gcd(b, a).
- Dropping a remainder from the next line is wrong. Each new division must use the previous divisor as the new dividend and the previous remainder as the new divisor.
- Assuming the quotient is the GCD is wrong. The quotients guide the divisions, but the GCD comes from the last nonzero remainder.
Practice Questions
- 1 Use the Euclidean algorithm to find gcd(84, 30). Show each division step.
- 2 Use repeated division with remainders to find gcd(391, 299).
- 3 Explain why replacing gcd(a, b) with gcd(b, r) does not change the greatest common divisor when a = bq + r.