GCD & LCM Calculator

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are two of the most useful tools in number theory. They help simplify fractions, solve ratio problems, schedule repeating events, and much more.

Greatest Common Divisor (GCD)

The GCD of two or more integers is the largest positive integer that divides each of them without a remainder. It is used to reduce fractions to their simplest form. For example, the fraction 48/18 can be simplified by dividing both numerator and denominator by their GCD, 6, giving 8/3.

Least Common Multiple (LCM)

The LCM of two or more integers is the smallest positive integer that is divisible by each of them. It is useful for finding common denominators when adding fractions, or for scheduling events that repeat at different intervals. For example, if one bus arrives every 4 minutes and another every 6 minutes, they will both arrive together every 12 minutes (the LCM of 4 and 6).

The Euclidean Algorithm

The Euclidean algorithm is one of the oldest and most efficient methods for computing the GCD of two numbers. Instead of factoring the numbers, it repeatedly replaces the larger number with the remainder of dividing the two numbers. This process continues until the remainder is zero. The last non-zero remainder is the GCD.

GCD and LCM Relationship

For any two positive integers a and b:

This means you can always find the LCM if you know the GCD, and vice versa.