Fraction simplification
- Input
- MDC(36, 24)
- Expected output
- 12
36/24 simplifies to 3/2.
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
Coprime numbers
- Input
- MDC(17, 31)
- Expected output
- 1
GCD=1 means they are coprime.
Full tool FAQ
GCD (Greatest Common Divisor) is the largest positive integer that divides all numbers in the set without a remainder. For example, GCD(12, 18) = 6.
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.