Greatest Common Divisor Calculator — GCD & Euclidean Algorithm
Enter two whole numbers and the calculator finds their greatest common divisor (GCD) — the largest integer that divides both without remainder — using the Euclidean algorithm, with every division step shown. It also computes the least common multiple (LCM) from GCD automatically.
Largest positive integer that divides both A and B without remainder
Step 1: 48 ÷ 18
Step 2: 18 ÷ 12
Step 3: 12 ÷ 6
Remainder = 0 → previous remainder is the GCD
How does this calculator work?
GCD is found by the Euclidean algorithm: repeatedly divide the larger by the smaller and replace the pair with (divisor, remainder) until the remainder is 0 — the last non-zero remainder is the GCD. Then LCM = A × B / GCD. For GCD(48, 18): 48 = 2×18+12, 18 = 1×12+6, 12 = 2×6+0, so GCD = 6, LCM = 144.
Formula
How this is calculated
The Euclidean algorithm is an ancient and highly efficient method for computing GCD. Starting with the larger number (a) and the smaller (b), it repeatedly replaces the pair with (b, a mod b) — i.e., the divisor becomes the new dividend and the remainder becomes the new divisor — until the remainder is zero. The last non-zero remainder is the GCD.
The algorithm is efficient because each step reduces the numbers significantly. In the worst case (consecutive Fibonacci numbers) it takes O(log(min(a, b))) steps. The maximum number of steps for two n-digit numbers is roughly 4.8 × n, so even six-digit inputs finish in a few dozen steps.
The least common multiple (LCM) follows directly from the GCD via LCM(a, b) = a × b / GCD(a, b). This relationship is useful for fraction arithmetic (the LCD of two denominators equals their LCM). The GCD also tells you the simplified form of the fraction a/b: divide both numerator and denominator by GCD(a, b).
Frequently asked questions
The GCD (greatest common divisor) is the largest number that divides both integers without remainder — it makes fractions simpler. The LCM (least common multiple) is the smallest number that both integers divide into — it is used as the common denominator when adding fractions. They are related by GCD(a, b) × LCM(a, b) = a × b.
When GCD(a, b) = 1, the two numbers share no common factors other than 1 — they are called coprime or relatively prime. The fraction a/b is already in its simplest form, and LCM(a, b) = a × b.
Each step computes a = q × b + r, then replaces (a, b) with (b, r). The GCD of a pair equals the GCD of the next pair because any common divisor of (a, b) also divides r = a − q × b, and vice versa. When r = 0, b is the GCD because it divides itself and everything in the chain back to the original inputs.
Also known as
TG we-Calculate Editorial Team. (2026). Greatest Common Divisor Calculator — GCD & Euclidean Algorithm [Online calculator]. TG we-Calculate. https://we-calculate.com/calculator/greatest-common-divisor-calculator
TG we-Calculate Editorial Team. "Greatest Common Divisor Calculator — GCD & Euclidean Algorithm." TG we-Calculate. 2026. https://we-calculate.com/calculator/greatest-common-divisor-calculator.
TG we-Calculate Editorial Team, "Greatest Common Divisor Calculator — GCD & Euclidean Algorithm," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/calculator/greatest-common-divisor-calculator
@misc{wecalculate_greatest_common_divisor_calculator, title = {Greatest Common Divisor Calculator — GCD & Euclidean Algorithm}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/calculator/greatest-common-divisor-calculator}}, year = {2026}, note = {TG we-Calculate} }
Did this calculator help you?