Greatest Common Divisor (Euclid's Algorithm)

Learn about Euclid's Algorithm, which can be used to calculate the GCD of two numbers.

We'll cover the following

Introduction

The Greatest Common Divisor (GCD) or the Highest Common Factor (HCF) of two numbers is the largest number that divides both of them. In other words, the Greatest Common Divisor (GCD) of two integers (a, b), denoted by gcd(a,b), is defined as the largest positive integer d, such that d | a and d | b, where x | y implies that x divides y.

A simple solution is to find all prime factors of both numbers and then find the intersection of all factors present in both numbers. Finally, return the product of the elements in the intersection.

According to the Euclid’s Algorithm:

gcd(A, B) = gcd(B, A % B) // recurrence for GCD
gcd(A, 0) = A // base case

Proof

Let’s discuss the proof of the recurrence.

  • Let us suppose, a = bq + r.

  • Let d be any common divisor of a and b, which implies d | a and d | b implies that d | (a – bq), which in turn implies that d | r.

  • Let e be any common divisor of b and r, which implies that e|b, e|r which in turn implies that e|(bq + r).

  • This way, we can get e | a. Hence, any common divisor of a and b must also be a common divisor of r, and any common divisor of b and r must also be a divisor of a, which implies that d is a common divisor of a and b if, and only if, d is a common divisor of b and r.

The GCD of more than 2 numbers, e.g., gcd(a,b,c) is equal to gcd(a,gcd(b,c)) and so on.

Solution

Before moving to the coding solution, let us look at the visualization below to understand the approach to solving this problem.

Now that you have a sense of how this approach will work, let’s see how this concept can be converted into code.

Press + to interact
#include <iostream>
using namespace std;
int gcd(int a, int b) {
  return (b == 0 ? a : gcd(b, a % b));
}
int main() {
  int a = 100, b = 20;
  int result;
  result = gcd(a,b);
  cout << result;
}

Explanation:

  • The above function, gcd(), accepts two numbers as input and provides the output. As we are using the % operator, the number of recursive calls required to reach the final result would be less than n, where n = max(a,b).
  • Euclid’s GCD algorithm runs in O(log(N)), where N = max(a,b).