Home › Math Calculators › GCD & LCM Calculator
Number Theory Precision
GCD & LCM Calculator (Euclidean Algorithm Solver)
Compute the Greatest Common Divisor (GCD / HCF) and Least Common Multiple (LCM) for two or more integers with step-by-step Euclidean division and prime factorizations.
Greatest Common Divisor (GCD)
6
Also known as HCF
Least Common Multiple (LCM)
144
LCM(A,B) = (|A × B|) / GCD
Euclidean Algorithm Steps:
48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0 → GCD is 6
18 = 12 × 1 + 6
12 = 6 × 2 + 0 → GCD is 6
Understanding GCD, LCM & Euclidean Division
The Greatest Common Divisor (GCD)—also called Highest Common Factor (HCF)—of two non-zero integers is the largest positive integer that divides both numbers without leaving a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is divisible by both numbers.
Core Number Theory Theorems
Euclidean Division: a = b × q + r, where 0 ≤ r < |b|
GCD Invariant: GCD(a, b) = GCD(b, r)
Fundamental Relation: GCD(a, b) × LCM(a, b) = |a × b|
How the Euclidean Algorithm Works
Devised around 300 BC by the Greek mathematician Euclid of Alexandria, this algorithm repeatedly divides the larger number by the smaller number and replaces the pair with the divisor and the remainder until the remainder is zero. The last non-zero remainder is the GCD.
Frequently Asked Questions
When the GCD of two numbers is 1, the numbers are said to be coprime or relatively prime (for example, 15 and 28). In this case, LCM is simply their direct product (15 × 28 = 420).
By mathematical convention, GCD and LCM are always positive integers regardless of the signs of the input numbers: GCD(-48, 18) = 6.
Educational Disclaimer: Local JavaScript math execution uses IEEE-754 double precision standard.