GCD and LCM
GCD and LCM of two or three integers, with the Euclidean algorithm unrolled line by line and the simplified fraction.
Result
6
- LCM
- 8640
- Simplified fraction
- 45 / 32
Euclidean algorithm
270 = 192 × 1 + 78 192 = 78 × 2 + 36 78 = 36 × 2 + 6 36 = 6 × 6 + 0
Note
The GCD is 6 and the LCM is 8640.
Calculation, assumptions and sources
OverviewGCD of two or three integers by the Euclidean algorithm, with the chain of divisions dividend = divisor × quotient + remainder down to the last non-zero remainder.
GCD of two or three integers by the Euclidean algorithm, with the chain of divisions dividend = divisor × quotient + remainder down to the last non-zero remainder. The LCM follows from GCD × LCM = a × b, and the fraction a/b is given simplified.
Method & formulasa = b × q + r, then GCD(a, b) = GCD(b, r)
The Euclidean algorithm replaces (a, b) with (b, r) while the remainder r is non-zero; the last non-zero remainder is the GCD. For two numbers, GCD × LCM = a × b gives the LCM and serves as a check. For three numbers this identity does not apply, and the calculation proceeds pairwise.
- GCD
- the largest integer dividing both numbers.
- LCM
- the smallest non-zero integer that both numbers divide.
- Coprime
- GCD equal to 1; the LCM is then the product of the two numbers.
Validity domainInputs: positive integers up to 90,000,000.
Inputs: positive integers up to 90,000,000. Decimals and negatives are refused; the GCD of negative numbers is that of their absolute values. GCD(0, b) is b by convention; GCD(0, 0) does not exist.