How to Use This GCD LCM Calculator
This GCD and LCM calculator makes it easy to find the greatest common divisor and least common multiple of two or more positive integers. Simply enter your numbers into the input fields, and the calculator instantly displays both results along with detailed step-by-step workings.
Steps:
- Enter at least two positive integers in the input fields provided
- Click "+ Add Number" to include additional numbers (up to as many as you need)
- Remove extra inputs with the ✕ button on the right side of each field (minimum two inputs are always kept)
- View the GCD result (shown in blue) and LCM result (shown in green) in the display panel
- Scroll down in the display to see the full Euclidean algorithm steps and prime factorization of each number, the GCD, and the LCM
For two numbers, the calculator also verifies that GCD × LCM equals the product of the two numbers, a useful identity for checking your work.
What Is the Greatest Common Divisor?
The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides each of the given numbers without leaving a remainder. For example, the GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly.
Some common examples: GCD(8, 12) = 4, GCD(15, 25) = 5, GCD(7, 13) = 1. When two numbers share no common factors other than 1, they are called coprime or relatively prime. The pair (7, 13) is an example of coprime numbers.
The GCD is not limited to two numbers. You can find the GCD of three or more numbers by applying the operation iteratively: GCD(a, b, c) = GCD(GCD(a, b), c). For instance, GCD(12, 18, 30) = GCD(GCD(12, 18), 30) = GCD(6, 30) = 6.
What Is the Least Common Multiple?
The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of each of the given numbers. For example, the LCM of 4 and 6 is 12, because 12 is the smallest number that both 4 and 6 divide into evenly. Multiples of 4 are 4, 8, 12, 16, 20, ... and multiples of 6 are 6, 12, 18, 24, ...; the first number appearing in both lists is 12.
The LCM is closely related to the GCD through the identity: LCM(a, b) × GCD(a, b) = |a × b|. This means if you know one, you can always compute the other. For example, GCD(12, 18) = 6 and 12 × 18 = 216, so LCM(12, 18) = 216 / 6 = 36.
Like the GCD, the LCM can be extended to more than two numbers. LCM(a, b, c) = LCM(LCM(a, b), c). For instance, LCM(4, 6, 8) = LCM(LCM(4, 6), 8) = LCM(12, 8) = 24.
The Euclidean Algorithm
The Euclidean algorithm is one of the oldest and most efficient methods for computing the GCD of two numbers. Described by the Greek mathematician Euclid around 300 BCE in his work Elements, the algorithm is based on the principle that the GCD of two numbers also divides their difference.
The modern version uses division with remainder. Given two numbers a and b (where a ≥ b), we compute a = b × q + r, where q is the quotient and r is the remainder (0 ≤ r < b). Then GCD(a, b) = GCD(b, r). We repeat this process until the remainder becomes 0, at which point the last non-zero remainder is the GCD.
Example: Find GCD(252, 105).
- 252 = 105 × 2 + 42
- 105 = 42 × 2 + 21
- 42 = 21 × 2 + 0
The remainder is 0, so GCD(252, 105) = 21. This calculator shows every step of the Euclidean algorithm in the display panel so you can follow along with the calculation.
The Euclidean algorithm is remarkably efficient. Even for very large numbers, it converges quickly. In fact, the number of steps is at most roughly five times the number of digits in the smaller number (a result known as Lamé'e's theorem). This makes it practical for numbers with hundreds or even thousands of digits.
Prime Factorization Method
Prime factorization is another way to find the GCD and LCM. Every integer greater than 1 can be expressed as a unique product of prime numbers (the Fundamental Theorem of Arithmetic). For example, 12 = 2² × 3 and 18 = 2 × 3².
To find the GCD using prime factorization: take the lowest power of each prime that appears in every factorization. For 12 = 2² × 3 and 18 = 2 × 3², the GCD uses the lower power of 2 (which is 2¹) and the lower power of 3 (which is 3¹), giving GCD = 2 × 3 = 6.
To find the LCM using prime factorization: take the highest power of each prime that appears in any factorization. For the same numbers, the LCM uses 2² (the highest power of 2) and 3² (the highest power of 3), giving LCM = 4 × 9 = 36.
This calculator displays the prime factorization of each input number as well as the factorization of the GCD and LCM results, so you can see exactly how the common and uncommon prime factors contribute to each answer.
Applications of GCD and LCM
The GCD and LCM have wide-ranging applications across mathematics, computer science, and everyday life:
- Simplifying fractions: To reduce a fraction to its lowest terms, divide both the numerator and denominator by their GCD. For example, 18/24 simplifies to 3/4 because GCD(18, 24) = 6.
- Adding fractions: To add fractions with different denominators, find the LCM of the denominators to get the least common denominator (LCD). For 1/4 + 1/6, the LCD is LCM(4, 6) = 12.
- Scheduling: If a bus arrives every 15 minutes and a train every 20 minutes, they will both arrive together every LCM(15, 20) = 60 minutes.
- Cryptography: The RSA encryption algorithm relies heavily on number theory concepts related to GCD, including the extended Euclidean algorithm for finding modular inverses.
- Computer science: The Euclidean algorithm is used in hash table implementations, rational number arithmetic, and polynomial computations.
- Tiling and patterns: If you have tiles of size 6 cm × 6 cm and want to cover a rectangular floor without cutting tiles, the floor dimensions must be multiples of the tile size. The GCD helps determine the largest square tile that can evenly cover a rectangular area.
Frequently Asked Questions
What is the difference between GCD and LCM?
The GCD (Greatest Common Divisor) is the largest number that divides all given numbers evenly, while the LCM (Least Common Multiple) is the smallest number that is a multiple of all given numbers. They are related by the identity: GCD(a, b) × LCM(a, b) = a × b. For example, for the numbers 12 and 18, the GCD is 6 (the largest divisor they share) and the LCM is 36 (the smallest number both divide into).
Can I calculate GCD and LCM for more than two numbers?
Yes. This calculator supports two or more numbers. For the GCD, compute GCD(GCD(a, b), c) iteratively. For the LCM, compute LCM(LCM(a, b), c) iteratively. Simply click the "+ Add Number" button to include additional inputs.
What does the Euclidean algorithm actually do?
The Euclidean algorithm repeatedly replaces the larger of two numbers with the remainder after dividing by the smaller number. When the remainder reaches 0, the last non-zero remainder is the GCD. For example, to find GCD(48, 18): 48 = 18 × 2 + 12, then 18 = 12 × 1 + 6, then 12 = 6 × 2 + 0, so the GCD is 6. This process is guaranteed to terminate and is extremely efficient even for large numbers.
Why is prime factorization useful for GCD and LCM?
Prime factorization reveals the building blocks of each number. For the GCD, you take the lowest power of each prime common to all numbers. For the LCM, you take the highest power of each prime appearing in any number. This method makes it easy to see why the GCD and LCM are what they are, and it provides a clear visual understanding of the relationship between the numbers.
What does it mean if the GCD is 1?
If the GCD of two or more numbers is 1, those numbers are said to be coprime (or relatively prime). This means they share no common prime factors. For example, 8 and 15 are coprime because GCD(8, 15) = 1, even though neither 8 nor 15 is itself a prime number. Coprime numbers play an important role in number theory and cryptography.
Can I use zero as an input?
No. This calculator requires positive integers greater than zero. The GCD of zero and a non-zero number n is defined as |n|, and the LCM of zero and any number is 0, but these edge cases are not typically useful in practical applications. The calculator only accepts positive whole numbers (1, 2, 3, ...).
How large can the numbers be?
This calculator uses JavaScript's standard number type, which safely handles integers up to 2^53 − 1 (approximately 9 × 10^15). For most practical purposes, this range is more than sufficient. If you need to work with numbers larger than this, specialized arbitrary-precision libraries would be required.
What is the relationship between GCD, LCM, and the product of two numbers?
For any two positive integers a and b, the identity GCD(a, b) × LCM(a, b) = a × b always holds. This means if you know any three of these four values, you can calculate the fourth. The calculator displays this verification in the "GCD × LCM" and "Product of Numbers" panels when exactly two numbers are entered.