Greatest Common Divisor Calculator
The greatest common divisor (GCD) of two or more numbers is the largest number that divides all of them with no remainder — for example the GCD of 12 and 18 is 6. This GCD Calculator finds it for any list of numbers; just enter them below separated by commas.
GCD Calculator
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.
Frequently asked questions
How do I find the greatest common divisor?
List the factors of each number and take the largest they share, or use the Euclidean algorithm. The GCD of 12 and 18 is 6.
What is the GCD of two numbers?
It is the largest whole number that divides both without a remainder. For 8 and 12 it is 4.
What is the Euclidean algorithm?
It finds the GCD by repeatedly replacing the larger number with the remainder of dividing it by the smaller, until the remainder is zero.
What is the difference between GCD and LCM?
The GCD is the largest number that divides them all, while the least common multiple (LCM) is the smallest number they all divide into.
Can I find the GCD of more than two numbers?
Yes. Enter as many numbers as you like, separated by commas, and the calculator returns the greatest common divisor of the whole set.