GCD & LCM Calculator — Step-by-Step Solutions

The GCD & LCM Calculator finds the Greatest Common Divisor and Least Common Multiple of two or more numbers. It uses the Euclidean algorithm and prime factorisation to compute results efficiently.

Enter your numbers and the calculator will show the GCD, LCM, prime factorisations, and step-by-step working. Useful for simplifying fractions, finding common denominators, and solving number theory problems.

Number A

Number B

Your calculations will appear here

How to Use the GCD & LCM Calculator

Enter two or more positive integers in the input fields, separated by commas if using a single field.
Click "Calculate" to find both the GCD and LCM instantly.
Review the step-by-step working, which shows the Euclidean algorithm and prime factorisation for each number.
Use the results to simplify fractions or find common denominators in further calculations.

Formula and Theory

The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of them without leaving a remainder. It is also called the highest common factor (HCF). The Euclidean algorithm computes the GCD efficiently: GCD(a, b) = GCD(b, a mod b), repeated until the remainder is zero. The last non-zero remainder is the GCD.

The least common multiple (LCM) of two or more integers is the smallest positive integer that is divisible by each of them. The relationship between GCD and LCM is given by the formula: LCM(a, b) = |a * b| / GCD(a, b). This means you only need to compute the GCD to derive the LCM.

Prime factorisation provides an alternative method. The GCD takes the lowest power of each common prime factor, while the LCM takes the highest power of every prime factor present in any of the numbers. For example, 12 = 2^2 * 3 and 18 = 2 * 3^2, so GCD = 2 * 3 = 6 and LCM = 2^2 * 3^2 = 36.

Worked Examples

Example 1: GCD using the Euclidean algorithm

Problem: Find the GCD of 48 and 18.

Solution: GCD(48, 18): 48 = 2 * 18 + 12. GCD(18, 12): 18 = 1 * 12 + 6. GCD(12, 6): 12 = 2 * 6 + 0. The last non-zero remainder is 6.

Answer: GCD(48, 18) = 6

Example 2: LCM from GCD

Problem: Find the LCM of 12 and 8.

Solution: First find GCD(12, 8) = 4. Then LCM = (12 * 8) / 4 = 96 / 4 = 24.

Answer: LCM(12, 8) = 24

Example 3: GCD of three numbers

Problem: Find the GCD of 24, 36, and 60.

Solution: GCD(24, 36) = 12. Then GCD(12, 60) = 12.

Answer: GCD(24, 36, 60) = 12

Example 4: Real-world application: simplifying a recipe ratio

Problem: A recipe calls for 150g flour and 225g sugar. Simplify the ratio.

Solution: Find GCD(150, 225). 225 = 1 * 150 + 75. 150 = 2 * 75 + 0. GCD = 75. Divide both: 150/75 = 2, 225/75 = 3.

Answer: The ratio simplifies to 2:3

Frequently Asked Questions

What is the difference between GCD and LCM?

The GCD is the largest number that divides both inputs evenly, while the LCM is the smallest number that both inputs divide into evenly. They are inversely related through the formula LCM(a, b) = (a * b) / GCD(a, b).

Why is the GCD useful for simplifying fractions?

Dividing both the numerator and denominator of a fraction by their GCD reduces the fraction to its simplest form. For example, 18/24 simplified by GCD(18, 24) = 6 gives 3/4.

What is the Euclidean algorithm?

It is an efficient method for computing the GCD. You repeatedly divide the larger number by the smaller and replace the larger with the remainder, continuing until the remainder is zero. The last non-zero remainder is the GCD.

Can I find the GCD of more than two numbers?

Yes. Compute the GCD of the first two numbers, then find the GCD of that result with the third number, and so on. The process works because GCD is associative: GCD(a, b, c) = GCD(GCD(a, b), c).

When would I use the LCM in everyday life?

The LCM is useful when scheduling events that repeat at different intervals. For example, if one bus comes every 12 minutes and another every 8 minutes, they will arrive together every LCM(12, 8) = 24 minutes.