Euclidean Algorithm Calculator — GCD Step by Step
Compute the GCD (greatest common divisor) of any two positive integers using the Euclidean algorithm, with every division step shown in full.
The largest integer that divides both numbers exactly
Divide 48 by 18 — quotient 2, remainder 12
Divide 18 by 12 — quotient 1, remainder 6
Divide 12 by 6 — quotient 2, remainder 0
Remainder is 0 — algorithm terminates
- 1
GCD via Euclidean algorithm
6Each division step is shown in the table below. - 2
LCM from identity a × b = GCD × LCM
48 × 18 ÷ 6 = 144
How does this calculator work?
The Euclidean algorithm computes GCD(a, b) by repeatedly replacing (a, b) with (b, a mod b) until b = 0; the last non-zero value is the GCD. LCM = a × b ÷ GCD. The algorithm requires O(log min(a,b)) steps and is exact for any positive integers — no factorisation needed.
Formula
How this is calculated
The Euclidean algorithm finds the greatest common divisor of two positive integers without factorising either number. It rests on the identity GCD(a, b) = GCD(b, a mod b): the GCD of two numbers equals the GCD of the smaller and the remainder from dividing the larger by the smaller. Applying this rule repeatedly yields a strictly decreasing chain of remainders. When the remainder reaches 0, the previous non-zero value is the GCD.
This calculator shows each iteration as an explicit division a = q × b + r (q = quotient, r = remainder), then continues with the new pair (b, r). Consecutive Fibonacci numbers are the worst case — they need the most steps relative to their size — but in practice the algorithm terminates in O(log min(a, b)) steps, making it extremely efficient for arbitrarily large integers.
The LCM (least common multiple) is derived from the identity a × b = GCD × LCM, so LCM = a × b ÷ GCD. The calculator takes the absolute values of any negative inputs before computing, since divisibility does not depend on sign.
Frequently asked questions
An ancient procedure — attributed to Euclid (~300 BCE) — that finds the GCD of two integers by repeatedly replacing the larger with the remainder of dividing the two, until the remainder is zero. The last non-zero remainder is the GCD. It runs in O(log min(a,b)) steps.
Each remainder is strictly smaller than the previous divisor, so the sequence of remainders is strictly decreasing. Since all values are non-negative integers they must eventually reach 0.
For any two positive integers a and b, a × b = GCD(a, b) × LCM(a, b). Rearranging gives LCM = a × b ÷ GCD, which is always a whole number because GCD divides both a and b exactly.
TG we-Calculate Editorial Team. (2026). Euclidean Algorithm Calculator — GCD Step by Step [Online calculator]. TG we-Calculate. https://we-calculate.com/calculator/euclidean-algorithm-calculator
TG we-Calculate Editorial Team. "Euclidean Algorithm Calculator — GCD Step by Step." TG we-Calculate. 2026. https://we-calculate.com/calculator/euclidean-algorithm-calculator.
TG we-Calculate Editorial Team, "Euclidean Algorithm Calculator — GCD Step by Step," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/calculator/euclidean-algorithm-calculator
@misc{wecalculate_euclidean_algorithm_calculator, title = {Euclidean Algorithm Calculator — GCD Step by Step}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/calculator/euclidean-algorithm-calculator}}, year = {2026}, note = {TG we-Calculate} }
Did this calculator help you?