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