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

2. if $x>y$ then

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

But then

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

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\ge 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$, $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$

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