Extended Euclidean Algorithm

In this lesson, we'll talk about the Extended Euclidean Algorithm and Linear Diophantine Equations.

Extended Euclidean Algorithm

As we saw in the last lesson, the Euclidean Algorithm finds the greatest common divisor between two integers. There's an extended version of this algorithm. But before talking about it, we need to talk about a theorem:

Bézout's Identity: Let and be integers with . There exist integers and such that

The purpose of the Extended Euclidean Algorithm is to calculate such and given and . To do this, we'll make some modifications to the Euclidean Algorithm. Let's remember the step of the Euclidean Algorithm:

1. If , return
2. Otherwise, return the gcd of and

If , we can set to and to anything because it will be multiplied by , so (we'll set to ). Our equation will be satisfied with these values since and is the gcd of and .

Now, let's try to find of the equation based in the solutions of the equation . In the lesson of modular arithmetic, we learn that . Substituting this value into the second equation gives us the following:

So and is a solution to the equation .