Calculate the Greatest Common Divisor (GCD) of two or more numbers using the Euclidean algorithm or prime factorization method. View step-by-step solutions, Bézout coefficients, LCM, and coprimalit...
The **GCD Calculator** finds the greatest common divisor of two or more integers, meaning the largest positive integer that divides every input with no remainder. In practice, it is the cleanest way to reduce fractions, compare shared factors, and support number-theory work that depends on exact divisibility.
You can solve it with the Euclidean algorithm or with prime factorization. The Euclidean method repeatedly replaces the larger number with the remainder until the remainder is zero, while the factorization method compares the prime powers shared by every input.
The calculator also shows the related LCM, checks whether the inputs are coprime, and provides Bézout coefficients for the two-number case. That gives you both the answer and the structure behind it. It is useful when you want to move from a simple shared-factor question into the broader number-theory relationships around the same inputs. That extra context is what makes the result more than a single classroom vocabulary word.
GCD appears anywhere shared divisibility matters: fraction reduction, modular arithmetic, solving linear combinations, and checking coprimality. This calculator is useful because it exposes both the Euclidean path and the factorization path, so the result is easy to verify and explain. The extra outputs also make it easier to connect the answer to LCM, Bézout identities, and coprime tests without opening a second tool.
Euclidean: gcd(a, b) = gcd(b, a mod b); base case gcd(a, 0) = a. Prime factorization: gcd = ∏ p^min(e₁, e₂) over shared primes.
Result: The GCD of 48 and 36 is 12.
48 = 36 × 1 + 12, and 36 = 12 × 3 + 0, so the last nonzero remainder is 12.
The Euclidean algorithm is the standard fast method for computing gcd(a, b). Instead of listing all factors, it repeatedly replaces the larger number with the remainder after division. When the remainder reaches zero, the last nonzero remainder is the GCD. This is why the method remains efficient even for large integers, and why it is the version most often used in programming and computer algebra systems.
The factorization table is slower for large numbers, but it is excellent for understanding why the answer is what it is. By comparing prime exponents across the inputs and taking the minimum exponent for each shared prime, you can reconstruct the GCD directly. That makes the calculator useful for instruction, especially when learners are transitioning from factor trees to algorithmic methods.
For two inputs, the extended Euclidean algorithm produces integers x and y such that ax + by = gcd(a, b). Those coefficients matter in modular inverses and Diophantine equations. The coprime check is equally important: when the GCD is 1, the numbers share no nontrivial factor, which is a foundational condition in many number-theory and cryptographic problems.
The GCD of two or more integers is the largest positive integer that divides all of them without a remainder. For example, GCD(12, 18) = 6.
Repeatedly replace the larger number with the remainder of dividing it by the smaller until the remainder is zero. The last nonzero remainder is the GCD.
GCD(a, b) × LCM(a, b) = a × b. This identity lets you find one if you know the other.
The Euclidean algorithm repeatedly replaces the larger number with the remainder from dividing the larger by the smaller. The process continues until the remainder is zero; the last non-zero remainder is the GCD.
The GCD is used to simplify fractions to lowest terms, split quantities into equal groups, and reduce ratios before further calculations. It is the quickest way to strip two numbers down to the largest shared unit they both contain.
For any two positive integers a and b: GCD(a,b) × LCM(a,b) = a × b. This identity lets you compute the LCM quickly once you know the GCD.