Enter data
Education- Euclidean algorithm
- Prime factors
- Divisors and multiples
Result
CalcCoreWhat the GCD and LCM calculator does
The calculator finds the GCD (greatest common divisor) and the LCM (least common multiple) of two or more natural numbers (up to 20 numbers, each up to 18 digits) and shows the solution by one of three methods: the Euclidean algorithm, prime factors or going through divisors and multiples. A separate mode factors a number into primes and shows all its divisors with their count and sum.
What are GCD and LCM
The GCD is the largest natural number that divides all the given numbers without a remainder. The LCM is the smallest natural number divisible by each of the given numbers. For 12 and 18: GCD = 6, LCM = 36. For two numbers GCD · LCM = a · b always, that is 6 · 36 = 216 = 12 · 18.
The Euclidean algorithm
Divide the larger number by the smaller one, then the smaller by the remainder, and so on until the remainder is zero. The last nonzero remainder is the GCD. For 48 and 18: 48 = 2 · 18 + 12, 18 = 1 · 12 + 6, 12 = 2 · 6 + 0, so GCD = 6 and LCM = 48 · 18 / 6 = 144.
For several numbers GCD and LCM are computed step by step: GCD(a, b, c) = GCD(GCD(a, b), c) and LCM(a, b, c) = LCM(LCM(a, b), c). For example, for 12, 18 and 30: GCD = 6, LCM = 180.
Prime factors
Factor every number into primes and build a table of exponents. For the GCD take the common primes with the smallest exponents, for the LCM all primes with the largest ones. For 12 = 2² · 3, 18 = 2 · 3² and 30 = 2 · 3 · 5 we get GCD = 2 · 3 = 6 and LCM = 2² · 3² · 5 = 180.
Divisors and multiples
This is the school method for small numbers. The divisors of 12 are 1, 2, 3, 4, 6, 12, of 18 — 1, 2, 3, 6, 9, 18; the common divisors are 1, 2, 3, 6 and the largest is 6. The multiples of 18 are 18, 36; the number 36 is divisible by 12, so LCM = 36.
Factorization and divisors
In the “Factors and divisors” mode the number is factored into primes, and from the factorization the number of divisors τ = (e₁ + 1)(e₂ + 1)… and the sum of divisors σ = Π (p^(e+1) − 1)/(p − 1) are computed. For 360 = 2³ · 3² · 5 we get τ = 4 · 3 · 2 = 24 and σ = 15 · 13 · 6 = 1170. Large numbers (up to 18 digits) are factored by a fast algorithm, so the answer appears at once.
Where GCD and LCM are used
The GCD is needed to reduce a fraction (numerator and denominator are divided by their GCD) and to split several quantities into equal groups of the largest size. The LCM is needed for a common denominator when adding fractions and in repeating-event problems: if one event repeats every 12 days and another every 18, they coincide every 36 days.
All calculations are exact: numbers are handled as integers, and the LCM is never rounded, even for long numbers.
FAQ
What is the GCD?
The greatest common divisor is the largest natural number that divides all the given numbers without a remainder. For example, GCD(12, 18) = 6.
What is the LCM?
The least common multiple is the smallest natural number divisible by each of the given numbers. For example, LCM(12, 18) = 36.
How are GCD and LCM related?
For two numbers GCD(a, b) · LCM(a, b) = a · b. So LCM = a · b / GCD. The calculator shows this check.
How do I find the GCD of two numbers?
The fastest way is the Euclidean algorithm: divide the larger number by the smaller one, then the smaller by the remainder, until the remainder is zero. The last nonzero remainder is the GCD. For 48 and 18 it is 6.
How do I find the GCD and LCM of three or more numbers?
Step by step: GCD(a, b, c) = GCD(GCD(a, b), c), LCM(a, b, c) = LCM(LCM(a, b), c). For 12, 18 and 30 we get GCD = 6, LCM = 180.
Which numbers are called coprime?
Numbers whose GCD is 1: they have no common divisors except one. For example, 8 and 15. For such numbers the LCM equals the product.
How do I find the LCM through prime factors?
Factor the numbers into primes and take every prime with its largest exponent. For 12 = 2² · 3 and 18 = 2 · 3² the LCM is 2² · 3² = 36.
How many numbers can I enter?
From two to twenty natural numbers, each up to 18 digits. Separate them with a space, a semicolon or a comma and a space.
Why is “12,5” not accepted?
Because a comma without a space looks like a decimal number, and GCD and LCM are only defined for natural numbers. Write “12 5” or “12; 5”.
How do I factor a number into primes?
Divide the number by the smallest primes until 1 remains. For 360 = 2³ · 3² · 5. In the “Factors and divisors” mode the calculator shows these divisions and all the divisors.
How many divisors does a number have?
If n = p₁^e₁ · p₂^e₂ · …, the number of divisors is (e₁ + 1)(e₂ + 1)… For 360 it is 4 · 3 · 2 = 24.
Does the calculator work with very large numbers?
Yes, up to 18 digits. GCD and LCM are computed exactly, and large numbers are factored with a fast algorithm that includes a primality test.