21
1,260
0
1=yes, 0=no
2
21
12
5
3
252
105
2
42
105
42
2
21
42
21
2
0
0
0
0
0
0
0
0
0
0
0
0
0
21
1,260
0
1=yes, 0=no
2
21
12
5
3
252
105
2
42
105
42
2
21
42
21
2
0
0
0
0
0
0
0
0
0
0
0
0
0
Euclid's Algorithm is one of the oldest and most elegant algorithms in mathematics, dating back to around 300 BCE in Euclid's Elements (Book VII, Propositions 1-2). It computes the Greatest Common Factor (GCF) of two integers through a sequence of divisions, where each step replaces the larger number with the remainder of dividing the two.
The algorithm is based on the fundamental identity:
$$\text{GCF}(a, b) = \text{GCF}(b, a \bmod b)$$
This works because any common divisor of $$a$$ and $$b$$ must also divide $$a - qb = r$$ (the remainder), and vice versa. By repeatedly applying this reduction, the numbers shrink until the remainder reaches zero, at which point the last nonzero remainder is the GCF.
Our calculator displays every step of the algorithm — the dividend, divisor, quotient, and remainder — so you can trace the entire computation. This step-by-step visibility makes it an invaluable learning tool for students studying number theory, and a practical verification tool for professionals working with modular arithmetic, cryptographic key generation, or Diophantine equations.
The algorithm's efficiency is remarkable: it requires at most $$2\log_2(\min(a,b))$$ steps, making it $$O(\log n)$$ — far superior to brute-force factor enumeration. The worst case occurs with consecutive Fibonacci numbers, which produce quotients of 1 at every step, maximizing the number of iterations.
The algorithm proceeds as follows:
Step 1: Divide the larger number by the smaller: $$a = b \cdot q_1 + r_1$$
Step 2: If $$r_1 = 0$$, then $$\text{GCF} = b$$. Otherwise, replace: $$b = r_1 \cdot q_2 + r_2$$
Step 3: Continue: $$r_1 = r_2 \cdot q_3 + r_3$$
Repeat until some $$r_k = 0$$. Then $$\text{GCF} = r_{k-1}$$ (the last nonzero remainder).
For example, $$\text{GCF}(252, 105)$$:
$$252 = 105 \times 2 + 42$$
$$105 = 42 \times 2 + 21$$
$$42 = 21 \times 2 + 0$$
So $$\text{GCF}(252, 105) = 21$$ in 3 steps.
The sequence of quotients $$[q_1, q_2, \ldots, q_k]$$ forms the continued fraction representation of $$a/b$$, connecting this algorithm to deep results in Diophantine approximation.
The step count reveals the computational complexity for your specific inputs. Fewer steps mean the numbers share a large common factor discovered quickly. The maximum steps for numbers below $$n$$ occurs with consecutive Fibonacci numbers (e.g., 89 and 55 require 9 steps). If the GCF equals 1, the numbers are coprime. The quotient sequence provides the continued fraction expansion of $$a/b$$, useful in rational approximation theory.
Inputs
Results
252 = 2×105 + 42, then 105 = 2×42 + 21, then 42 = 2×21 + 0. GCF = 21 in 3 steps.
Inputs
Results
Consecutive Fibonacci numbers are coprime and require the maximum steps. All quotients are 1.
It appears in Euclid's Elements (c. 300 BCE), Book VII, Propositions 1-2, making it one of the oldest known algorithms — over 2,300 years old. While the method was likely known before Euclid, his systematic presentation in the Elements established it as a foundational algorithm in mathematics.
The algorithm takes at most $$2\log_2(\min(a,b))$$ steps. Gabriel Lame proved in 1844 that the number of steps never exceeds 5 times the number of digits in the smaller number. The worst case occurs with consecutive Fibonacci numbers, where every quotient equals 1.
The Extended Euclidean Algorithm not only finds $$\text{GCF}(a,b)$$ but also integers $$x, y$$ such that $$ax + by = \text{GCF}(a,b)$$ (Bezout's identity). This is essential for computing modular inverses in cryptography, solving linear Diophantine equations, and RSA key generation.
Fibonacci numbers $$F_n$$ and $$F_{n-1}$$ produce quotient 1 at every step: $$F_n = 1 \cdot F_{n-1} + F_{n-2}$$. This means the remainders decrease as slowly as possible (each is barely less than the divisor), maximizing iterations. Lame's theorem uses this fact to bound the algorithm's complexity.
In RSA encryption, you need the modular inverse of $$e$$ modulo $$\phi(n)$$, computed via the Extended Euclidean Algorithm. The algorithm also verifies that $$\text{GCF}(e, \phi(n)) = 1$$ (required for a valid public key). It runs in the key generation phase of RSA, Diffie-Hellman, and elliptic curve cryptosystems.
Yes. The algorithm generalizes to any Euclidean domain, including polynomials. For polynomials, division with remainder replaces integer division, and the algorithm finds the greatest common divisor polynomial. This is used in symbolic algebra, coding theory, and control systems engineering.
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
