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.
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.