15. GCD and LCM

The GCD (greatest common divisor) and the LCM (least common multiple) appear in OSN problems in many disguises: splitting items evenly, simplifying fractions, finding when two events repeat at the same time. This chapter covers how to compute them quickly.

Definitions

• GCD(a, b) is the largest number that divides both a and b exactly.
• LCM(a, b) is the smallest positive number that is divisible by both a and b.

Example for 12 and 18:

Greatest common divisor: 6. Least common multiple: 36.

The primary-school method — factor into prime numbers, take the smallest exponent for the GCD and the largest for the LCM — is correct, but slow: for a up to 10¹⁸, the factoring alone already takes far too long.

The Euclidean algorithm

The fast method is more than two thousand years old and uses only one property:

GCD(a, b) = GCD(b, a mod b), and GCD(a, 0) = a.

The reason: every common divisor of a and b also divides a − b, and therefore also divides a mod b. So the set of common divisors does not change, while the numbers shrink quickly.

A helpful picture: imagine an a × b rectangle that you want to cover with equal square tiles without cutting any. Cut off as many b × b squares as possible from one end; the leftover piece measures (a mod b) × b. The tiles that can cover the original rectangle are exactly the tiles that can cover the leftover — because the part that was cut off can certainly be covered. Repeating the cutting until nothing is left gives the largest tile size, which is the GCD.

Trace GCD(48, 18):

The answer is 6.

Recursive version:

long long fpb(long long a, long long b) {
    if (b == 0) return a;
    return fpb(b, a % b);
}

Loop version:

long long fpb(long long a, long long b) {
    while (b != 0) {
        long long sisa = a % b;
        a = b;
        b = sisa;
    }
    return a;
}

One more example, GCD(1071, 462):

The answer is 21. Notice how fast the numbers shrink: every two steps, the larger number is at least halved.

The number of steps is O(log min(a, b)) — even for numbers as large as 10¹⁸ it is fewer than 90 steps. The most "stubborn" pair is two consecutive Fibonacci numbers: for 1,134,903,170 and 701,408,733, the algorithm needs 43 steps, and that is already the worst case in the billions range. Compare that with the primary-school method, which has to factor both numbers first — for numbers that large, the factoring alone takes far longer than the entire Euclidean algorithm.

LCM from the GCD

The property that connects the two:

GCD(a, b) × LCM(a, b) = a × b

So:

long long kpk(long long a, long long b) {
    return a / fpb(a, b) * b;        // divide first, then multiply
}

Check with the example 12 and 18: the GCD is 6, and 12 / 6 × 18 = 2 × 18 = 36 — it matches the table at the start of the chapter.

GCD and LCM of many numbers

Both can be computed in sequence:

long long g = a[0];
for (int i = 1; i < n; i++) g = fpb(g, a[i]);

long long k = a[0];
for (int i = 1; i < n; i++) k = kpk(k, a[i]);

The running GCD is safe, and can even stop early: once the value reaches 1, the result cannot change anymore.

The running LCM overflows quickly: the LCM of 1 through 20 is already 232,792,560, and the LCM of 1 through 43 already exceeds the long long limit. That is why problems usually ask for the LCM modulo some number, or restrict the data.

Problem patterns

Simplifying a fraction. Divide the numerator and denominator by their GCD.

long long g = fpb(p, q);
cout << p / g << "/" << q / g << "\n";

Repeating events. Lamp A blinks every 12 seconds, lamp B every 18 seconds. They blink together every LCM(12, 18) = 36 seconds.

Splitting evenly. There are 48 candies and 18 chocolates, distributed evenly with nothing left over among as many children as possible: GCD(48, 18) = 6 children.

Square tiles. A 48 × 18 cm floor is covered with equal square tiles without cutting any: the largest side is GCD(48, 18) = 6 cm.

Coprime numbers. a and b are called coprime if GCD(a, b) = 1. This is a condition that comes up often, for example with the modular inverse.

The extended Euclidean algorithm

An advanced version that not only computes the GCD, but also finds x and y satisfying:

a·x + b·y = GCD(a, b)

long long fpb_luas(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = fpb_luas(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

For example, for a = 3 and b = 7: the algorithm produces x = -2 and y = 1, and indeed 3 × (−2) + 7 × 1 = 1. Since the term 7 · y contributes nothing modulo 7, this means 3 × (−2) ≡ 1 (mod 7), so the inverse of 3 modulo 7 is −2, which is normalized to ((-2 % 7) + 7) % 7 = 5. Check: 3 × 5 = 15 = 2 × 7 + 1. Correct.

What it is for: finding the modular inverse when the modulus is not a prime number, so Fermat's little theorem (Chapter 14) does not apply. If GCD(a, m) = 1, then from a·x + m·y = 1 we get a·x ≡ 1 (mod m), so x is the inverse of a.

Homework

Most common mistakes

OSN tips

Recognize the GCD and LCM cues in the problem statement. These two words rarely appear as-is in OSN problems; what appears is the story.

Write the LCM as a / fpb(a, b) * b, not a * b / fpb(a, b). Both are mathematically correct, but the second form computes a * b first and can overflow even when the LCM itself is small. Dividing first always works exactly, because the GCD always divides a exactly.

The LCM can explode, the GCD never does. The GCD is never larger than the smallest number, but the LCM of several numbers can grow very fast: the LCM of 1 through 20 alone is already more than 2 × 10⁸. If a problem asks for the LCM of many numbers without a modulo, check the constraints — often what is actually asked is the answer modulo something, or the constraints really are small.

The Euclidean algorithm is very fast, so do not replace it. Finding the GCD by trying every divisor takes up to 10⁹ steps for numbers that large; Euclid finishes in tens of steps. The difference is not an optimization, but the difference between possible and impossible.

The GCD of a sequence of numbers is computed step by step. fpb(a, b, c) equals fpb(fpb(a, b), c), and this property holds for any number of values. The correct initial value is 0, because fpb(0, x) = x. Starting from 1 is a mistake that makes every answer 1.

Differences are a hidden hint. A problem that says "all the numbers leave the same remainder when divided by d" is really talking about differences: d must divide every difference exactly. This change of viewpoint turns a problem that looks hard into a single line of GCD.

Summary

• GCD(a, b) is the greatest common divisor, LCM(a, b) the least common multiple.
• Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), stopping when b = 0. It takes O(log min(a, b)) steps.
• The LCM is computed from the GCD: a / fpb(a, b) * b — divide first, then multiply, so it does not overflow.
• The running GCD is safe and can stop as soon as it reaches 1; the running LCM overflows quickly.
• The problem patterns: simplifying fractions (GCD), events repeating together (LCM), splitting evenly into as many groups as possible (GCD), the largest square tile (GCD).
• Extended Euclid finds x and y in a·x + b·y = GCD(a, b), and is used for the modular inverse when the modulus is not prime.

OSN-style exercises

None of the following three problems mention the words GCD or LCM. That is exactly what is being practiced: recognizing the intended tool from the wording of the story.

The skeletons for all three are in exercises/15/osn/.

Problem 1 — Largest Square Tile

A rectangular floor measuring P × L centimeters is to be covered with square tiles that are all the same size. Tiles may not be cut, may not overlap, and the floor must be covered completely with nothing left over.

Determine the largest tile side that satisfies these conditions, and how many tiles are used.

Input format. One line containing two integers P and L.

Output format. One line containing two integers: the largest tile side and the number of tiles, separated by a single space.

Constraints. 1 ≤ P, L ≤ 10⁹.

Sample input

12 18

Sample output

6 6

Explanation. The tile side must divide both 12 and 18 exactly. The possible choices are 1, 2, 3, and 6; the largest is 6. With 6 × 6 tiles, the floor is divided into 2 × 3 = 6 tiles.

The skeleton: exercises/15/osn/01-ubin-persegi.cpp

Problem 2 — Common Multiples

A factory has two machines. The first machine beeps at every second that is a multiple of X, and the second machine at every second that is a multiple of Y. Count how many seconds between second A and second B, inclusive, both machines beep at the same time.

Input format. One line containing four integers A, B, X, and Y.

Output format. One line containing the number of such seconds.

Constraints.

• 1 ≤ A ≤ B ≤ 10¹⁸
• 1 ≤ X, Y ≤ 10⁹

Sample input

1 100 4 6

Sample output

8

Explanation. Both machines beep together at seconds 12, 24, 36, 48, 60, 72, 84, and 96 — there are eight. Note the constraint on B: checking every second one by one is impossible.

The skeleton: exercises/15/osn/02-kelipatan-bersama.cpp

Problem 3 — Common Divisor of Differences

You are given N integers. Find the largest positive integer d such that all the numbers leave the same remainder when each is divided by d.

If all the numbers are exactly equal, d can be any value; for that case print 0.

Input format. The first line contains an integer N. The second line contains N integers.

Output format. One line containing the largest d, or 0 for the special case above.

Constraints.

• 2 ≤ N ≤ 200,000
• 1 ≤ Aᵢ ≤ 10¹⁸

Sample input

3
5 11 17

Sample output

6

Explanation. With d = 6, all three numbers leave remainder 5. There is no larger d that gives the same remainder for all three.

The skeleton: exercises/15/osn/03-pembagi-selisih.cpp

Stuck or already done? Open the homework solutions page.