Euclidean Algorithm: Algorithm and Correctness

Welcome, students 👋 In this lesson, you will learn how the Euclidean Algorithm finds the greatest common divisor of two integers and why it always works. This is a key idea in Number Theory because it gives a fast, reliable method for simplifying fractions, solving divisibility problems, and building more advanced results like Bézout’s identity.

What the Euclidean Algorithm Does

The greatest common divisor of two integers $a$ and $b$, written $\gcd(a,b)$, is the largest positive integer that divides both numbers. For example, $\gcd(48,18)=6$ because $6$ divides both $48$ and $18$, and no larger positive integer does.

The Euclidean Algorithm is a step-by-step method for finding $\gcd(a,b)$ using repeated division with remainders. The main idea is simple: instead of checking every divisor, you replace a pair of numbers with a smaller pair that has the same gcd.

The key division step is:

$$a=bq+r$$

where $a$ and $b$ are integers, $b\neq 0$, $q$ is the quotient, and $r$ is the remainder with $0\le r<|b|$.

The Euclidean Algorithm says that if $a=bq+r$, then

$$\gcd(a,b)=\gcd(b,r).$$

This is the heart of the method. It lets you keep shrinking the problem until the remainder becomes $0$.

Example of the procedure

Find $\gcd(48,18)$.

First divide $48$ by $18$:

$$48=18\cdot 2+12$$

So $\gcd(48,18)=\gcd(18,12)$.

Now divide $18$ by $12$:

$$18=12\cdot 1+6$$

So $\gcd(18,12)=\gcd(12,6)$.

Now divide $12$ by $6$:

$$12=6\cdot 2+0$$

Since the remainder is $0$, the process stops. The gcd is the last nonzero remainder, so

$$\gcd(48,18)=6.$$

This is efficient because the numbers get smaller very quickly 📉

Why the Algorithm Is Correct

A mathematical algorithm is not just a procedure that works on examples. To be trusted, it must be correct. In Number Theory, correctness means the method always gives the right answer for every valid input.

For the Euclidean Algorithm, correctness has two parts:

The process eventually stops.
The final answer is really the gcd.

Why the process stops

Each step replaces a pair $(a,b)$ with $(b,r)$, where the remainder $r$ satisfies

$$0\le r<|b|.$$

So the second number gets smaller each time, but it never becomes negative. A decreasing sequence of nonnegative integers cannot go on forever. Therefore, the algorithm must eventually reach a remainder of $0$.

This is an example of a termination argument. It shows the algorithm will not run forever.

Why the gcd does not change

Suppose

$$a=bq+r.$$

If a number $d$ divides both $a$ and $b$, then $d$ also divides $r$, because

$$r=a-bq.$$

Since $d$ divides both $a$ and $b$, it divides any integer combination of them, including $a-bq$.

Now go the other way. If $d$ divides both $b$ and $r$, then $d$ divides

$$bq+r=a.$$

So the common divisors of $(a,b)$ are exactly the common divisors of $(b,r)$. That means the greatest common divisor is the same:

$$\gcd(a,b)=\gcd(b,r).$$

This is the key correctness fact. It explains why the algorithm can replace one pair with another without changing the answer.

A Worked Correctness Example

Let’s look again at $48$ and $18$ and connect each step to correctness.

We have

$$48=18\cdot 2+12,$$

so the common divisors of $48$ and $18$ are exactly the common divisors of $18$ and $12$.

Then

$$18=12\cdot 1+6,$$

so the common divisors of $18$ and $12$ are exactly the common divisors of $12$ and $6$.

Finally,

$$12=6\cdot 2+0,$$

so the common divisors of $12$ and $6$ are the same as the common divisors of $6$ and $0$.

Now, every positive divisor of $6$ also divides $0$, since $0=6\cdot 0$. So the largest common divisor is $6$. The algorithm gives the correct result because every step preserves the gcd and the process ends when the remainder is $0$ ✅

How This Fits into Euclidean Algorithm Reasoning

The Euclidean Algorithm is more than a shortcut for finding gcds. It is a model of mathematical reasoning.

When you use it, you are doing three things:

applying the division algorithm to write $a=bq+r$,
using divisibility ideas to show the gcd stays the same,
repeating the step until the remainder is $0$.

This pattern is important in many areas of Number Theory. For example, if you want to simplify a fraction like $\frac{48}{18}$, knowing $\gcd(48,18)=6$ lets you reduce it to

$$\frac{48}{18}=\frac{8}{3}.$$

The gcd tells you the largest number that can divide both numerator and denominator.

The Euclidean Algorithm also connects directly to more advanced topics. One of the biggest is Bézout’s identity, which says that if $d=\gcd(a,b)$, then there exist integers $x$ and $y$ such that

$$ax+by=d.$$

The Euclidean Algorithm helps prove this identity by working backward from the remainders.

Why the Method Is Efficient

A practical reason the Euclidean Algorithm matters is speed ⏱️ Suppose you want to find $\gcd(2024,748)$. Checking all common divisors by hand would take a long time. The Euclidean Algorithm uses only division and remainders.

Here is a shortened version:

$$2024=748\cdot 2+528$$

$$748=528\cdot 1+220$$

$$528=220\cdot 2+88$$

$$220=88\cdot 2+44$$

$$88=44\cdot 2+0$$

$$\gcd(2024,748)=44.$$

Notice how quickly the numbers get smaller. This efficiency is one reason the Euclidean Algorithm is used in computing and in many mathematical proofs.

Common Mistakes to Avoid

A few errors can make the algorithm confusing:

Forgetting that the remainder must satisfy $0\le r<|b|$.
Stopping too early before the remainder is $0$.
Thinking the gcd is the last remainder, even if it is $0$. The gcd is the last nonzero remainder.
Mixing up the roles of $a$ and $b$ in the step $a=bq+r$.

A helpful habit is to write each step clearly and check that the remainder is smaller than the divisor.

Conclusion

students, the Euclidean Algorithm is a powerful method for finding $\gcd(a,b)$. Its correctness comes from two facts: each step keeps the gcd unchanged, and the remainders decrease until the process stops. This makes the algorithm both reliable and efficient. It is a major tool in Number Theory and a foundation for later ideas such as Bézout’s identity and solving divisibility problems. When you understand why it works, not just how to use it, you are doing real mathematical reasoning 🌟

Study Notes

The greatest common divisor is written as $\gcd(a,b)$ and means the largest positive integer dividing both $a$ and $b$.
The Euclidean Algorithm uses repeated division with remainder: $a=bq+r$, where $0\le r<|b|$.
The key rule is $\gcd(a,b)=\gcd(b,r)$.
The algorithm stops because the remainders form a decreasing sequence of nonnegative integers.
The answer is the last nonzero remainder.
Correctness means the method always gives the right answer and always finishes.
The proof of correctness depends on divisibility facts: if $d$ divides $a$ and $b$, then $d$ divides $a-bq$, and if $d$ divides $b$ and $r$, then $d$ divides $bq+r$.
The Euclidean Algorithm helps simplify fractions, solve gcd problems efficiently, and supports later results like Bézout’s identity.