Course contentsShow
← Mathematics
Lesson 2714 of 3,12154. Number TheoryFree lesson

Working Through Euclidean Algorithm Examples

Apply the Euclidean Algorithm step-by-step to find GCDs of various integer pairs.

Working Through Euclidean Algorithm Examples

You'll learn: How to apply the Euclidean Algorithm step-by-step to compute the GCD of two integers efficiently.

The Core Process

The Euclidean Algorithm repeatedly applies the Division Algorithm until you reach a remainder of zero. At each step, you replace the larger number with the smaller, and the smaller number with the remainder. The last non-zero remainder is your GCD.

Think of it like peeling layers off an onion: each division strips away the "excess" until you're left with the common factor core.

Step-by-Step Example 1: GCD(84, 30)

  1. Divide 84 by 30: 84 = 30 × 2 + 24
  2. Divide 30 by 24: 30 = 24 × 1 + 6
  3. Divide 24 by 6: 24 = 6 × 4 + 0

Since the remainder is 0, we stop. The last non-zero remainder is 6, so GCD(84, 30) = 6.

Example 2: GCD(252, 105)

  1. 252 = 105 × 2 + 42
  2. 105 = 42 × 2 + 21
  3. 42 = 21 × 2 + 0

The GCD is 21.

Example 3: GCD(97, 13)

  1. 97 = 13 × 7 + 6
  2. 13 = 6 × 2 + 1
  3. 6 = 1 × 6 + 0

The GCD is 1 (these numbers are relatively prime).

The Pattern

Notice how each step uses the divisor and remainder from the previous step. The algorithm always terminates because remainders strictly decrease and remain non-negative. Typically, it converges surprisingly fast—even for large numbers!

Key Takeaway: The Euclidean Algorithm finds the GCD by repeatedly replacing pairs (a, b) with (b, a mod b) until the remainder is zero; the last non-zero remainder is the GCD.