Euclidean Algorithm — Definition, Formula & Examples

The Euclidean Algorithm is a method for finding the greatest common divisor (GCD) of two positive integers by repeatedly dividing the larger number by the smaller and replacing with the remainder until the remainder is zero.

Given integers $a$ and $b$ with $a > b > 0$ , the Euclidean Algorithm applies the division algorithm iteratively: $a = bq + r$ where $0 \le r < b$ , then replaces $(a, b)$ with $(b, r)$ . The process terminates when $r = 0$ , at which point the last nonzero remainder equals $\gcd(a, b)$ .

Key Formula

\gcd(a, b) = \gcd(b,\; a \bmod b), \quad \gcd(a, 0) = a

Where:

$a$ = The larger of the two positive integers
$b$ = The smaller of the two positive integers
$a \bmod b$ = The remainder when a is divided by b

How It Works

Start with two positive integers. Divide the larger by the smaller and note the remainder. Replace the larger number with the smaller, and the smaller with the remainder. Repeat until the remainder is zero. The last nonzero remainder is the GCD. This works because

\gcd(a, b) = \gcd(b, a \bmod b)

, so each step preserves the GCD while shrinking the numbers.

Worked Example

Problem: Find the GCD of 270 and 192 using the Euclidean Algorithm.

Step 1: Divide 270 by 192. The quotient is 1 and the remainder is 78.

270 = 192 \times 1 + 78

Step 2: Replace: now find GCD of 192 and 78. Divide 192 by 78.

192 = 78 \times 2 + 36

Step 3: Replace: now find GCD of 78 and 36. Divide 78 by 36.

78 = 36 \times 2 + 6

Step 4: Replace: now find GCD of 36 and 6. Divide 36 by 6.

36 = 6 \times 6 + 0

Step 5: The remainder is 0, so the last nonzero remainder is the GCD.

Answer:

\gcd(270, 192) = 6

Why It Matters

The Euclidean Algorithm is fundamental in cryptography — RSA encryption relies on it to compute modular inverses. It also appears throughout number theory courses when solving linear Diophantine equations and working with modular arithmetic.

Common Mistakes

Mistake: Stopping at the wrong step and reporting the divisor instead of the last nonzero remainder.

Correction: The GCD is the last nonzero remainder, not the number you divided by in the final step. When you reach a remainder of 0, look back one step for the answer.