GCD (Greatest Common Divisor)

The greatest common divisor is the largest number that divide two integers without a remainder. The Euclidean Algorithm is commonly used for computing GCD.

Basic

The following examples calculate the greatest common divisor of two given integers. Using gcd method of math in Python, we can easily compute GCD.

import math

math.gcd(2, 8) # result: 2

math.gcd(5, 15) # result: 5

math.gcd(28, 72) # result: 4

The following snippet shows how the GCD works with the last example above (gcd(28, 72)).

# Calculate a remainder of 72/28
72 % 28 = 16
# Calculate a remainder using the previous number 16
28 % 16 = 12
# Repeat...
16 % 12 = 4
12 % 4 = 0

We got the decimal 4 before the final result is zero. This is the greatest common remainder.

Extended Euclidean Algorithm

The Extended Euclidean Algorithm finds integer coefficients x and y as such that below, if we have values of a and b.

a * x + b * y = gcd(a, b)

The following Python script is an example to find the coefficients. It refers to this article.

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

    gcd, x1, y1 = egcd(b % a, a)

    x = y1 - (b//a) * x1
    y = x1
    return gcd, x, y

# example values given
a = 25031
b = 39125

print(egcd(a, b))

Co-prime Numbers

If all numbers given are primes, the following principle holds.

a = 2
b = 3
c = 5

gcd(a*b, a*c) # 2 (a)
gcd(b*a, b*c) # 3 (b)
gcd(c*a, c*b) # 5 (c)

References

• CryptoHack

• The Extended Euclidean Algorithm