Euclidean (GCD)

Introduction

Given two non-negative integers $a$ and $b$ , we want to find their greatest common divisor (GCD), that is, the largest positive integer that divides both numbers.

For example:

$\text{GCD}(2, 4) = 2$
$\text{GCD}(6, 9) = 3$

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

1

CODEFORCESRow GCD

Rating: 1600

\text{GCD}(7, 10) = 1

Formally,

\text{GCD}(a, b) = \max \{k > 0 : (k \mid a) \text{ and } (k \mid b)\}

Here, the symbol $\mid$ means divisibility. For example, $k \mid a$ means that $k$ divides $a$ .

Algorithm

The Euclidean algorithm is based on several simple observations.

Observation 1

\text{GCD}(x, 0) = \text{GCD}(0, x) = x

If one of the numbers is zero, then the GCD is the other number.

Observation 2

\text{GCD}(a, b) = \text{GCD}(b, a)

The order of the numbers does not matter.

Observation 3

Assume $b \leq a$ . Then:

\text{GCD}(a, b) = \text{GCD}(a - b, b)

Indeed, subtracting $b$ from $a$ does not change the common divisors.

If we repeat this subtraction many times, we eventually get the remainder of dividing $a$ by $b$ . So a faster version is:

\text{GCD}(a, b) = \text{GCD}(a \bmod b, b)

Using this idea, we get the main recursive formula:

\text{GCD}(a, b) = \begin{cases} a, & \text{if } b = 0 \\ \text{GCD}(b, a \bmod b), & \text{otherwise} \end{cases}

Implementation

Recursive Solution

Iterative Solution

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int gcd(int a, int b) {
    while (b != 0) {
        a %= b;
        swap(a, b);
    }
    return a;
}