LCM and GCD Combined Calculator

LCM and GCD explained with the Euclidean algorithm

The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides all of them without leaving a remainder. The Lowest Common Multiple (LCM) is the smallest positive integer that is divisible by all of them. These two values are closely related: for any two positive integers a and b, the product of the GCD and LCM equals the product of the two numbers (GCD x LCM = a x b). This relationship means you only need to compute one of them to derive the other.

The GCD has many practical uses. When simplifying a fraction, you divide both the numerator and denominator by their GCD. When two quantities need to be divided into equal groups, the GCD tells you the largest group size that works for both. When coordinating two repeating events, the LCM tells you when they will next occur at the same time. If a bus comes every 12 minutes and a train every 18 minutes, and they are both at the station at 9:00 AM, the LCM (36 minutes) tells you they will next coincide at 9:36 AM.

This calculator uses the Euclidean algorithm to find the GCD. The algorithm works by repeatedly replacing the larger number with the remainder when the larger is divided by the smaller, until the remainder reaches zero. The last non-zero remainder is the GCD. This is one of the oldest known algorithms in mathematics, dating back to Euclid around 300 BCE, and it is still the most efficient method for computing GCDs of moderate-sized integers. The calculator shows you each step of the algorithm so you can follow the process and use it to check manual working.

For three numbers, the GCD is computed by applying the algorithm twice: GCD(a, b, c) = GCD(GCD(a, b), c). The LCM for three numbers follows the same pattern: LCM(a, b, c) = LCM(LCM(a, b), c). The third input field on this calculator is optional. If you leave it blank, only two numbers are used. If you fill it in, all three are included in both the GCD and LCM calculations.

When GCD and LCM arise in everyday problems

Fractions are perhaps the most common context where GCD matters. Any time you need to simplify a fraction or find the lowest-terms form, you divide both parts by the GCD. For 48/72, the GCD is 24, so the simplified form is 2/3. When adding fractions with different denominators, you need the LCM of those denominators. To add 5/12 + 7/18, the LCM of 12 and 18 is 36, giving you 15/36 + 14/36 = 29/36. These operations are routine in school mathematics and practical calculations involving recipes, measurements, and proportions.

In scheduling, the LCM is the key tool. If a machine requires servicing every 8 days and another every 12 days, and both are serviced today, the LCM (24 days) is when you will next need to service both on the same day. This is useful for maintenance planning, synchronizing deliveries, scheduling recurring meetings, and any other repeating task where you want to find coinciding cycles.

The Euclidean algorithm step by step

The algorithm replaces the pair (a, b) with (b, a mod b) on each step. For example, GCD(48, 18): 48 = 18 x 2 + 12, then 18 = 12 x 1 + 6, then 12 = 6 x 2 + 0. Since the remainder is 0, GCD(48, 18) = 6. Each step is shown in the calculator output so you can trace the sequence. This transparency makes the calculator useful not just for getting answers but for understanding how the algorithm works, which is a common topic in computer science and discrete mathematics courses.

The algorithm is guaranteed to terminate because the remainder decreases at each step, and it reaches zero in a finite number of iterations. The number of steps is at most proportional to the number of digits in the smaller input, making it highly efficient. Even for inputs in the millions, the algorithm finishes in a fraction of a second.