# GCD (Greatest Common Divisor)

Last modified: 2023-08-29

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

**in Python, we can easily compute GCD.**

`math`

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