🔢 Number Theory & Euclidean Division Solver
GCD & LCM Calculator
Calculate Greatest Common Divisor (GCD/GCF) and Least Common Multiple (LCM) with step-by-step Euclidean algorithm divisions and prime factorizations.
Sample Pairs:
GCD(48, 180)
GCD(24, 36)
Euclidean Classic (1071, 462)
Coprime Pair (35, 64)
Greatest Common Divisor (GCD)
12
Numbers share a common factor > 1
Least Common Multiple (LCM)
720
LCM(48, 180) = (48 × 180) / 12 = 720
Euclidean Algorithm Step-by-Step Division Table:
| Step | Dividend (a) | Divisor (b) | Quotient (q) | Remainder (r = a mod b) | Equation |
|---|
Prime Factorization Breakdown:
The Euclidean Algorithm and LCM Relationship
For any two positive integers $a$ and $b$, the Greatest Common Divisor and Least Common Multiple satisfy:
GCD(a, b) × LCM(a, b) = a × b
LCM(a, b) = (a × b) / GCD(a, b)
LCM(a, b) = (a × b) / GCD(a, b)
If $\text{GCD}(a, b) = 1$, the two integers are coprime (relatively prime), and their LCM is simply their product $a \times b$.