In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
For two integers `x`

, `y`

, the greatest common divisor of `x`

and `y`

is denoted `gcd(x, y)`

.

For example, the GCD of `8`

and `12`

is `4`

, that is, `gcd(8, 12) = 4`

## Euclidean Algorithm

The basic Euclidean algorithm for GCD is based on the below facts.

- If we subtract a smaller number from a larger (we reduce a larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
- Now instead of subtraction, if we divide the smaller number, the algorithm stops when we find remainder 0.

### Recursive

```
#!/usr/bin/env python3
# Function to return gcd of a and b
def gcd(a, b):
if a == 0 :
return b
return gcd(b%a, a)
```

### Iterative

```
#!/usr/bin/env python3
# Function to return gcd of a and b
def gcd(a, b):
while(a):
a, b = b%a, a
return b
```

### Time Complexity

Time Complexity: `O(log(min(a, b)))`

## Extended Euclidean Algorithm

Extended Euclidean algorithm also finds integer coefficients `x`

and `y`

such that:
`ax + by = gcd(a, b)`

```
#!/usr/bin/env python3
# Function for extended Euclidean Algorithm
def gcd_extended(a, b):
# Base Case
if a == 0 :
return b, 0, 1
gcd, x1, y1 = gcd_extended(b%a, a)
# Update x and y using results of recursive call
x = y1 - (b//a) * x1
y = x1
return gcd, x, y
```

- The extended Euclidean algorithm is particularly useful when a and b are co-prime (Co-prime numbers are those numbers that have their GCD as 1).

## Few Problems

Find GCD of nums more than two numbers (or array)

```
#!/usr/bin/env python3
arr = [2, 4, 6, 8]
gcd_num = gcd(arr[0], arr[1])
for i in range(2, len(arr)):
gcd_num = gcd(gcd_num, arr[i])
```

Time Complexity: `O(n * log(m))`

, where `n`

is length of array and `m`

is the smallest element of the array