GCD Calculator
Compute the greatest common divisor of several integers with the Euclidean steps shown
输入整数
支持输入多个整数，至少需要 2 个数才能计算最大公因数
About this tool
The GCD calculator finds the greatest common divisor of two or more integers:
- Any count: enter as many integers as you like, separated by commas, spaces or new lines
- Live result: the answer updates as you type
- Working shown: every step of the Euclidean algorithm is listed
- Divisor lists: see all divisors of each input number
What the GCD is
The greatest common divisor is the largest positive integer that divides every number in the set. For example GCD(12, 18) = 6, because 6 is the largest integer dividing both 12 and 18.
When to use it
- Reduce a fraction by dividing numerator and denominator by their GCD
- Number theory homework and study
- Modular arithmetic in cryptography
- The basis for the LCM: LCM = product of the pair divided by their GCD
Math notes
- Euclidean algorithm: GCD(a,b) = GCD(b, a mod b), repeated until the remainder is 0; the last b is the answer
- GCD and LCM: GCD(a,b) times LCM(a,b) equals a times b
- Coprime: when GCD(a,b) = 1, a and b share no factor
- More than two numbers: take the GCD of the first pair, then combine that result with the next number, and so on