Euclid's algorithm for finding the Greatest Common Divisor of two or more integers is based on the following observations:

  1. if \(x = y\) then

\[ gcd(x, y) = gcd(x, x) = x \]

  1. if \[x > y\] then

\[ gcd(x, y) = gcd(x - y, y) \]

proof: suppose that \(d\) is a divisor of \(x\) and \(y\) then \(x\) and \(y\) can be expressed as

\[ \begin{align*} x &= q_1d \\ y &= q_2d \end{align*} \]

But then

\[ x - y = q_1d - q_2d = d(q_1 - q_2) \]

Therefore \(d\) is a divisor of \(x - y\)

int gcd(int x, int y) {
  while (x != y) {
    if (x > y) {
      x -= y;
    } else {
      y -= x;
    }
  }
  return x;
}

Using the remainder operator instead of multiple subtraction operations is an improvement in performance however eventually one of \(x\) or \(y\) will become zero

\[ gcd(x, 0) = gcd(0, x) = x \]

int gcd(int x, int y) {
  while (x != 0 && y != 0) {
    if (x > y) {
      x %= y;
    } else {
      y %= x;
    }
  }
  return max(x, y);
}

By ensuring that \(x \geq y\) we can get rid of the if statement inside the while loop

int gcd(int x, int y) {
  if (x < y) {
    swap(x, y);
  }
  while (y != 0) {
    int remainder = x % y;
    x = y;
    y = remainder;
  }
  // at this point `gcd(x, y) = gcd(x, 0) = x`
  return x;
}

However if \(x < y\) the first iteration of the loop will actually swap the operands, e.g. when \(x = 3, y = 5\), \(remainder = 3 % 5 = 3\), \(x_{new} = 5\), \(y_{new} = 3\) therefore it's not necessary to make the initial swap

int gcd(int x, int y) {
  while (y != 0) {
    int remainder = x % y;
    x = y;
    y = remainder;
  }
  // at this point `gcd(x, y) = gcd(x, 0) = x`
  return x;
}

Example: finding the GCD of \(102\) and \(38\)

\[ \begin{align*} 102 &= 2 \cdot 38 + 26 \\ 38 &= 1 \cdot 26 + 12 \\ 26 &= 2 \cdot 12 + 2 \\ 12 &= 6 \cdot 2 + 0 \end{align*} \]

The last non-zero remainder is \(2\) thus the GCD is 2

Implementation

Recursive version

int gcd(int x, int y) {
  if (y == 0) {
    return x;
  }
  return gcd(y, x % y);
}

explanation