Greatest common divisor calculator

The greatest common divisor is the largest number that divides every value you enter exactly. It is the key to simplifying fractions and to splitting quantities into equal groups.

Enter as many numbers as you need, separated by commas or spaces.

Euclid's algorithm is applied: the pair (a, b) is replaced by (b, remainder of a divided by b) until the remainder is zero. The last non-zero divisor is the GCD.

With more than two numbers the calculation is done pairwise and accumulated.

Simplifying fractions is its commonest use

Dividing numerator and denominator by their greatest common divisor leaves the fraction in lowest terms in a single step. Eighty-four over one hundred and twenty has a GCD of twelve, so it simplifies directly to seven tenths without stripping out factors two at a time.

Euclid's algorithm is over two thousand years old

It appears in Euclid's Elements and remains the most efficient method for the general case. It consists of dividing the larger by the smaller and keeping the remainder, repeating until the remainder is zero. It is so effective that it is used today in cryptography, inside the RSA algorithm.

Coprime numbers

When the greatest common divisor is one, the numbers share no factor and are called coprime. It does not mean they are prime: eight and nine are coprime and neither is prime.

Exact divisions

It is the tool for splitting different quantities into equal groups as large as possible: how many identical bouquets come from twenty-four roses and thirty-six carnations, or the largest square tile that covers a room without cuts.