Scienceland

Euclidean algorithm

Euclidean algorithm is a way of finding the greatest common divisor (GCD) of two integers. The original version of the algorithm, when GCD is calculated by subtraction, was discovered by Euclid (III century BC). At present, division is often used, since this method is more effective.

Computing the GCD by dividing

The greatest common divisor of a pair of numbers is the largest number that completely divides both numbers of the pair. Let it be required to calculate the GCD for the numbers 108 and 72. The algorithm for calculating by dividing will be as follows:

  1. We divide the greater number (divisible) by the smaller (divisor): 108 / 72 = 1, the remainder is 36.
  2. Since the remainder is not zero, the divisor turns into a divisible, and the remainder is a divisor: 72 / 36 = 2, the remainder is 0.
  3. When the remainder is zero, the divisor is the desired GCD for a pair of given numbers. That is GCD(108, 72) = 36. Indeed, 108 / 36 = 3 and 72 / 36 = 2.

In this algorithm, the division is repeated until the remainder is zero. When it becomes so, the GCD is the divisor of the last division. For example, it is required to find the GCD(106, 16):

  1. 106 / 16 = 6, the remainder is 10
  2. 16 / 10 = 1, ... 6
  3. 10 / 6 = 1, ... 4
  4. 6 / 4 = 1, ... 2
  5. 4 / 2 = 2, ... 0
  6. GCD(106, 16) = 2

Calculation of GCD by subtraction

When the GCD is found by subtraction, it is also required to reach zero. The algorithm is similar to the division method, only here, at each next step, the subtrahend and the difference from the previous step are taken. In this case, always less is subtracted from a larger number. This kind of algorithm is suitable only for positive integers.

Let it be required to find the GCD(108, 72):

  1. 108 - 72 = 36
  2. 72 - 36 = 36
  3. 36 - 36 = 0
  4. GCD(108, 72) = 36

GCD(44, 60):

  1. 60 - 44 = 16
  2. 44 - 16 = 28
  3. 28 - 16 = 12
  4. 16 - 12 = 4
  5. 12 - 4 = 8
  6. 8 - 4 = 4
  7. 4 - 4 = 0
  8. GCD(44, 60) = 4

This algorithm is sometimes described in a different way. Subtraction ends earlier, in a step where one number divides another completely. That is, combine the subtraction with the divisibility check. The finding the GCD for 44 and 60 will look like this:

  1. Does 44 divide 60 without remainder? No. 60 - 44 = 16.
  2. Does 16 divide 44 without remainder? No. 44 - 16 = 28.
  3. Does 16 divide 28 ... ? No. 28 - 16 = 12.
  4. Does 12 divide 16 ... ? No. 16 - 12 = 4.
  5. Does 4 divide 12 ... ? Yes. Then GCD(44, 60) = 4.

Note that GCD is a divisor. If in the example we divide 12 by 4, we get a quotient 3. But this is not GCD.

Proof of the Euclidean algorithm

If one natural number from a pair completely divides another, then their GCD will be equal to the smaller of them:

if a / b without remainder, then GCD(a, b) = b. For example: GCD(15, 5) = 5.

Thus, if we come to a pair of numbers, one of which divides completely the other, the smaller will be the greatest common divisor for both. Euclid's algorithm looks for exactly such a pair of numbers.

The second fact. It is required to prove that if one number is greater than another, their greatest common divisor is equal to the greatest common divisor for the smaller number from the pair, and the difference of the larger and smaller numbers. This can be written as:

if a < b, then GCD(a, b) = GCD(a, b - a).

The proof of GCD(a, b) = GCD(a, b - a) is as follows. Let b - a = c. If any number x divides without remainder both a and b, then it will also divide c completely. Because if a and b are not equal, then the divisor in them fits the whole, but a different number of times. And if you subtract one from the other, then the divisor must also fit an integer number of times into the resulting difference.

If we successively decrease a and b, then sooner or later we come to the value of the smaller of them, which will divide the larger number without remainder. The smaller number in this pair will be the greatest common divisor for the original pair of natural numbers. This is the Euclidean algorithm.