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