## Euclidean Algorithm for finding GCD

### How to find GCD (Greatest Common Divisor) of two numbers via coding? How to implement Euclidean algorithm in Python?

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, arr)
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