GCD of Two Numbers Calculator

Example Data Table

Formula Used

Euclidean recurrence

GCD and LCM identity

Bézout identity

Zero rules

gcd(a, 0) = |a| for nonzero a. The value gcd(0, 0) is undefined.

How to Use This Calculator

1. Enter the first whole number. A leading plus or minus sign is allowed.
2. Enter the second whole number. Do not enter commas, spaces, decimals, or exponent notation.
3. Select one detailed method or choose all supported methods.
4. Choose whether to list divisors, verify the GCD-LCM identity, or show the extended table.
5. Press Calculate GCD. The main result appears above the form.
6. Review the Euclidean steps, prime factors, coefficients, ratio, fraction, and relationship checks.
7. Copy the result, export CSV, create a PDF, print the page, or copy a shareable link.

Understanding the Greatest Common Divisor

The greatest common divisor is the largest positive integer that divides two integers without a remainder. It is also called the greatest common factor or highest common factor. These names describe the same number. The calculator uses absolute values for the main GCD, so negative signs do not make the result negative.

Why the Euclidean algorithm matters

Listing every factor can work for small values. It becomes slow for large values. The Euclidean algorithm is usually much faster. It replaces a pair of numbers with the smaller number and the remainder. Each replacement keeps the same GCD. The process ends when a remainder becomes zero.

For 48 and 18, divide 48 by 18. The remainder is 12. Next, divide 18 by 12. The remainder is 6. Finally, divide 12 by 6. The remainder is zero. Therefore, the last nonzero divisor is 6.

Prime factors and common factors

Prime factorization gives another clear method. Write each number as a product of primes. Keep only the primes shared by both numbers. Use the smaller exponent for every shared prime. Multiplying those shared prime powers gives the GCD.

Every positive common divisor must divide the GCD. This fact makes the common factor list easy to understand. Once the GCD is known, its positive divisors are exactly the positive numbers that divide both inputs.

Reduced ratios and fractions

A ratio can be reduced by dividing both terms by their GCD. The same rule reduces a fraction. For example, 48:18 becomes 8:3 after division by 6. The fraction 48/18 also becomes 8/3. A GCD of one means the ratio or fraction is already in lowest terms.

LCM and verification

The least common multiple is the smallest nonnegative number divisible by both inputs. For nonzero integers, the product of the GCD and LCM equals the absolute product of the inputs. This calculator displays both sides of that identity, which provides a useful arithmetic check.

Bézout coefficients

The extended Euclidean algorithm does more than find a divisor. It also finds integers x and y that satisfy ax + by = gcd(a, b). These coefficients support modular inverses, congruences, cryptography, and linear Diophantine equations. When the GCD is one, a modular inverse may exist.

Special values

Zero needs careful treatment. The GCD of zero and a nonzero integer is the absolute value of the nonzero integer. The LCM in that case is zero. The GCD of zero and zero is not defined because no greatest positive common divisor exists. The calculator reports this case clearly.

Choosing a method

Use the Euclidean algorithm for fast general work. Use prime factorization when learning factor structure. Use common factors for small classroom examples. Use the binary method when studying low-level integer algorithms. Use repeated subtraction for intuition, not speed. Use the extended method when coefficients or modular arithmetic are required.

Frequently Asked Questions