Find the GCD of two numbers with full step-by-step Euclidean algorithm trace.
The Euclidean algorithm finds the greatest common divisor (GCD) of two integers by repeated division. At each step, replace the larger number with the remainder of dividing the larger by the smaller: gcd(a, b) = gcd(b, a mod b). When the remainder is 0, the last non-zero remainder is the GCD. The algorithm terminates in at most O(log(min(a,b))) steps.
Euclidean algorithm
gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a
The GCF calculator computes the result directly. This calculator shows every step of the Euclidean algorithm — each division, quotient and remainder — making it a learning tool for understanding the process.
It takes at most O(log(min(a,b))) steps. The worst case is consecutive Fibonacci numbers, where each step reduces the pair by approximately the golden ratio.