Compute GCD (Greatest Common Divisor) and LCM (Least Common Multiple) using the Euclidean algorithm
a =
b =
Results
Input
Greatest Common Divisor (GCD)
Least Common Multiple (LCM)
Step-by-Step Derivation (Euclidean Algorithm)
Euclidean Algorithm Steps
① Let a ≥ b, divide the larger by the 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 the remainder becomes 0
Property: gcd(a,b) × lcm(a,b) = a × b
The Euclidean algorithm (Euclid's algorithm) is one of the oldest and most important algorithms in number theory, first described by Euclid in his Elements. It remains the standard method for computing greatest common divisors.
⚠The Euclidean algorithm runs in O(log min(a,b)) — very efficient. Bézout's identity states that there exist integers x,y such that ax+by = gcd(a,b). Extended Euclidean algorithm can find these coefficients for modular inverses and Diophantine equations.
What Are GCD and the Euclidean Algorithm?
The Greatest Common Divisor (GCD) of two positive integers is the largest integer that divides both numbers. The Euclidean algorithm is the classic method for computing GCD through repeated division, relying on the property that gcd(a,b) = gcd(b, a mod b).
Greatest Common Divisor (GCD)
The largest positive integer that divides each of the given numbers. Example: gcd(12,18)=6 because common divisors are 1,2,3,6.
Euclidean Algorithm
Divide larger by smaller → remainder; replace larger with smaller, smaller with remainder; repeat until remainder=0; last non-zero remainder is GCD. Time complexity O(log min(a,b)).
Least Common Multiple (LCM)
The smallest positive integer divisible by both numbers. Relationship: LCM(a,b) = a×b / GCD(a,b).
Bézout's Identity
There exist integers x,y such that ax+by = gcd(a,b). The extended Euclidean algorithm finds these coefficients, used for modular inverses and linear Diophantine equations.
💡 Example: Find gcd(48,18). 48÷18=2 remainder 12, 18÷12=1 remainder 6, 12÷6=2 remainder 0 → gcd=6. Common divisors of 48 and 18: 1,2,3,6 — the greatest is 6.
Applications
Fraction ReductionModular ArithmeticRSA CryptographyCompetitive ProgrammingNumber Theory Basics
Frequently Asked Questions
What is the Greatest Common Divisor (GCD)?▼
The GCD of several positive integers is the largest positive integer that divides each of them. For example, gcd(12,18)=6 because the common divisors of 12 and 18 are 1,2,3,6, with 6 being the largest.
How does the Euclidean algorithm work?▼
Divide the larger number by the smaller, get remainder; divide the smaller by the remainder; repeat until remainder=0. The last non-zero remainder is the GCD. Example: gcd(48,18): 48÷18=2 r12, 18÷12=1 r6, 12÷6=2 r0 → GCD=6.
What is the relationship between GCD and LCM?▼
For any two positive integers a and b: a × b = gcd(a,b) × lcm(a,b). The product of the two numbers equals the product of their GCD and LCM. Use this to quickly compute LCM from GCD.
What is the time complexity of the Euclidean algorithm?▼
O(log min(a,b)), which is very efficient. The remainder at least halves each step, so even very large numbers require few iterations to find the GCD.
Free online calculators and tools covering mathematics, unit conversion, text processing, and daily life. Accurate, fast, mobile-friendly, and completely free to use.