GCD and LCM Calculator
This calculator finds the greatest common divisor (GCD) and the least common multiple (LCM) of two whole numbers at the same time, updating as you type. The GCD is the largest number that divides both values without leaving a remainder, while the LCM is the smallest number that both values divide into. Together they are the workhorses behind reducing fractions, finding common denominators, and solving many number-theory and scheduling problems.
GCD (greatest common divisor)
LCM (least common multiple)
The GCD is computed with the Euclidean algorithm and the LCM is derived from LCM(a,b) = |a·b| / GCD(a,b).
Publicidad
How it works
The greatest common divisor is found with the Euclidean algorithm: repeatedly replace the pair (a, b) with (b, a mod b) until the second number becomes zero — the remaining first number is the GCD. For example, for 12 and 18: 18 mod 12 = 6, then 12 mod 6 = 0, so the GCD is 6. Once you have the GCD, the least common multiple follows directly from the identity LCM(a, b) = |a · b| / GCD(a, b). For 12 and 18 that is (12 · 18) / 6 = 216 / 6 = 36. This division-based route is far faster than listing every divisor or multiple by hand.
Publicidad
Preguntas frecuentes
- What is the greatest common divisor (GCD)?
- The greatest common divisor of two numbers is the largest whole number that divides both of them without leaving a remainder. For example, the GCD of 12 and 18 is 6, because 6 divides both 12 and 18 exactly and no larger number does. It is also called the greatest common factor (GCF) or highest common factor (HCF).
- What is the least common multiple (LCM)?
- The least common multiple of two numbers is the smallest positive number that is a multiple of both. For example, the LCM of 12 and 18 is 36, because 36 is the first number that appears in both the 12 times table and the 18 times table. It is used to find a common denominator when adding fractions.
- How does the Euclidean algorithm find the GCD?
- The Euclidean algorithm repeatedly replaces the pair (a, b) with (b, a mod b), where "a mod b" is the remainder of dividing a by b, until the second number becomes zero. The remaining first number is the GCD. For 48 and 18: 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the GCD is 6.
- How are the GCD and LCM related?
- For any two whole numbers a and b, the product of the GCD and the LCM equals the absolute value of their product: GCD(a, b) × LCM(a, b) = |a · b|. So once you know the GCD, you can find the LCM instantly with LCM(a, b) = |a · b| / GCD(a, b), which is exactly how this calculator works.
- What if one of the numbers is zero?
- By convention, the GCD of a number and zero is the number itself, so GCD(n, 0) = n. The LCM, however, is defined as zero whenever either input is zero, because zero is the only common multiple of zero and any other number. This calculator returns 0 for the LCM in that case.