✖

Greatest common divisor

The greatest common divisor (GCD) of two integers is the number that divides both of them with no remainder, such that no larger number also divides both with no remainder. It is also called the highest common factor (HCF).

As an example, take the numbers 24 and 32. What is their greatest common divisor? First of all, we are looking for a number that divides both.

  • For instance, 12 divides 24, but it does not divide 32, because 32 / 12 is 2.666…, which is not an integer. So 12 cannot be the greatest common divisor of 24 and 32.
  • What about 4? It divides both numbers: 24 / 4 is 6 and 32 / 4 is 8. So 4 is our first candidate. Is there a larger number that divides both?
  • The number 8 divides both 24 and 32, and it is larger than 4.
  • There is no number larger than 8 that divides both. So 8 is the greatest common divisor of 24 and 32.

The Euclidean algorithm for finding the greatest common divisor

There is a fairly simple way to find the greatest common divisor of two numbers: the Euclidean algorithm. Let’s start with two numbers x and y whose greatest common divisor we want to find. As an example, we’ll try x = 50 and y = 35. Then we proceed as follows:

  1. Divide x / y and remember the remainder. Call this remainder z. In our example we get 50 / 35, which leaves a remainder of z = 15.
  2. Now swap the variables: store the value of y in x and the value of z in y. Throw away the original value of x. After this step we have x = 35 and y = 15.
  3. Now check whether y is equal to zero. If it is, the greatest common divisor is x. Since y is not zero, we carry on and repeat the whole procedure from the first step.
  4. Divide x / y again, that is 35 / 15, which leaves a remainder of z = 5.
  5. Swap the variables, giving x = 15 and y = 5. Since y is not zero, we carry on.
  6. Divide x / y, that is 15 / 5. The remainder is z = 0.
  7. Swap the variables and we get x = 5 and y = 0.
  8. Now y = 0 and the algorithm stops. The greatest common divisor is x = 5.

It is important to note that the order of the numbers does not matter. If we swapped the numbers in the example, we would get the pair x = 35 and y = 50. The procedure would be the same:

  1. Divide x / y, that is 35 / 50, which leaves a remainder of z = 35.
  2. Swap the variables: x = 50 and y = 35.
  3. We can see that after this step we have simply swapped the contents of the variables x and y…

Calculator

This calculator works out the greatest common divisor for you.