# 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.

``````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)
``````