LCM and GCD Calculator
Find the LCM and GCD (HCF) of two or more numbers of any size, with prime factorisations and Euclidean algorithm steps.
This guide is not yet available in your language and is shown in English.
Tool guide
What this tool does
The LCM and GCD Calculator finds the least common multiple and greatest common divisor of any list of whole numbers, however long. It shows each number’s prime factorisation, the steps of the Euclidean algorithm and the Bézout identity for a pair of numbers.
The greatest common divisor (GCD, also called the highest common factor or HCF) is the largest number that divides every number in a list, and the least common multiple (LCM) is the smallest positive number that every number in the list divides into. You need the GCD to simplify fractions and ratios, and the LCM to add fractions with different denominators or to work out when repeating events line up again.
This calculator uses the Euclidean algorithm, which repeatedly replaces the larger number by its remainder until the remainder is zero, and then LCM(a, b) = |a × b| ÷ GCD(a, b). Both are applied pairwise across the list using arbitrary-precision integers, so 30-digit numbers work as well as small ones. For two numbers the algorithm’s steps and the Bézout coefficients are listed, and up to 50 numbers are factorised into primes so you can see where the answers come from.
How to use LCM and GCD Calculator
- Type or paste two or more whole numbers into the Numbers box, separated by commas, spaces or new lines.
- Read the GCD (HCF) and LCM cards; they update as you type.
- For exactly two numbers, follow the Euclidean algorithm steps in the working panel and read the Bézout identity.
- Check the prime factorisation table: the GCD uses the lowest shared power of each prime, the LCM the highest power.
- Download the factorisation table as CSV if you need it in a spreadsheet.
Tips for better results
- Two numbers are coprime when their GCD is 1; then their LCM is simply their product.
- To simplify a fraction, divide the numerator and denominator by their GCD.
- For timetable problems, such as buses every 12 and 18 minutes, the LCM (36) is when they next leave together.
Common use cases
- Simplifying fractions and finding common denominators.
- Working out repeating schedules, gear ratios and tile patterns.
- Number theory and competitive programming exercises with large integers.
- Checking modular inverses through the Bézout identity.
Common mistakes to avoid
- Multiplying the numbers to find the LCM; that only works when they are coprime.
- Including 0 in an LCM calculation: any list containing 0 has an LCM of 0.
- Confusing GCD and LCM in word problems: "largest equal groups" needs the GCD, "first time together again" needs the LCM.
Frequently asked questions
What is the relationship between GCD and LCM?
For two positive integers, GCD(a, b) × LCM(a, b) = a × b. For 84 and 126, the GCD is 42 and the LCM is 252, and 42 × 252 = 84 × 126 = 10,584.
How does the Euclidean algorithm work?
Divide the larger number by the smaller and keep the remainder. Replace the pair with (smaller, remainder) and repeat until the remainder is zero. The last non-zero remainder is the GCD.
What is the Bézout identity?
For any integers a and b there are integers x and y with ax + by = GCD(a, b). The calculator finds x and y with the extended Euclidean algorithm, which is how modular inverses are computed.
How large can the numbers be?
GCD and LCM work for numbers with hundreds of digits. Prime factorisations are shown for numbers below 10^24, and very hard composites may keep an unsplit part in brackets.
Feedback & suggestions
Help us improve LCM and GCD Calculator. We read every message.