# 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 <a href="#basic" id="basic"></a>

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

```shellscript
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)`**).

```shellscript
# 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 <a href="#extended-euclidean-algorithm" id="extended-euclidean-algorithm"></a>

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](https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/).

```shellscript
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 <a href="#co-prime-numbers" id="co-prime-numbers"></a>

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

```shellscript
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 <a href="#references" id="references"></a>

* [CryptoHack](https://cryptohack.org/courses/modular/egcd/)
* [The Extended Euclidean Algorithm](https://web.archive.org/web/20230511143526/http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html)