Euclidean algorithm

The Euclidean algorithm finds the greatest common divisor (GCD) of two whole numbers: the largest number that divides both with nothing left over.

Explanation

A sheet of paper is 18 by 12 cm. We want to cut it into equal squares, as large as possible, with nothing left over. The side of a square must fit into 18 and into 12 a whole number of times. Try the sizes from 12 down: 12 doesn't fit into 18 a whole number of times, and neither do 11, 10, 9, 8 or 7. Then 6 fits into both, since 18 = 3 · 6 and 12 = 2 · 6, and the sheet becomes six squares of 6 by 6 after 7 checks. The number 6 is the greatest common divisor of 18 and 12.

Fig. 1. An 18 by 12 sheet cuts into six squares of 6 by 6, the largest that leave nothing over.

Take a sheet 75 by 21 cm. Counting down from 21 finds 3 after 19 checks. That is fine here, but problems give numbers up to 2 \cdot 10^9. Two neighbouring numbers, such as 2 000 000 000 and 1 999 999 999, have no common divisor except 1, so counting down checks about 2 \cdot 10^9 sizes. By the usual rule of thumb from time complexity, about 10^8 simple steps per second, that takes about 20 seconds. We need a way to make the sheet smaller without changing the answer.

Cut off the largest square you can, 21 by 21. Cutting off a square subtracts the short side from the long one, so a strip 75 − 21 = 54 by 21 is left. Suppose squares of some size cut the whole sheet with nothing left. Their side divides 75 and 21, so it also divides 54, and the same squares cut the strip. Squares that cut both the cut-off square and the strip also cut the whole sheet. So the 75 by 21 sheet and the 54 by 21 strip have the same answer.

Keep cutting the largest square from what is left until nothing is left. The last piece is a 3 by 3 square, so the answer for the whole sheet is 3. That took 8 cuts instead of 19 checks.

Fig. 2. Cutting one square at a time takes 8 cuts.

The sheet starts with a run of three squares of 21 and ends with a run of three squares of 3. Each run is cut one square at a time, though we could tell in advance how many squares of that size fit. On the sheet 2 000 000 000 by 1 999 999 999 this method cuts one square, leaves a strip 1 999 999 999 by 1, and then makes about 2 \cdot 10^9 cuts, as slow as counting down.

So the question is how many equal squares fit in a row along the long side, and what is left after them. That is division with remainder: 75 divided by 21 is 3 with remainder 12, because 75 = 3 · 21 + 12. Three squares go at once, and a strip 21 by 12 is left. The pair 75 and 21 becomes 21 and 12 in one step, and the big sheet from before now takes two steps.

This is the Euclidean algorithm: replace the two numbers by the smaller one and the remainder of the larger divided by the smaller, until the remainder is 0. The other number is then the greatest common divisor.

The sheet is 75 by 21, and the pair is 75 and 21.

Take the remainder: 75 = 3 · 21 + 12. Shift the pair: it becomes 21 and 12.

Take the remainder: 21 = 1 · 12 + 9. Shift the pair: it becomes 12 and 9.

Take the remainder: 12 = 1 · 9 + 3. Shift the pair: it becomes 9 and 3.

Take the remainder: 9 = 3 · 3 + 0. Shift the pair: it becomes 3 and 0. Stop at zero: the answer is 3.

Squares of 3 by 3 cut the whole sheet: 25 across and 7 down.

1/6

Fig. 3. The Euclidean algorithm on the 75 by 21 sheet.

Step through the Euclidean algorithm with the buttons or the arrow keys. Blue squares are cut in this step, and the pair below gives the sides of the strip that is left.

The pair ends as 3 and 0, so the greatest common divisor of 75 and 21 is 3, found in 4 steps instead of 8 cuts. The steps also split both sides into equal parts: 75 = 25 · 3 and 21 = 7 · 3.

Least common multiple

Two buses leave a stop together. One leaves every 18 minutes, the other every 12. When do they next leave together? The first bus leaves at minutes 18, 36, 54 and so on, and the first of these that 12 divides is 36. The smallest number that two numbers both divide is their least common multiple (LCM).

Fig. 4. The two buses next leave together at minute 36.

The GCD gives it without listing multiples. The first bus leaves at 18 · k minutes for k = 1, 2, 3 and so on, and 18 · k = 6 · 3 · k. For 12 = 6 · 2 to divide this number, 2 must divide 3 · k. 3 and 2 have no common divisor except 1, because a common divisor d would make 6 · d divide 18 and 12. So 3 · k is even only when k is even, and the smallest such k is 2, and the LCM is 18 · 2 = 36. That is 18 / 6 · 12: divide one number by the GCD and multiply by the other. For the sheet, the LCM of 75 and 21 is 75 / 3 · 21 = 525.

Reducing a fraction

To reduce the fraction 21/75, divide the top and the bottom by their GCD, 3, and get 7/25. It can't be reduced further: if some d larger than 1 divided both 7 and 25, then 3 · d would divide both 21 and 75, and 3 would not be their GCD.

Implementation

In code, the sides of the sheet are a and b, and a % b is the strip left over. Each step does three things:

1. Take the remainder: r = a % b.

2. Shift the pair: a = b, b = r.

3. Stop at zero: when b == 0, the answer is a.

If b is 0 from the start, the loop doesn't run and the answer is a. That is right: every number divides 0, so the GCD of 7 and 0 is 7. For two zeros the program prints 0, which is the usual convention.

The program reads two numbers a and b and prints their GCD. For the 75 by 21 sheet the input is:

75 21

The numbers can be up to 10^{18}, so they are kept in long long (64-bit, up to about 9 \cdot 10^{18}).

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    if (a < 0) a = -a;   // remove these two lines if the numbers are never negative
    if (b < 0) b = -b;

    while (b != 0) {     // stop at zero
        // take the remainder
        long long r = a % b;
        // shift the pair
        a = b;
        b = r;
    }

    cout << a << '\n';
}

Many solutions you will read write it as a recursive one-liner, a function that calls itself on a smaller pair:

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

Since C++17, the header <numeric> has std::gcd(a, b) and std::lcm(a, b). To compute the LCM yourself, write a / gcd(a, b) * b in long long. The LCM of two numbers up to 2 \cdot 10^9 can be up to 4 \cdot 10^{18}, which still fits in long long. For numbers up to 10^{18} the LCM may not fit even so, and std::lcm doesn't warn about it.

The loop takes O(\log \min(a, b)) steps. If b is at most half of a, the remainder is less than b, so less than half of a. If b is more than half of a, then a / b is 1, and the remainder a - b is less than half of a. Either way the remainder is less than half of a, and two steps later that remainder is the larger number of the pair. So every two steps at least halve the larger number. After the first step the larger number is the old smaller one (if a < b, the first step only swaps them). For numbers up to 2 \cdot 10^9 the slowest pair is 1836311903 and 1134903170, two neighbouring Fibonacci numbers, with 44 steps: at every step a / b is 1, so the numbers shrink as slowly as possible. For numbers up to 10^{18} it takes at most 85 steps.

GCD of many numbers

The GCD of several numbers is the largest number that divides all of them. Take the numbers one by one and keep g, the GCD of the numbers so far: g = gcd(g, x) for each new x. Start from g = 0, because the GCD of 0 and x is x, so the first number is taken as it is. For 84, 126 and 210, g goes 84, 42, 42, and the answer is 42.

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long g = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        g = gcd(g, x);
    }
    cout << g << '\n';
}

Each call takes O(\log C) steps, where $C$ is the largest number, so $n$ numbers take O(n \log C). The LCM of many numbers works the same way: start from 1 and replace l with l / gcd(l, x) * x. It grows fast, though: three numbers near 10^9, no two of which share a divisor larger than 1, give an LCM near 10^{27}, far beyond long long, so check that the problem promises an answer that fits.

Correctness proof

Each step replaces the pair $(a,b)$ by $(b,r)$, where $r$ is the remainder: a = q \cdot b + r. The step keeps the set of common divisors of the pair the same.

If $d$ divides $a$ and $b$, it divides a - q \cdot b = r, so $d$ is a common divisor of $b$ and $r$. If $d$ divides $b$ and $r$, it divides q \cdot b + r = a, so $d$ is a common divisor of $a$ and $b$. The two pairs have exactly the same common divisors, so they have the same greatest one.

Fig. 5. 3 divides 75 and 21, so it divides 75 − 3 · 21 = 12 too.

The loop ends with the pair $(g,0)$. Every number divides 0, so the common divisors of $g$ and 0 are the divisors of $g$, and the greatest of them is $g$ itself. By the argument above, it is also the greatest common divisor of the numbers we started with. The loop does end, because $b$ gets smaller at every step and never goes below 0.

Common mistakes

• Subtracting the smaller number instead of taking the remainder. On 1000000000000000000 1 the subtraction loop runs 10^{18} times and runs out of time, while the % loop takes one step. When a statement defines its function by subtraction, compute it with %.

• Dividing before checking for zero. while (a % b != 0) divides by zero on the input 7 0; check b == 0 before dividing.

• Forgetting negative numbers. The segment from (0, 0) to (4, −6) has gcd(4, −6) + 1 = 3 integer points, but a hand-written gcd returns −2, because C++ % keeps the sign of the left number, and the count comes out as −1. Take absolute values first or use std::gcd.

Similar algorithms

The extended Euclidean algorithm is needed for equations in whole numbers and for division by a number modulo m.

The school method finds the GCD from the common prime factors of both numbers. Prime factorization takes about O(\sqrt{n}) steps per number, far more than the Euclidean algorithm, so use it only when the problem asks about the factors themselves.

Practice