GCD : Greatest Common Divisor

Definition

GCD(Greatest Common Divisor) of two or more given numbers, not all zero, is the highest possible number which divides them all.

$$GCD = \text{Multiplication of common factors}\\ \text{of all given numbers}$$

Lets see how we can code it in different ways.

Prime factorization

Its as per the definition and discussed above. So, one can say, let $A$ and $B$ be the two numbers with unique prime factorization given as\

$$A = p_1^{a_1} p_2^{a_2} p_3^{a_3}\dots{p_n^{a_n}}$$ $$B = p_1^{b_1} p_2^{b_2} p_3^{b_3}\dots p_n^{b_n}$$ $$gcd(A,B) = p_1^{min(a_1,b_1)} p_2^{min(a_2,b_2)} p_3^{min(a_3,b_3)}\dots p_n^{min(a_n,b_n)}$$

Here are a few examples.

Find the GCD of 36 and 24.

Lets do the prime factorization of both the numbers, 36 and 24.

$$36 = 2^2 \times 3^2$$ $$24 = 2^3 \times 3^1$$ $$gcd(24,36) = 2^{min(2,3)} 3^{min(2,1)} = 12$$

Find the GCD of 15, 21 and 6.

Again, start by prime factorization of all the given numbers.

$$6 = 2^1 \times 3^1$$ $$15 = 3^1 \times 5^1$$ $$21 = 3^1 \times 7^1$$ $$gcd(6,15,21) = 2^{min(1,0,0)} 3^{min(1,1,1)} 5^{min(0,1,0)} 7^{min(0,0,1)}\\ = 3$$

I will cover the factorization code and what are the efficient ways to do so in another article.

Euclid’s algorithm

The Euclid’s algorithm says that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number. Alternatively, the gcd of two numbers also divides their difference.

I will cover Euclid’s algorithm and Extended Euclid’s algorithm in another article. For time being just remember the following rules.

Following the above definition one can say\

$$gcd(a,0) = a$$ $$gcd(0,b) = b$$ $$gcd(a,b) = a \ \ \ \ \text{, if} \ a = b$$ $$gcd(a,b) = gcd(a-b,b) \ \ \, \ \text{, if} \ a > b$$ $$gcd(a,b) = gcd(a,b-a) \ \ \, \ \text{, if} \ b > a$$

After all, $a$’s greatest divisor is itself, which is also $a$ divisor of zero.

Lets convert this into some code,

Iterative Code

/**
 * An iterative function to return the GCD of two numbers
 *
 * @param a
 *            first number
 * @param b
 *            second number
 * @return gcd of a & b
 */
public static int iterativeGCD(int a, int b) {
  if (a == 0) {
    return b;
  } else if (b == 0) {
    return a;
  }

  while (a != b) {
    if (a > b) {
      a = a - b;
    } else {
      b = b - a;
    }
  }
  return a;
}

Recurvive Code

/**
 * A recursive function to return the GCD of two numbers
 *
 * @param a
 *            first number
 * @param b
 *            second number
 * @return gcd of a & b
 */
public static int recursiveGCD(int a, int b) {
  if (a == 0) { // Case 1
    return b;
  } else if (b == 0) { // Case 2
    return a;
  }

  if (a == b) { // Case 3
    return a;
  }

  if (a > b) { // Case 4
    return recursiveGCD(a - b, b);
  } else { // Case 5
    return recursiveGCD(a, b - a);
  }
}

Running an example for $A = 420$ and $B = 96$ we obtained the $gcd(A,B) = 12$ on 8th iteration.

When	A	B
Before 1st iteration	420	96
After 1st iteration	324	96
After 2nd iteration	228	96
After 3rd iteration	132	96
After 4th iteration	36	96
After 5th iteration	36	60
After 6th iteration	36	24
After 7th iteration	12	24
After 8th iteration	12	12

Faster Euclid’s Algorithm

One can look at another definition for Euclid’s Algorithm, which is as follows

$$gcd(a,b) = gcd(a,b \ \text{mod}\ a) \ \ \ \text{, if} \ b > a$$ $$gcd(a,b) = gcd(a \ \text{mod}\ b,b) \ \ \ \text{, if} \ a > b \ ,$$ $$\text{where} \ a \ \text{mod} \ b = a - b \lfloor{a/b}\rfloor$$

The code for the above is simple

Iterative Code

/**
 * A faster iterative function to return the GCD of two numbers
 *
 * @param a
 *            first number
 * @param b
 *            second number
 * @return gcd of a & b
 */
public static int iterativeFasterGCD(int a, int b) {

  while (a != 0 && b != 0) {
    if (a > b) {
      a = a % b;
    } else {
      b = b % a;
    }
  }
  return Math.max(a, b);
}

Recurvive Code

/**
 * A faster recursive function to return the GCD of two numbers
 *
 * @param a
 *            first number
 * @param b
 *            second number
 * @return gcd of a & b
 */
public static int recursiveFasterGCD(int a, int b) {
  if (a == 0) { // Case 1
    return b;
  } else if (b == 0) { // Case 2
    return a;
  }

  if (a == b) { // Case 3
    return a;
  }

  if (a > b) { // Case 4
    return recursiveGCD(a % b, b);
  } else { // Case 5
    return recursiveGCD(a, b % a);
  }
}

Running the same example for $A = 420$ and $B = 96$ we obtained the $gcd(A,B) = 12$ on 4th iteration.

When	A	B
Before 1st iteration	420	96
After 1st iteration	36	96
After 2nd iteration	36	24
After 3rd iteration	12	24
After 4th iteration	12	0

Why using mod is faster ?

Notice in normal Euclid’s algorithm, that we subtracted $A$’s value from $B$’s four times before $A$ became less than $B$. The same effect results from replacing $A$’s value by $A \ \text{mod} \ B$. (In this case, $420 \ \text{mod} \ 96 = 36$) Using this approach forces us to change the loop condition, however, as here what will eventually happen is that one of $A$ or $B$ will become zero. (Indeed, $A == B$ is impossible to arrive at unless $A == B$)

One Liner- Wait, What?

$$gcd(a,b) = gcd(b \ \text{mod} \ a,a) \ \ \text{, if} \ a \neq 0$$ $$gcd(a,b) = b \ \ \text{, if} \ a = 0$$

Tadda!!! What kind of sorcery is this, right? Why the hell I am telling you this right now? Well, its not new its same as above two algorithms. Two things to keep in mind, one $A \neq 0$. Another observation is whatever be the case $A > B$ or $B > A$, it doesn’t matter, we will be swapping the values on each recursive call and eventually we will reach the solution.

Now, don’t ask me everything why it will work, just take a pen paper and write down the values in each iteration.

/**
 * A recursive function to return the GCD of two numbers
 *
 * @param a
 *            first number
 * @param b
 *            second number
 * @return gcd of a & b
 */
public static int gcd(int a, int b) {
    return a == 0 ? b : gcd(b % a, a);
}

Stein’s Algorithm : Binary method

This method relies on the fact that for two non-negative integers we can compute GCD by only using subtraction and division by 2. There are five cases which needs to be implemented.

Note : Multiplication and division by $2$ can be done with bitwise operation.

If $a = b,$

$$gcd(a,b) = a \ ,if \ a = b$$

If $a = 0 \ or \ b = 0,$

$$gcd(a, 0) = a \ and \ gcd(0, b) = b$$

If $a \ and \ b \ are \ both \ even,$

$$gcd(a, b) = 2*gcd(a/2, b/2) \\ (as \ 2 \ is \ a \ common \ divisor)$$

If $a \ is \ even \ and \ b \ is \ odd \ or \ a \ is \ odd \ and \ b \ is \ even,$

$$gcd(a, b) = gcd(a/2, b) \\ gcd(a, b) = gcd(a, b/2)$$

If $both \ a \ and \ b \ are \ odd,$

$$gcd(a, b) = gcd((a-b)/2, b) \ ,if \ a > b \\ gcd(a, b) = gcd(a, (b-a)/2) \ ,if \ b > a \\ (difference \ of \ two \ odd \ numbers \ is \ even)$$

/**
 * A recursive function to return the GCD of two numbers
 *
 * @param a
 *            first number
 * @param b
 *            second number
 * @return gcd of a & b
 */
public static int gcd(int a, int b) {
    if (b == 0) return a;
    if (a == 0) return b;

    // a and b even
    if ((a & 1) == 0 && (b & 1) == 0) return gcd(a >> 1, b >> 1) << 1;

    // a is even, b is odd
    else if ((a & 1) == 0) return gcd(a >> 1, b);

    // a is odd, b is even
    else if ((b & 1) == 0) return gcd(a, b >> 1);

    // a and b odd, a >= b
    else if (a >= b) return gcd((a - b) >> 1, q);

    // a and b odd, a < b
    else return gcd(a, (b - a) >> 1);
}

Time Complexity:

$O(N*N)$ where $N$ is the number of bits in the larger number.

Or $O((\log(a)+\log(b))^2)$ the total number of steps is at most the sum of the numbers of bits of a and b. Since subtracting two numbers smaller than a and b costs $O(\log a+\log b)$ bit operations.

References and Further Readings

• Euclidean algorithm
• GCD