Euclidean Algorithm and Extended Euclidean Algorithm in Python

The Euclidean Algorithm is a method for calculating the greatest common divisor (GCD) of two integers. With Python, we can use recursion to calculate the GCD of two integers with the Euclidean Algorithm.

def euclideanAlgorithm(a,b):
    if b == 0:
        return a
    return euclideanAlgorithm(b, a % b)

print(euclideanAlgorithm(10,25))

#Output:
5

We can also use Python to implement the Extended Euclidean Algorithm which finds integers x and y such that ax + by = gcd(a,b) with a recursive function.

def extendedEuclideanAlgorithm(a,b):
    if a == 0:
        return b, 0, 1
    gcd, u, v = extendedEuclideanAlgorithm(b % a, a)
    x = v - (b // a ) * u
    y = u
    return gcd, x, y

print(extendedEuclideanAlgorithm(10,25))

#Output:
(5, -2, 1)

Python allows us to implement complex algorithms to do various calculations. One such calculation is finding the greatest common divisor of two integers.

We can use the math gcd() function in Python to find the GCD of two integers, but implementing the Euclidean Algorithm which is used to find the GCD of two integers isn’t too bad.

We can use a recursive function to find the GCD of two numbers with the Euclidean Algorithm.

The Euclidean algorithm is a continual repetition which repeatedly divides the divisor of two integers by the remainder of that division until the resulting remainder is 0. The GCD is the last non-zero remainder in this algorithm.

With Python, we can implement this easily with a recursive function. For a recursive function, we need to define a base case, and a recursive step.

The base case is when the remainder after division between the two integers is 0. The recursive step is calling our algorithm with the divisor and remainder after division.

Below is a recursive function which takes two integers and returns the GCD using the Euclidean Algorithm.

def euclideanAlgorithm(a,b):
    if b == 0:
        return a
    return euclideanAlgorithm(b, a % b)

print(euclideanAlgorithm(10,25))
print(euclideanAlgorithm(90,33))
print(euclideanAlgorithm(1003,85))
print(euclideanAlgorithm(74,46))

#Output:
5
3
17
2

Implementing the Extended Euclidean Algorithm in Python

We can also implement the Extended Euclidean Algorithm in Python.

The Extended Euclidean Algorithm is an algorithm that finds integers x and y such that ax + by = gcd(a,b).

The Extended Euclidean Algorithm works in two steps. First, we need to find the GCD. So we use the Euclidean Algorithm to calculate the GCD of two integers. Then, to get x and y, we work backwards recursively.

For a recursive function, we need a base case and a recursive step.

In the extended Euclidean Algorithm, we have the same base case as above, as we are first finding the GCD of the two integers.

Then, we work backwards to get x and y.

To get x and y, at each step we can update the coefficients based on the following equations, where u and v are the coefficients which satisfy the equation (a % b) * u + b * v = GCD(a,b).

x = v - (a // b) * u
y = u

Below is a full implementation of the Extended Euclidean Algorithm in Python.

def extendedEuclideanAlgorithm(a,b):
    if b == 0:
        return a, 0, 1
    gcd, u, v = extendedEuclideanAlgorithm(b, a % b)
    x = v - (a // b ) * u
    y = u
    return gcd, x, y

print(extendedEuclideanAlgorithm(10,25))
print(extendedEuclideanAlgorithm(90,33))
print(extendedEuclideanAlgorithm(1003,85))
print(extendedEuclideanAlgorithm(74,46))

#Output:
(5, 1, -2)
(3, 11, -4)
(17, 12, -1)
(2, -8, 5)

Hopefully this article has been helpful for you to learn how to implement the Euclidean Algorithm and Extended Euclidean Algorithm to calculate greatest common divisors in Python.