**Difficulty:** Medium, **Asked-in:** Microsoft, SAP Labs

**Key takeaways**

- The Euclidean algorithm is one of the oldest and most widely known algorithms. It is a method of computing the greatest common divisor (GCD) of two integers m and n.
- One of the best problems to learn problem-solving using recursion (Decrease and conquer strategy).
- It allows computers to do various simple number-theoretic tasks and serves as a foundation for more complicated algorithms in number theory.

Given two non-negative integers m and n, we have to find their greatest common divisor or GCD or HCF**.** It is the largest number which is a divisor of both m and n.

**Some important note**

- If any one of the integer is 0, then the GCD is the other number. It means, if m = 0, n != 0, then GCD(m, n) = n. Similarly, if m != 0, n = 0, then GCD(m, n) = m.
- When both m and n are 0, their GCD is undefined i.e. it can be any arbitrarily large number!
- If the smaller of the two numbers can divide the larger number then the GCD is the smaller number.

**Examples**

Input: m = 40, n = 32, Output: 8

Explanation: Integers 1, 2, 4, and 8 can divide both 40 and 30. Here 8 is the largest number, So, GCD (40, 30) = 10.

Input: m = 60, n = 40, Output: 20

Explanation: Integers 1, 2, 4, 5, 10 and 20 can divide both 60 and 40. Here 20 is the largest number, So, GCD (40, 30) = 10.

**Solution Idea**

As we have seen earlier, if a smaller number is divisible by the larger number then GCD is equal to the smaller number. Otherwise, GCD will be definitely smaller than the smaller of both numbers!

Suppose m > n and m are not divisible by n. Then we need to find the largest number x (x < m and x < n) which is divisible by both m and n. One observation is: Integers from n/2 + 1 to n - 1 will not be the GCD of both m and n because all these integers are not divisible by the smaller number n. So the first best guess for GCD would be x = n/2.

So one basic idea would be to run a loop from i = n/2 to 2 and check whether the current integer i divides both m and n. If yes, then the value is required GCD.

**Solution Pseudocode**

```
int gcd(int m, int n)
{
int minValue = min(m, n)
if (m % minValue == 0 && n % minValue == 0)
return minValue
for (int i = minValue/2; i >= 2; i = i - 1)
{
if (m % i == 0 && n % i == 0)
return i
}
return 1
}
```

Suppose m > n and GCD(m, n) = x. Based on the definition of the GCD, x is the largest number that divides both m and n. Now let's think about the difference m - n, which is smaller than the largest number!

If x divides m and n, then it would also divide the number m - n. Here is the simple proof: Suppose, m = ax and n = bx, where a > b. Then m - n = ax - bx = (a - b)x i.e. if we divide m - n with x, we will get the value a - b.

So the idea is: The common divisors of m and n would be the same as the common divisors of m - n, and n, where m and n are positive integers. GCD(m, n) = GCD(m - n, n).

This is a recursive equation where we solve the problem of finding the GCD of m and n using the smaller problem of finding the GCD of m - n and n. In other words: the greatest common divisor of two positive integers consists of replacing the larger number with the difference of the numbers and repeating this until the two numbers are equal: that is their greatest common divisor!

For example, to compute GCD(48,18), one proceeds as follows:

- GCD(48,18) = GCD(48 - 18,18) = GCD(30, 18)
- GCD(30, 18) = GCD(30 - 18, 18) = GCD(12, 18)
- GCD(12, 18) = GCD(12, 18 - 12) = GCD(12, 6)
- GCD(12, 6) = GCD(12 - 6, 6) = GCD(6, 6)

Now both numbers are equal, which is the base case => So GCD(48, 18)= 6. Note: This method can be very slow if one number is much larger than the other. Think!

**Recursive Pseudocode Implementation**

```
int gcd(int m, int n)
{
if (m == 0)
return n
if (n == 0)
return m
if (m == n)
return m
if (m > n)
return gcd(m - n, n)
return gcd(m, n - m)
}
```

**Iterative Pseudocode Implementation**

```
int gcd (int m, int n)
{
while (m != n)
{
if (m > n)
m = m - n
else
n = n - m
}
return m
}
```

The Euclidean algorithm is more efficient method of calculating GCD where the difference of the two numbers m and n is replaced by the remainder of the division of m by n. This is the idea of the Euclid algorithm: the gcd of two integers m and n with m > n equals the gcd of n and m mod n (the remainder when m is divided by n). In other words, GCD(m, n) = GCD(n, m mod n).

As we know from the idea of the mod operator, the remainder of the division of m by n can be written as m mod n. This is a recursive algorithm where we replace the input size (m, n) with (n, m mod n) repeatedly until the pair is (x, 0), where x is the greatest common divisor.

**Recursive Structure:** GCD(m , n) = gcd(n, m mod n)

**Base case:** GCD(m , n) = m, if n =0

Proof: If we divide m with n, we can write: m = kn + m mod n, where k is an integer (the quotient). Suppose any number x that divides both m and n, then we write it further:

=> m/x = (kn)/x + (m mod n)/x.

Here, m/x and (kn)/x are integers, then (m mod n)/x must be an integer. Hence any number x that divides both m and n should divide m mod n as well. For example, to compute gcd(48,18), the computation is as follows:

- GCD(48,18) = GCD(18, 48 mod 18) = GCD(18, 12)
- GCD(18, 12) = GCD(12, 18 mod 12) = GCD(12, 6)
- GCD(12, 6) = GCD(6, 12 mod 6) = GCD(6, 0)

Now we reached the base case => So GCD(48, 18)= 6.

**Recursive Pseudocode Implementation**

```
int gcd(int m, int n)
{
if (n == 0)
return m
return gcd(n, m % n)
}
```

**Iterative Pseudocode Implementation**

```
int gcd (int m, int n)
{
while (n)
{
m = m % n
swap(m, n)
}
return m
}
```

Extended Euclidean algorithm also finds integer coefficients x and y such that: For every pair of whole numbers m and n, there are two integers x and y such that mx + ny = gcd(m, n).

**Recursive Implementation**

```
int gcdExtended(int m, int n, int *x, int *y)
{
if (m == 0)
{
*x = 0
*y = 1
return n
}
int x1, y1
int gcd = gcdExtended(n%m, m, &x1, &y1)
*x = y1 - (n/m) * x1
*y = x1
return gcd
}
```

**Iterative Implementation**

```
int gcd(int m, int n, int &x, int &y)
{
*x = 1, *y = 0
int x1 = 0, y1 = 1
int m1 = m, n1 = n
while (n1)
{
int quotient = m1 / n1
int temp = x
*x = x1
x1 = temp - quotient * x1
temp = y
*y = y1
y1 = temp - quotient * y1
temp = m1
m1 = n1
n1 = temp - quotient * n1
}
return m1
}
```

- What would be the time complexities of the above approaches? What would be the worst-case scenario of the Euclidean algorithm?
- Explore the other methods of calculating the GCD of two numbers.
- Explore various properties related to the GCD.
- How do we find the LCM of two numbers using the GCD?
- Explore various applications of GCD computer science.

- Divide and Conquer Algorithm
- Binary Search Algorithm
- Merge Sort Algorithm
- Quick Sort Algorithm
- Analysis of Recursion
- Iteration vs Recursion Comparison

**Note:** Gradually we will update more exciting content to this blog!

**Enjoy learning, enjoy mathematics!**

Monty Hall Problem

There are 3 doors behind which are two goats and a car. You pick door 1 hoping for the car but don’t open it right away. Monty Hall, the game show host who knows what's behind the doors, opens door 3, which has a goat. Here's the game: do you want to pick door No. 2? Is it to your advantage to switch your choice?

Visual Proof: The Sum of Important Mathematical Series

The summation formulas are used to calculate the sum of the sequence. In this blog, we have discussed the visual proofs: the sum of numbers from 1 to n (arithmetic series), the sum of infinite geometric series, the sum of squares of numbers from 1 to n, etc.