Greatest Common Divisor Calculator (GCD Calculator) allows you to easily calculate the GCD of two or more numbers. Enter the numbers below separated by commas.
Greatest common divisor:
What is the Greatest Common Divisor?
Greatest Common Divisor (or GCD) of two or more integers is the largest positive integer that divides each of the integers. For example, the GCD of 24 and 18 is 6. The greatest common divisor is useful for reducing fractions to the lowest terms.
How GCD is calculated?
1. Prime factorizations
Greatest common divisors can be computed by determining the prime factorizations of the two numbers and comparing factors. In practice, this method is only feasible for small numbers, as computing prime factorizations takes too long.
2. Euclid’s algorithm
The method introduced by Euclid for computing the greatest common divisors is based on the fact that given two positive integers a and b such that a > b, the common divisors of a and b are the same as the common divisors of a – b and b. So, Euclid’s method for computing the greatest common divisor of two positive integers consists of replacing the larger number by the difference of the numbers. Then repeating this until the two numbers are equal: that is their greatest common divisor.
3. Euclidean algorithm
A more efficient method is the Euclidean algorithm, a variant in which the difference of the two numbers a and b is replaced by the remainder of the Euclidean division (also called division with remainder) of a by b. Denoting this remainder as a mod b, the algorithm replaces (a, b) by (b, a mod b) repeatedly until the pair is (d, 0), where d is the greatest common divisor.
How to use the Greatest Common Divisor Calculator?
Simply enter at least two integers into the calculator then click on the Calculate GCD button. The GCD Calculator immediately shows the result. We use the Euclidean algorithm for computing the greatest common divisor which is one of the best of its kind.