🧩 What is GCD? (Greatest Common Divisor)

The GCD of two numbers is the largest number that divides both numbers exactly (without leaving a remainder).
For example:

  • Numbers: 12 and 18

  • Divisors of 12: 1, 2, 3, 4, 6, 12

  • Divisors of 18: 1, 2, 3, 6, 9, 18

  • GCD(12,18) = 6 ✅

🔹 How to Calculate GCD

  1. Using the Euclidean Algorithm:

    • If b = 0, GCD(a, b) = a

    • Otherwise, GCD(a, b) = GCD(b, a % b)
      This is an efficient method even for large numbers.

  2. Using Common Divisors Method (Naive):

    • List all divisors of both numbers

    • Choose the largest common one

🧮 What is LCM? (Least Common Multiple)

The LCM of two numbers is the smallest number that is divisible by both numbers.

  • Numbers: 12 and 18

  • Multiples of 12: 12, 24, 36, 48 …

  • Multiples of 18: 18, 36, 54 …

  • LCM(12,18) = 36 ✅

🔹 Relation Between GCD and LCM

There is a simple formula connecting GCD and LCM:

lcm

This formula allows you to find LCM easily if GCD is known.

💻 Coding Examples

Python

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

x, y = 12, 18
print("GCD:", gcd(x, y))
print("LCM:", lcm(x, y))

C++

#include <iostream>
using namespace std;

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

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int x = 12, y = 18;
    cout << "GCD: " << gcd(x, y) << endl;
    cout << "LCM: " << lcm(x, y) << endl;
    return 0;
}

Java

public class GCDLCM {
    static int gcd(int a, int b) {
        while(b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    public static void main(String[] args) {
        int x = 12, y = 18;
        System.out.println("GCD: " + gcd(x, y));
        System.out.println("LCM: " + lcm(x, y));
    }
}

📝 Step-by-Step Example

Numbers: 12 and 18

  1. GCD Calculation (Euclidean Algorithm)

    • Step 1: 18 % 12 = 6

    • Step 2: 12 % 6 = 0

    • GCD = 6

  2. LCM Calculation using formula

    • LCM = (12 × 18) / 6 = 36

✅ Result: GCD = 6, LCM = 36

💡 Tips & Tricks

  • GCD is useful in simplifying fractions.

  • LCM is commonly used to add/subtract fractions with different denominators.

  • For multiple numbers, GCD(a, b, c) = GCD(GCD(a, b), c)

  • Similarly, LCM(a, b, c) = LCM(LCM(a, b), c)

This is one of the fundamental DSA problems and is often asked in coding interviews because it tests both mathematical reasoning and programming skills.