Euclidean Algorithm Explained: Definition, Steps and Applications

The Euclidean algorithm is one of the oldest algorithms in mathematics — described by Euclid around 300 BCE — and one of the most useful. It finds the greatest common divisor (GCD) of two integers efficiently, using nothing more than repeated division with remainder. It is the foundation of a significant portion of computational number theory, appears in every major mathematics competition, and underlies the RSA cryptography system that secures most internet communication today.

This guide explains the Euclidean algorithm step by step, proves why it works, extends it to find integer solutions to linear equations, and shows where it appears in the curriculum and in competition mathematics.

---

What Is the Euclidean Algorithm?

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two positive integers — the largest integer that divides both without remainder.

The key insight: $\gcd(a, b) = \gcd(b, r)$gcd(a,b)=gcd(b,r) where $r$r is the remainder when $a$a is divided by $b$b.

This means you can replace the larger number with the smaller, and the smaller number with the remainder, repeating until the remainder is 0. The last non-zero remainder is the GCD.

---

The Euclidean Algorithm: Step by Step

Algorithm:

Given two positive integers $a > b$a>b:

1. Divide $a$a by $b$b: write $a = q \cdot b + r$a=q⋅b+r where $0 \leq r < b$0≤r<b
2. If $r = 0$r=0: the GCD is $b$b. Stop.
3. If $r \neq 0$r=0: replace $(a, b)$(a,b) with $(b, r)$(b,r) and go to Step 1.

Why it terminates: The remainders form a strictly decreasing sequence of non-negative integers — so the algorithm must reach 0 in a finite number of steps.

---

Worked Examples

Example 1 — Finding gcd(252, 105)

$$252 = 2 \times 105 + 42$$252=2×105+42 $$105 = 2 \times 42 + 21$$105=2×42+21 $$42 = 2 \times 21 + 0$$42=2×21+0

Remainder is 0. Last non-zero remainder: 21.$$\gcd(252, 105) = 21$$gcd(252,105)=21

Check: $252 = 21 \times 12$252=21×12 ✓ and $105 = 21 \times 5$105=21×5 ✓

---

Example 2 — Finding gcd(1071, 462)

$$1071 = 2 \times 462 + 147$$1071=2×462+147 $$462 = 3 \times 147 + 21$$462=3×147+21 $$147 = 7 \times 21 + 0$$147=7×21+0 $$\gcd(1071, 462) = 21$$gcd(1071,462)=21

---

Example 3 — Finding gcd(17, 13) (Consecutive-ish primes)

$$17 = 1 \times 13 + 4$$17=1×13+4 $$13 = 3 \times 4 + 1$$13=3×4+1 $$4 = 4 \times 1 + 0$$4=4×1+0 $$\gcd(17, 13) = 1$$gcd(17,13)=1

When the GCD is 1, the two numbers are coprime (share no common factor other than 1). This is significant in number theory and cryptography.

---

Example 4 — Finding gcd(144, 89) (Fibonacci numbers!)

$$144 = 1 \times 89 + 55$$144=1×89+55 $$89 = 1 \times 55 + 34$$89=1×55+34 $$55 = 1 \times 34 + 21$$55=1×34+21 $$34 = 1 \times 21 + 13$$34=1×21+13 $$21 = 1 \times 13 + 8$$21=1×13+8 $$13 = 1 \times 8 + 5$$13=1×8+5 $$8 = 1 \times 5 + 3$$8=1×5+3 $$5 = 1 \times 3 + 2$$5=1×3+2 $$3 = 1 \times 2 + 1$$3=1×2+1 $$2 = 2 \times 1 + 0$$2=2×1+0 $$\gcd(144, 89) = 1$$gcd(144,89)=1

This is not a coincidence. 144 and 89 are consecutive Fibonacci numbers, and consecutive Fibonacci numbers are always coprime. The Euclidean algorithm applied to consecutive Fibonacci numbers produces the maximum possible number of steps — making Fibonacci pairs the “worst case” for the algorithm. This is a classical result in algorithm analysis.

---

Why the Euclidean Algorithm Works: The Proof

Claim: $\gcd(a, b) = \gcd(b, r)$gcd(a,b)=gcd(b,r) where $a = qb + r$a=qb+r.

Proof:

Let $d = \gcd(a, b)$d=gcd(a,b). We show $d = \gcd(b, r)$d=gcd(b,r).

Since $d \mid a$d∣a and $d \mid b$d∣b: $d \mid (a – qb) = r$d∣(a−qb)=r. So $d$d is a common divisor of $b$b and $r$r.

Now let $e$e be any common divisor of $b$b and $r$r. Then $e \mid qb$e∣qb and $e \mid r$e∣r, so $e \mid (qb + r) = a$e∣(qb+r)=a. Thus $e$e is a common divisor of $a$a and $b$b, so $e \leq d$e≤d.

Therefore $d$d is the greatest common divisor of $b$b and $r$r: $\gcd(b, r) = d = \gcd(a, b)$gcd(b,r)=d=gcd(a,b). □

This proof is short, elegant, and uses only the definition of divisibility — a model of mathematical reasoning that competition students should know.

---

The Euclidean Algorithm and the LCM

The GCD and LCM (least common multiple) are related by:$$\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$$lcm(a,b)=gcd(a,b)a⋅b​

So once the GCD is found using the Euclidean algorithm, the LCM follows immediately.

Example: $\text{lcm}(252, 105) = \frac{252 \times 105}{21} = \frac{26460}{21} = 1260$lcm(252,105)=21252×105​=2126460​=1260.

---

The Extended Euclidean Algorithm

The extended Euclidean algorithm not only finds $\gcd(a, b)$gcd(a,b) but also finds integers $x$x and $y$y such that:$$ax + by = \gcd(a, b)$$ax+by=gcd(a,b)

This is called a Bézout identity (or Bézout’s lemma), and it states that the GCD of two integers can always be expressed as an integer linear combination of those integers.

Method: Back-substitution

Working backwards through the Euclidean algorithm steps, express each remainder as a linear combination of $a$a and $b$b.

Example: Find $x$x, $y$y such that $252x + 105y = 21 = \gcd(252, 105)$252x+105y=21=gcd(252,105).

From the Euclidean algorithm steps:$$42 = 252 – 2 \times 105 \quad \cdots (1)$$42=252−2×105⋯(1) $$21 = 105 – 2 \times 42 \quad \cdots (2)$$21=105−2×42⋯(2)

Substitute (1) into (2):$$21 = 105 – 2(252 – 2 \times 105) = 105 – 2 \times 252 + 4 \times 105 = 5 \times 105 – 2 \times 252$$21=105−2(252−2×105)=105−2×252+4×105=5×105−2×252

So: $252 \times (-2) + 105 \times 5 = 21$252×(−2)+105×5=21.

x=−2x = -2 x=−2, y=5y = 5 y=5.

Check: $252 \times (-2) + 105 \times 5 = -504 + 525 = 21$252×(−2)+105×5=−504+525=21 ✓

---

Applications of the Extended Euclidean Algorithm

1. Solving Linear Diophantine Equations

A linear Diophantine equation is an equation of the form $ax + by = c$ax+by=c where $a$a, $b$b, $c$c are integers and we seek integer solutions $x$x, $y$y.

Theorem (Bézout): $ax + by = c$ax+by=c has integer solutions if and only if $\gcd(a, b) \mid c$gcd(a,b)∣c.

Method:

1. Find $\gcd(a, b)$gcd(a,b) using the Euclidean algorithm.
2. Check if $\gcd(a, b) \mid c$gcd(a,b)∣c. If not: no solution.
3. Use back-substitution to find a particular solution $(x_0, y_0)$(x0​,y0​) to $ax + by = \gcd(a,b)$ax+by=gcd(a,b).
4. Scale: multiply by $c / \gcd(a,b)$c/gcd(a,b) to get a solution to $ax + by = c$ax+by=c.
5. The general solution is: $x = x_0 \cdot \frac{c}{d} + \frac{b}{d}t$x=x0​⋅dc​+db​t, $y = y_0 \cdot \frac{c}{d} – \frac{a}{d}t$y=y0​⋅dc​−da​t for any integer $t$t, where $d = \gcd(a,b)$d=gcd(a,b).

Example: Solve $252x + 105y = 63$252x+105y=63.

$\gcd(252, 105) = 21$gcd(252,105)=21 and $21 \mid 63$21∣63 ✓.

From above: $252(-2) + 105(5) = 21$252(−2)+105(5)=21. Multiply by $63/21 = 3$63/21=3:

$252(-6) + 105(15) = 63$252(−6)+105(15)=63.

Particular solution: $(x_0, y_0) = (-6, 15)$(x0​,y0​)=(−6,15).

General solution: $x = -6 + 5t$x=−6+5t, $y = 15 – 12t$y=15−12t for any integer $t$t.

Check with t=1t=1 t=1: $252(-1) + 105(3) = -252 + 315 = 63$252(−1)+105(3)=−252+315=63 ✓

2. Modular Inverses

If $\gcd(a, m) = 1$gcd(a,m)=1, the extended Euclidean algorithm finds the modular inverse of $a$a modulo $m$m — the integer $x$x such that $ax \equiv 1 \pmod{m}$ax≡1(modm).

From $ax + my = 1$ax+my=1 (Bézout, since $\gcd(a,m) = 1$gcd(a,m)=1): $ax \equiv 1 \pmod{m}$ax≡1(modm).

This is foundational to RSA cryptography and appears in competition number theory problems.

Example: Find the inverse of 7 modulo 11.

$\gcd(7, 11) = 1$gcd(7,11)=1. Apply extended Euclidean algorithm:

$11 = 1 \times 7 + 4$11=1×7+4 $7 = 1 \times 4 + 3$7=1×4+3 $4 = 1 \times 3 + 1$4=1×3+1 $3 = 3 \times 1 + 0$3=3×1+0

Back-substitution: $1 = 4 – 1 \times 3 = 4 – (7 – 4) = 2 \times 4 – 7 = 2(11 – 7) – 7 = 2 \times 11 – 3 \times 7$1=4−1×3=4−(7−4)=2×4−7=2(11−7)−7=2×11−3×7

So $7 \times (-3) + 11 \times 2 = 1$7×(−3)+11×2=1, meaning $7 \times (-3) \equiv 1 \pmod{11}$7×(−3)≡1(mod11).

$-3 \equiv 8 \pmod{11}$−3≡8(mod11).

Modular inverse of 7 mod 11 is 8. Check: $7 \times 8 = 56 = 5 \times 11 + 1 \equiv 1 \pmod{11}$7×8=56=5×11+1≡1(mod11) ✓

---

The Euclidean Algorithm in the Ontario Curriculum

The Euclidean algorithm is not part of the standard Ontario K–12 curriculum, but GCD and LCM are:

Grade 8 (Ontario): Students find the GCD and LCM of pairs of numbers using factor lists or prime factorisation. The Euclidean algorithm provides a faster method for large numbers and is worth knowing as a supplement to the curriculum approach. See our Grade 8 math curriculum Ontario guide.

Grade 9 MTH1W (Ontario): Number theory concepts including GCD appear in the curriculum. See our Ontario Grade 9 math curriculum guide.

Math 30-1 (Alberta): Divisibility and integer properties underpin the polynomial content. See our Math 30-1 complete guide.

---

Where the Euclidean Algorithm Appears in Competitions

AMC 8 and Gauss Contest (Grades 7–8)

GCD and LCM problems appear regularly in both contests — typically using factor lists or prime factorisation rather than the Euclidean algorithm directly. Knowing the algorithm gives a faster method for large numbers. See our AMC 8 guide and Gauss math contest guide.

AMC 10 and Cayley/Fermat Contests (Grades 9–11)

Number theory problems at this level include GCD and coprimality. The extended Euclidean algorithm enables solving linear Diophantine equations that appear as multi-step problems. Recognising when a problem reduces to $ax + by = c$ax+by=c and applying Bézout’s lemma is a standard technique.

Euclid Contest (CEMC, Grade 12)

The Euclidean algorithm and its extensions appear in Euclid Part B and Part C number theory problems. Modular inverses (found via the extended algorithm) underpin certain problems involving fractions modulo a prime. See our Euclid math contest guide.

COMC and CMO

Linear Diophantine equations, Bézout’s identity, and modular inverses — all rooted in the extended Euclidean algorithm — are standard tools in COMC Part C and CMO number theory. See our COMC math contest guide and Canadian Mathematical Olympiad guide.

---

---

Common Mistakes with the Euclidean Algorithm

Mistake 1: Using the wrong pair after each step.After computing $a = qb + r$a=qb+r, the next step uses $(b, r)$(b,r) — not $(a, r)$(a,r) or $(q, r)$(q,r). The larger number is replaced by the smaller, and the smaller by the remainder.

Mistake 2: Stopping too early. The algorithm stops when the remainder is 0, and the GCD is the previous (non-zero) remainder — not the quotient of the final step.

Mistake 3: Back-substitution direction errors in the extended algorithm. In back-substitution, it is easy to substitute in the wrong direction or to make a sign error. Write each remainder explicitly as a linear combination at every step, checking the arithmetic before proceeding.

Mistake 4: Assuming ax+by=cax + by = c ax+by=c always has solutions.It has solutions if and only if $\gcd(a, b) \mid c$gcd(a,b)∣c. If $\gcd(a, b) \nmid c$gcd(a,b)∤c, no integer solution exists. Check divisibility before attempting to solve.

Mistake 5: Giving only one solution to a Diophantine equation.Linear Diophantine equations with solutions have infinitely many. The general solution involves a parameter $t$t. Competition problems sometimes ask for specific solution types (positive integers, smallest positive solution) — find the general solution first, then filter.

---

Practice Problems

Set A — Euclidean algorithm

Find each GCD using the Euclidean algorithm (show all steps):

1. $\gcd(48, 18)$gcd(48,18)
2. $\gcd(210, 45)$gcd(210,45)
3. $\gcd(1000, 256)$gcd(1000,256)
4. $\gcd(144, 55)$gcd(144,55)
5. $\gcd(999, 111)$gcd(999,111)

Set B — LCM

6. Find $\text{lcm}(48, 18)$lcm(48,18)
7. Find $\text{lcm}(210, 45)$lcm(210,45)
8. The GCD of two numbers is 12 and their LCM is 360. One number is 36. Find the other.

Set C — Extended algorithm and Diophantine equations

9. Find integers $x$x, $y$y such that $48x + 18y = \gcd(48, 18)$48x+18y=gcd(48,18).
10. Does $210x + 45y = 15$210x+45y=15 have integer solutions? If so, find the general solution.
11. Find the modular inverse of 5 modulo 13.
12. Find all positive integer solutions to $17x + 11y = 100$17x+11y=100.

---

Answers:

Set A:

1. $48 = 2\times18+12$48=2×18+12; $18=1\times12+6$18=1×12+6; $12=2\times6+0$12=2×6+0. gcd⁡(48,18)=6\gcd(48,18) = 6 gcd(48,18)=6
2. $210=4\times45+30$210=4×45+30; $45=1\times30+15$45=1×30+15; $30=2\times15+0$30=2×15+0. gcd⁡(210,45)=15\gcd(210,45) = 15 gcd(210,45)=15
3. $1000=3\times256+232$1000=3×256+232; $256=1\times232+24$256=1×232+24; $232=9\times24+16$232=9×24+16; $24=1\times16+8$24=1×16+8; $16=2\times8+0$16=2×8+0. gcd⁡(1000,256)=8\gcd(1000,256) = 8 gcd(1000,256)=8
4. $144=2\times55+34$144=2×55+34; $55=1\times34+21$55=1×34+21; $34=1\times21+13$34=1×21+13; $21=1\times13+8$21=1×13+8; $13=1\times8+5$13=1×8+5; $8=1\times5+3$8=1×5+3; $5=1\times3+2$5=1×3+2; $3=1\times2+1$3=1×2+1; $2=2\times1+0$2=2×1+0. gcd⁡(144,55)=1\gcd(144,55) = 1 gcd(144,55)=1 (consecutive Fibonacci-adjacent numbers)
5. $999=9\times111+0$999=9×111+0. gcd⁡(999,111)=111\gcd(999,111) = 111 gcd(999,111)=111

Set B: 6. $\text{lcm}(48,18) = 48\times18/6 = 864/6 = $ 144 7. $\text{lcm}(210,45) = 210\times45/15 = 9450/15 = $ 6308. $a \times b = \gcd \times \text{lcm}$a×b=gcd×lcm: $36 \times b = 12 \times 360 = 4320$36×b=12×360=4320; $b = $ 120

Set C: 9. From steps: $6 = 18-1\times12 = 18-(48-2\times18) = 3\times18-1\times48$6=18−1×12=18−(48−2×18)=3×18−1×48. So $48\times(-1)+18\times3=6$48×(−1)+18×3=6. x=−1,y=3x=-1, y=3 x=−1,y=310. $\gcd(210,45)=15$gcd(210,45)=15 and $15\mid15$15∣15 ✓. From above: $210\times(-1)+45\times(?)$210×(−1)+45×(?)… find particular solution then general. $210\times(-2)+45\times(9+?)$210×(−2)+45×(9+?)… Actually: divide through: $14x+3y=1$14x+3y=1. Back-sub: $\gcd(14,3)=1$gcd(14,3)=1; $14=4\times3+2$14=4×3+2; $3=1\times2+1$3=1×2+1; so $1=3-1\times2=3-(14-4\times3)=5\times3-14$1=3−1×2=3−(14−4×3)=5×3−14. So $14\times(-1)+3\times5=1$14×(−1)+3×5=1. Scale by 15: $14\times(-15)+3\times75=15$14×(−15)+3×75=15, i.e. $210\times(-1)+45\times5=15$210×(−1)+45×5=15… General solution: x=−1+3tx=-1+3t x=−1+3t, y=5−14ty=5-14t y=5−14t for any integer $t$t.

11. $\gcd(5,13)=1$gcd(5,13)=1: $13=2\times5+3$13=2×5+3; $5=1\times3+2$5=1×3+2; $3=1\times2+1$3=1×2+1. Back-sub: $1=3-2=3-(5-3)=2\times3-5=2(13-2\times5)-5=2\times13-5\times5$1=3−2=3−(5−3)=2×3−5=2(13−2×5)−5=2×13−5×5. So $5\times(-5)+13\times2=1$5×(−5)+13×2=1, meaning $5^{-1}\equiv -5\equiv 8\pmod{13}$5−1≡−5≡8(mod13). Modular inverse of 5 mod 13 is 8. Check: $5\times8=40=3\times13+1\equiv1\pmod{13}$5×8=40=3×13+1≡1(mod13) ✓
12. $\gcd(17,11)=1\mid100$gcd(17,11)=1∣100 ✓. Find particular solution: back-sub gives $17\times2-11\times3=1$17×2−11×3=1… actually $17=1\times11+6$17=1×11+6; $11=1\times6+5$11=1×6+5; $6=1\times5+1$6=1×5+1. So $1=6-5=6-(11-6)=2\times6-11=2(17-11)-11=2\times17-3\times11$1=6−5=6−(11−6)=2×6−11=2(17−11)−11=2×17−3×11. Scale by 100: $17\times200+11\times(-300)=100$17×200+11×(−300)=100. General: $x=200-11t$x=200−11t, $y=-300+17t$y=−300+17t. Positive integer solutions: $x>0$x>0: $t<200/11\approx18.2$t<200/11≈18.2; $y>0$y>0: $t>300/17\approx17.6$t>300/17≈17.6. So $t=18$t=18: $x=200-198=2$x=200−198=2, $y=-300+306=6$y=−300+306=6. (x,y)=(2,6)(x,y)=(2,6) (x,y)=(2,6) is the only positive solution.

---

Frequently Asked Questions

What is the Euclidean algorithm? A method for finding the greatest common divisor (GCD) of two integers by repeated division with remainder. At each step, the larger number is replaced by the smaller, and the smaller by the remainder, until the remainder is 0. The last non-zero remainder is the GCD.

Why is the Euclidean algorithm useful? It finds the GCD far more efficiently than prime factorisation for large numbers. It is also the foundation for the extended Euclidean algorithm, which solves linear Diophantine equations and finds modular inverses — both essential in competition number theory and cryptography.

What is the extended Euclidean algorithm?An extension that, in addition to finding $\gcd(a, b)$gcd(a,b), finds integers $x$x and $y$y satisfying $ax + by = \gcd(a, b)$ax+by=gcd(a,b) (Bézout’s identity). It uses back-substitution through the steps of the standard algorithm.

What is Bézout’s lemma?For any integers $a$a and $b$b, there exist integers $x$x and $y$y such that $ax + by = \gcd(a, b)$ax+by=gcd(a,b). The extended Euclidean algorithm finds these $x$x and $y$y explicitly.

Does the Euclidean algorithm appear in the Ontario curriculum? GCD and LCM are in the Ontario curriculum from Grade 8 onward, but the Euclidean algorithm specifically is not prescribed. It is taught as a competition mathematics tool and a more efficient alternative to factor-list methods.

How does the Euclidean algorithm relate to the Euclid Contest? The Euclid Contest (CEMC) is named after Euclid, who described the algorithm around 300 BCE. The algorithm itself — and its extension to Diophantine equations and modular inverses — appears in Euclid Contest number theory problems at the Part B and Part C level.

---

See our related guides: Fermat’s Little Theorem guide · rules of divisibility guide · perfect numbers guide · Euclid math contest guide · COMC math contest guide · Canadian Mathematical Olympiad guide · AMC 8 guide · Gauss math contest guide · Grade 8 math curriculum Ontario · math competitions in Canada

---

The Euclidean algorithm is ancient mathematics that still underlies modern cryptography and competition number theory. Know it properly.