GCD & LCM Calculator

Continue in the tool

More pages for this tool

GCD of two numbers Euclidean algorithm

GCD of Two Numbers, Euclidean Algorithm

The Euclidean algorithm computes GCD(a, b) in O(log min(a,b)) steps, one of the oldest and most efficient algorithms in mathematics.

Euclidean algorithm step by step

GCD(48, 18): 48 = 2×18 + 12 → GCD(18, 12): 18 = 1×12 + 6 → GCD(12, 6): 12 = 2×6 + 0 → GCD = 6.
The algorithm terminates when the remainder is zero. The last non-zero divisor is the GCD.

Examples

Fraction simplification

Input: MDC(36, 24)
Expected output: 12

36/24 simplifies to 3/2.

Coprime numbers

Input: MDC(17, 31)
Expected output: 1

GCD=1 means they are coprime.

Full tool FAQ

What is GCD?

GCD (Greatest Common Divisor) is the largest positive integer that divides all numbers in the set without a remainder. It can be found with the Euclidean algorithm or by comparing prime factorizations and taking the lowest power of each shared prime. For example, GCD(12, 18) = 6.

What is LCM?

What is the relationship between GCD and LCM?

How does the Euclidean algorithm work?

What are practical uses of GCD and LCM?

Does the tool support more than two numbers?

Why is zero not accepted?

What happens if the LCM is very large?

Frequently asked questions

What are coprime numbers?

Two integers are coprime (relatively prime) when their GCD is 1. E.g. 8 and 9 are coprime.

Does this page replace official or professional review?

No. It helps explain the scenario and use the tool more safely, but real decisions should consider official sources, full context and qualified guidance when needed.

Next steps