Calculate GCD and LCM using the Euclidean Algorithm (Division Method)
a =
b =
Result
Input
Greatest Common Divisor (GCD)
Least Common Multiple (LCM)
Step-by-Step (Euclidean Algorithm)
Euclidean Algorithm Steps
① Let a ≥ b, divide larger by smaller: a = q₁b + r₁
② If r₁ = 0, then gcd(a,b) = b
③ If r₁ ≠ 0, then gcd(a,b) = gcd(b, r₁)
④ Repeat until remainder = 0
Property: gcd(a,b) × lcm(a,b) = a × b
The Euclidean algorithm is one of the oldest and most important algorithms in number theory, first introduced by Euclid in his Elements. It remains the standard method for computing GCD.
⚠The Euclidean algorithm runs in O(log min(a,b)) time, extremely efficient. Bézout's Identity states that gcd(a,b) can be written as ax + by for integers x,y.
What Are GCD and Euclidean Algorithm?
The Greatest Common Divisor (GCD) is the largest positive integer that divides each of the integers. The Euclidean algorithm is the most efficient classic method to compute GCD.
Greatest Common Divisor
The largest common divisor of integers, written gcd(a,b). Example: gcd(12,18)=6.
Euclidean Algorithm
Divide larger by smaller, replace larger with smaller, smaller with remainder. Stop at 0. Time complexity O(log min(a,b)).
Least Common Multiple
LCM(a,b) = |a×b| / GCD(a,b). Product of two numbers = GCD × LCM.
Bézout's Identity
There exist integers x,y such that ax+by=gcd(a,b). Used for modular inverses and congruences.
💡 Example: Compute gcd(48,18). 48÷18=2 rem 12, 18÷12=1 rem 6, 12÷6=2 rem 0 → gcd=6. Common divisors: 1,2,3,6.
Applications
Fraction SimplificationCongruence EquationsRSA AlgorithmProgramming ContestsNumber Theory
Frequently Asked Questions
What is the Greatest Common Divisor?▼
The GCD (Greatest Common Divisor) is the largest positive integer that divides all given numbers without remainder, written gcd(a,b). Example: gcd(12,18)=6.
How does the Euclidean algorithm work?▼
Divide the larger number by the smaller one, get the remainder. Replace the larger with the smaller, the smaller with the remainder. Repeat until remainder=0. The last divisor is GCD.
What is the GCD-LCM relationship?▼
For any two positive integers a and b: a × b = gcd(a,b) × lcm(a,b). You can calculate LCM quickly once you know the GCD.
What is the time complexity?▼
The Euclidean algorithm runs in O(log min(a,b)) time, which is extremely fast even for very large integers.
Free online calculators and tools covering mathematics, unit conversion, text processing, and daily life. Accurate, fast, mobile-friendly, and completely free to use.