Find GCD of Two Numbers: Euclidean Algorithm

Blog cover image

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 the 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

A 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?

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

Enjoy learning, enjoy mathematics!

More from EnjoyMathematics

Follow us on:

LinkedinMedium

© 2020 EnjoyAlgorithms Inc.

All rights reserved.