Fraction simplification
- Input
- MDC(36, 24)
- Expected output
- 12
Dividing both by the GCD of 12 simplifies 36/24 to 3/2; no smaller number divides both at once.
Carregando ferramenta… / Loading tool…
GCD of two numbers Euclidean algorithm
The Euclidean algorithm computes GCD(a, b) in O(log min(a,b)) steps by repeatedly replacing the pair (a, b) with (b, a mod b) until the remainder hits zero. It is one of the oldest algorithms in mathematics, described by Euclid around 300 BC, and still the fastest known method for the problem.
Dividing both by the GCD of 12 simplifies 36/24 to 3/2; no smaller number divides both at once.
Both are prime, so the only possible common divisor is 1: GCD = 1 confirms they are coprime.
9 divisions before the remainder hits zero, the maximum for 2-digit numbers, because 89 and 55 are consecutive Fibonacci numbers.
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.
They are two integers whose only common positive divisor is 1, like 8 and 9: no number greater than 1 divides both. They are also called relatively prime, even when neither number is prime on its own.
At most 5 times the digit count of the smaller number, by Lamé's theorem (1844); the actual worst case happens with pairs of consecutive Fibonacci numbers, such as 89 and 55, which require the maximum number of divisions possible for their size.
No: it requires positive integers greater than zero, up to 10³⁰ each. Mathematically GCD(a, 0) = a, but the tool rejects zero and negative values to avoid ambiguous input, showing a specific error for each case.
Numbers
All values stay in your browser. No data is sent to any server.