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.

- https://cryptohack.org/courses/modular/egcd/
- https://web.archive.org/web/20230511143526/http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html

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)