✖

The greatest common divisor

The greatest common divisor of two integers is a number that divides both numbers without remainder, and yet there is no other larger number that also divides both numbers without remainder.

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

  • For example, although the number 12 divides 24, it does not divide 32 because 32 / 12 is equal to 2.666... which is not a whole number. So the number 12 cannot be the greatest common divisor of 24 and 32.
  • What about the number 4? That divides both numbers, 24 / 4 is equal to 6 and 32 / 4 is equal to 8. So number 4 is our first candidate. Isn't there a bigger number that divides both numbers?
  • The number 8 divides both 24 and 32, and it's bigger than 4.
  • There is no number greater than 8 that divides both numbers. So the number 8 is the greatest common divisor of the numbers 24 and 32.

Euclid's algorithm for finding the greatest common divisor

There is a relatively simple way to find the greatest common divisor of two numbers using Euclid's algorithm. Let's start with two numbers x and y, for which we want to find the greatest common divisor. For an example, we'll try this on the numbers x = 50 and y = 35 Then we'll proceed as follows:

  1. We divide x / y and remember the remainder after division. We note this remainder as z. For our example, we get 50 / 35, which gives us the remainder z = 15.
  2. Now we swap variables and store the value y in the variable x and store the value z in y. We discard the original value x. After this step, we get x = 35 and y = 15.
  3. Now let's see if y is equal to zero. If so, the greatest common divisor is x. Since y is not equal to zero, we continue on and repeat the whole procedure again from the first point.
  4. We divide x / y again, that is, we divide 35 / 15, which gives us the remainder after dividing z = 5.
  5. Swapping the variables, we get x = 15 and y = 5. Since y is not equal to zero, we continue.
  6. We divide by x / y, which gives 15 / 5. The remainder after division is z = 0.
  7. Swapping the variables, we get x = 5 and y = 0.
  8. At this point, y = 0 is and our algorithm ends. The greatest common divisor is the number x = 5.

Importantly, the order of the numbers does not matter. If we swapped the numbers from the example, we would get the pair x = 35 and y = 50. The procedure would be the same:

  1. Divide x / y, then divide 35 / 50, which gives us the remainder z = 35.
  2. Swap the variables x = 50 and y = 35.
  3. We can see that after this step we have just swapped the area of the variables x and y with each other...

Calculator

This calculator will calculate the greatest common divisor.