Greatest Common Divisor

The Greatest Common Divisor (GCD), sometimes known as the highest common factor, is the largest number which divides two positive integers (a,b).

How to calculate ?

There is several methods to obtain a GCD :

Divisors listing

The first method consist, as this names sounds for, list every divisor for each integers.

For a = 12, b = 8 , the divisors of a: {1,2,3,4,6,12} and the divisors of b: {1,2,4,8}. Comparing these two, then gcd(a,b) = 4.

This method is easy and can be quickly done for small integer but if the integers are a= 54213214, b=32541548 this can take a while.

Euclid's algorithm

This is a two step algorithm :

Do an Euclid's Division on the bigger integer (A) by the lower (B), keep the rest and B
If the rest = 0 then gcd = B else, do the step 1 again with A = B and B = rest.

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

Extended Euclid's Algorithm

The extended Euclidean algorithm is an algorithm for finding the greatest common divisor (GCD) of two integers and finding the coefficients of the linear combination of the two integers that give the GCD.

The extended Euclidean algorithm can be used to solve Diophantine equations, which are equations with integer solutions, and is also used in public key cryptography, such as the RSA algorithm, to find the modular inverse of an integer.

How it works ?

The extended Euclidean algorithm works by keeping track of the intermediate remainders and division results within the Euclid's algorithm and using them to calculate the coefficients.

At each step of the algorithm, the previous remainders and division results are used to calculate the new coefficients. The algorithm continues until the final remainder is zero.

def egcd(a,b):
    if b == 0:
        return a,0,1

    gcd, u1, v1 = egcd(b, a%b)

    u = v1 - (a//b) * u1
    v = u1

    return gcd, u, v

Resources

PreviousModular arithmetic NextFermat's little theorem

Last updated 2 years ago