# Find GCD of Two Numbers: Euclidean Algorithm

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.

### Understanding the Problem

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.

### Brute Force Approach

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

### Decrease and Conquer approach: Decreasing input size by the difference of both numbers

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

### Efficient Approach 2: Euclidean algorithm

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

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

### Critical Ideas to Think!

• 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.

### Similar blogs to explore

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

Enjoy learning, enjoy mathematics!

Share on social media:

© 2020 Code Algorithms Pvt. Ltd.