GCD Calculator
Find the Greatest Common Divisor (GCD) of two or more numbers using the Euclidean algorithm. Also computes the Least Common Multiple (LCM).
About this Calculator
Find the Greatest Common Divisor (GCD) of two or more numbers using the Euclidean algorithm. Also computes the Least Common Multiple (LCM).
Formula & Calculations
Formula
GCD(a,b) = GCD(b, a mod b), with GCD(a,0) = |a|. LCM(a,b) = |a*b| / GCD(a,b).Where:
- GCD=The largest positive integer that divides all input numbers without a remainder
- LCM=The smallest positive integer that is divisible by all input numbers
- a, b, c, ...=Two or more positive integers
Assumptions
- All input numbers must be positive integers.
- The Euclidean algorithm converges in at most O(log min(a,b)) steps.
- For more than two numbers, GCD and LCM are computed pairwise associatively.
Calculation Examples
Example 1
GCD(48,180) = 12, GCD(12,60) = 12. LCM(48,180) = 720, LCM(720,60) = 720.
Example 2
Euclidean algorithm: GCD(36,24) = GCD(24,12) = GCD(12,0) = 12. LCM = |24*36|/12 = 72.
Frequently Asked Questions
What is the Euclidean algorithm?
The Euclidean algorithm repeatedly replaces the larger number by the remainder when divided by the smaller number, until the remainder is zero. The last non-zero remainder is the GCD.
How is LCM related to GCD?
For two positive integers a and b, LCM(a,b) = |a * b| / GCD(a,b). This relationship is used to compute the LCM efficiently after finding the GCD.