GCD & LCM Calculator – Tutorial
On this page, you can find the logic, usage, and important details of the GCD & LCM Calculator calculator.
GCD & LCM — Concepts and Methods
This calculator finds the GCD (Greatest Common Divisor) and LCM (Least Common Multiple) of two integers using the Euclidean Algorithm.
1) Core Concepts
1.1 GCD — Greatest Common Divisor
The largest positive integer that divides both numbers without a remainder.
Example: GCD(12, 18)
- Divisors of 12: 1, 2, 3, 4, 6, 12
- Divisors of 18: 1, 2, 3, 6, 9, 18
- Common divisors: 1, 2, 3, 6 → largest is 6
1.2 LCM — Least Common Multiple
The smallest positive integer that is a multiple of both numbers.
Example: LCM(12, 18)
- Multiples of 12: 12, 24, 36, 48, 60, ...
- Multiples of 18: 18, 36, 54, 72, ...
- Smallest common multiple: 36
2) The Euclidean Algorithm
Listing all divisors is impractical for large numbers. The Euclidean Algorithm finds GCD very efficiently.
2.1 Core rule
GCD(a, b) = GCD(b, a mod b) (b ≠ 0)
"mod" is the remainder after division. E.g.: 18 mod 12 = 6 (since 18 = 12·1 + 6).
2.2 Why does it work?
Any d that divides both a and b also divides a − k·b.
Since a mod b = a − ⌊a/b⌋·b, d also divides a mod b.
Therefore the set of common divisors of {a, b} is identical to that of {b, a mod b},
so the greatest common divisor is the same.
2.3 Step-by-step example (18, 12)
- 18 mod 12 = 6 → GCD(18, 12) = GCD(12, 6)
- 12 mod 6 = 0 → GCD(12, 6) = GCD(6, 0)
- b = 0 → result: GCD = 6
3) LCM from GCD
LCM(a, b) = |a · b| / GCD(a, b)
3.1 Intuition via prime factorization
GCD takes the minimum exponent for each prime; LCM takes the maximum:
- 12 = 2² · 3¹
- 18 = 2¹ · 3²
- GCD = 2¹ · 3¹ = 6
- LCM = 2² · 3² = 36
- Check: |12 · 18| / 6 = 216 / 6 = 36 ✓
4) Special Cases
4.1 Negative numbers
GCD and LCM are defined for positive integers; absolute values are taken first. GCD(−12, 18) = GCD(12, 18) = 6.
4.2 Zero
- GCD(a, 0) = |a| — every integer divides 0, so a is the determining factor.
- LCM(a, 0) = 0 — the only multiple of 0 is 0.
- GCD(0, 0) is undefined in mathematics.
5) Applications
GCD is useful for:
- Simplifying fractions: 24/36 → GCD = 12 → 2/3
- Dividing into equal groups (largest equal share)
- Tiling and packaging problems
LCM is useful for:
- Period problems: "at what interval do two events coincide?"
- Finding a common denominator: 1/6 + 1/8 → LCM(6, 8) = 24
- Calendar cycles and repeating schedules
Note: For three or more numbers, apply iteratively: GCD(a,b,c) = GCD(GCD(a,b), c), and the same for LCM.