GCD / HCF Calculator

GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are identical concepts with different names. Both refer to the largest positive integer that divides two or more numbers without a remainder. "GCD" is more common in American mathematics and computer science, while "HCF" is frequently used in British and Indian educational systems. This calculator returns the same value regardless of which term you prefer.

Yes. Enter three, four, or more numbers separated by commas, spaces, or new lines. The calculator uses the associative property of GCD: gcd(a, b, c) = gcd(gcd(a, b), c). It computes the GCD of the first two numbers, then uses that result with the third number, and continues until all numbers are processed. The steps panel shows the progression through each pairwise calculation.

The Bézout identity finds integers x and y (which may be negative) such that ax + by = gcd(a, b). Negative coefficients are mathematically correct and expected. For example, gcd(48, 18) = 6 is expressed as 48 × (-1) + 18 × 3 = 6. The calculator automatically adjusts signs to match your original input values (including their signs).

The calculator handles single zeros correctly: gcd(a, 0) = |a| and lcm(a, 0) = 0. However, all zeros (0, 0, 0) produces an error because the GCD of zero and zero is mathematically undefined (every integer divides zero). At least one non-zero number is required for a meaningful result.

Enter your numerator and denominator as two numbers. The calculator displays a "Simplified Fractions" section showing the original fraction, the GCD used, and the reduced result. For example, entering 48, 18 shows 48/18 simplifies to 8/3 by dividing both by 6. This works for any pair of integers, including negative fractions.

Two or more numbers are coprime (or relatively prime) if their GCD equals 1. This means they share no prime factors. For example, 17 and 19 are coprime (both prime, different values), as are 8 and 15 (2³ and 3 × 5 share nothing). The calculator displays "Coprime? Yes" when this occurs. Note: numbers need not be prime themselves to be coprime to each other.

Yes. Enable "Show factorization" to see the prime decomposition of every input number. Each number is displayed as a product of primes with exponents, such as 56 = 2³ × 7. This helps visualize why the GCD is what it is: the GCD takes the lowest power of each common prime across all numbers.

For two numbers, GCD × LCM = |a × b|. The GCD captures shared factors; the LCM captures all factors at their highest occurrence. When you enter numbers, both values are calculated automatically. For multiple numbers, the relationship generalizes: gcd(a, b, c) × lcm(a, b, c) does not equal a × b × c, but each can be computed from prime exponent minima and maxima respectively.

Possible reasons: (1) The other calculator uses absolute values while yours included sign handling — both should give the same magnitude. (2) Integer overflow: numbers above 9,007,199,254,740,991 (2⁵³) may lose precision in JavaScript. (3) Different algorithms: some calculators use binary GCD (Stein's algorithm) which is faster but produces identical results. This calculator uses the classical Euclidean algorithm for educational transparency.

Click "Copy GCD" or "Copy LCM" for single values, or "Copy All Results" for a complete text summary including prime factorizations and steps. The formatted text includes all calculated values and can be pasted into documents, emails, or homework submissions. No account or login is required.

Yes. The GCD is defined for negative integers and equals the GCD of their absolute values. Enter -48, 18 and the calculator returns 6. The result is always non-negative by mathematical convention. The Bézout coefficients adjust their signs to accommodate your original negative inputs.

The Extended Euclidean Algorithm computes GCD and finds Bézout coefficients simultaneously. While the standard algorithm only gives the remainder chain, the extended version tracks additional variables to express the GCD as a linear combination of the inputs. This is essential in cryptography (RSA key generation) and solving linear Diophantine equations. Enable "Show Bézout identity" to see this in action.