GCD and LCM — Number Best Friends

Real-world analogy

What is it?

GCD (Greatest Common Divisor) is the largest positive integer that divides two numbers without a remainder. LCM (Least Common Multiple) is the smallest positive integer that is divisible by both numbers. They are connected by the formula LCM(a,b) = a*b/GCD(a,b). Euclid's Algorithm computes GCD efficiently in O(log(min(a,b))) time.

Real-world relevance

GCD is used to simplify fractions (12/18 simplifies to 2/3 by dividing both by GCD=6), schedule events that repeat at different intervals, tile floors with the largest possible square tiles, and even in cryptography (RSA encryption uses GCD). LCM tells you when traffic lights will all be green at the same time, or when multiple bus routes will arrive simultaneously.

Key points

• What is GCD? — GCD (Greatest Common Divisor) is the largest number that divides both a and b with no remainder. GCD(12, 8) = 4 because 4 is the biggest number that goes into both 12 and 8 evenly. It is also called HCF (Highest Common Factor).
• Euclid's Algorithm — An ancient and brilliant method: GCD(a, b) = GCD(b, a%b). Keep replacing until b becomes 0, then a is the GCD. Example: GCD(48,18) → GCD(18,12) → GCD(12,6) → GCD(6,0) = 6. This is incredibly fast — it works in O(log(min(a,b))) time!
• Coding Euclid's Algorithm — Recursive: int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } Iterative: while(b) { int t = b; b = a%b; a = t; } return a; Both work great. The recursive version is shorter and elegant.
• __gcd() built-in — C++ has a built-in: __gcd(a, b) returns the GCD. With C++17, you can also use gcd(a, b) from . These save time in contests! But it is important to understand the algorithm behind it.
• What is LCM? — LCM (Least Common Multiple) is the smallest number that both a and b divide into. LCM(4, 6) = 12 because 12 is the smallest number divisible by both 4 and 6. It answers: when do two repeating events first happen together?
• LCM formula using GCD — LCM(a, b) = a * b / GCD(a, b). This beautiful formula connects LCM and GCD! But be careful with overflow: if a * b is too big for int or even long long, compute a / GCD(a,b) * b instead (divide first to keep numbers smaller).
• GCD of multiple numbers — To find GCD of 3+ numbers, chain it: GCD(a, b, c) = GCD(GCD(a, b), c). Same for LCM. Loop through an array: result = arr[0]; for(int i=1; i<n; i++) result = gcd(result, arr[i]);
• Common CP applications — GCD/LCM appear in: fraction simplification, number theory problems, finding repeating patterns, tile-fitting problems, gear/cycle problems, and many more. If a problem mentions 'divides evenly' or 'common', think GCD/LCM!

Code example

#include <bits/stdc++.h>
using namespace std;

// GCD using Euclid's algorithm (recursive)
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// LCM using GCD (divide first to avoid overflow)
long long lcm(int a, int b) {
    return (long long)a / gcd(a, b) * b;
}

int main() {
    int a, b;
    cin >> a >> b;
    
    cout << "GCD of " << a << " and " << b << ": " << gcd(a, b) << endl;
    cout << "LCM of " << a << " and " << b << ": " << lcm(a, b) << endl;
    
    // Simplify a fraction
    int num = a, den = b;
    int g = gcd(num, den);
    cout << "Fraction " << num << "/" << den << " simplifies to ";
    cout << num / g << "/" << den / g << endl;
    
    // GCD of an array
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    int arrayGCD = arr[0];
    long long arrayLCM = arr[0];
    for (int i = 1; i < n; i++) {
        arrayGCD = gcd(arrayGCD, arr[i]);
        arrayLCM = arrayLCM / gcd((int)arrayLCM, arr[i]) * arr[i];
    }
    
    cout << "GCD of array: " << arrayGCD << endl;
    cout << "LCM of array: " << arrayLCM << endl;
    
    return 0;
}

Line-by-line walkthrough

1. 1. int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } — This is Euclid's algorithm. If b is 0, the GCD is a. Otherwise, the GCD of a and b equals the GCD of b and the remainder of a/b. For GCD(48,18): GCD(18,12) → GCD(12,6) → GCD(6,0) → 6.
2. 2. long long lcm(int a, int b) { return (long long)a / gcd(a, b) * b; } — We divide a by gcd first (which always divides evenly) before multiplying by b. This prevents overflow. The cast to long long ensures we have enough room.
3. 3. int g = gcd(num, den); ... num/g ... den/g — To simplify a fraction, divide both numerator and denominator by their GCD. For 12/18: GCD=6, so 12/6=2 and 18/6=3. Result: 2/3.
4. 4. arrayGCD = gcd(arrayGCD, arr[i]); — To find the GCD of many numbers, use chaining: GCD(a,b,c) = GCD(GCD(a,b), c). Start with the first element, then fold in each subsequent element.
5. 5. arrayLCM = arrayLCM / gcd((int)arrayLCM, arr[i]) * arr[i]; — Same chaining for LCM, using the formula LCM(a,b) = a/gcd(a,b)*b at each step.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    int a, b;
    cin >> a >> b;
    int result = a * b / gcd(a, b);
    cout << "LCM: " << result << endl;
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Euclid's GCD Algorithm Explained (YouTube)
• GCD and LCM — CP Algorithms (CP-Algorithms)
• GCD/LCM Problems (Codeforces)