Euclidean Algorithm Calculator
Find the GCD of two numbers with full step-by-step Euclidean algorithm trace.
Inputs
First positive integer.
Second positive integer.
GCD
21
Steps Required
3
Step by step
Step 1
252 = 2 × 105 + 42
Step 2
105 = 2 × 42 + 21
Step 3
42 = 2 × 21 + 0
GCD
= 21
How it works
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.
Formula
Euclidean algorithm
gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a
- a
- First integer
- b
- Second integer
Frequently Asked Questions
How is this different from the GCF calculator?
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.
How fast is the Euclidean algorithm?
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.
You might also need
- Greatest Common Factor CalculatorCommonly used together
- Extended Euclidean Algorithm CalculatorCommonly used together
- Chinese Remainder Theorem CalculatorCommonly used together
- Modular Inverse CalculatorCommonly used together
- Divisibility CheckerAlso in Number Theory
- Fibonacci CalculatorAlso in Number Theory