The Euclides algorithm

The highest common factor between two integers is the biggest number that divides both.

Example

For example, if we have $20$ and $16$ , the highest common factor between the two is $4$ , since:

The divisors of $20$ are: $1$ , $2$ , $4$ , $5$ , $10$ and $20$

The divisors of $16$ are: $1$ , $2$ , $4$ and $16$

The numbers that divide either $20$ or $16$ are: $1$ , $2$ and $4$ , and clearly the biggest is $4$ . So, the highest common factor between $20$ and $16$ is $4$ , and it is written as $h c f (20, 16) = 4$ .

Nevertheless, calculating the highest common factor between two numbers can turn out to be much more complicated for very big numbers.

To do so, a method exists which is known as algorithm of Euclides, which, although at first it looks a little bit strange at first, after practiced, it turns out to be much simpler than other methods.

Furthermore, it is also useful for solving diophantine equations.

The Euclides algorithm is based on the definition of three sequences of numbers: the first one is called $r_{j}$ , the second one will be called $s_{j}$ and the third one $t_{j}$ .

The Euclides algorithm consists in doing the following steps:

Two numbers are taken: $a \geq 0$ , $b > 0$ . We want to calculate $h c f (a, b)$ (the highest common factor between $a$ and $b$ ). For example, we might take $a = 10$ and $b = 5$ .
We define: $\begin{array}{rclrcl} r_{0} & = & a, & r_{1} & = & b \\ s_{0} & = & 1, & s_{1} & = & 0 \\ t_{0} & = & 0, & t_{1} & = & 1 \end{array}$ For example with $a = 10$ and $b = 5$ , we would have: : $\begin{array}{rclrcl} r_{0} & = & 10, & r_{1} & = & 5 \\ s_{0} & = & 1, & s_{1} & = & 0 \\ t_{0} & = & 0, & t_{1} & = & 1 \end{array}$
For $j \geq 2$ , we do the integer division of $r_{j - a}$ by $r_{j - 1}$ . We call the result $q_{j - 1}$ and to the remainder $r_{j}$ . In the previous example, if we want to calculate $r_{2}$ and $q_{1}$ (that is to say, $j = 2$ ) it is necessary to do the integer division between $r_{0} = 10$ and $r_{1} = 5$ . It is clear that the result of the divisón is $2$ with remainder $0$ , and therefore we write $q_{1} = 2$ and $r_{2} = 0$ .
Now, we define: $\begin{array}{rcl} s_{j} & = & s_{j - 2} - s_{j - 1} \cdot q_{j - 1} \\ t_{j} & = & t_{j - 2} - t_{j - 1} \cdot q_{j - 1} \end{array}$ In the previous example we had: $\begin{array}{rcl} s_{2} & = & s_{0} - s_{1} \cdot q_{1} = 1 - 0 \cdot 1 = 1 \\ t_{2} & = & t_{0} - t_{1} \cdot q_{1} = 0 - 1 \cdot 2 = - 2 \end{array}$
When there is one $r_{n + 1} = 0$ , then we have $h c f (a, b) = r_{n}$ (that is to say, that of the previous step!). Furthermore, it is also satisfied that: $h c f (a, b) = s_{n} \cdot a + t_{n} \cdot b$ ( $s_{n}$ and $t_{n}$ are also those of the previous step).

Returning to the example that we used on the previous steps, we have seen that for $j = 2$ it is already satisfied that $r_{2} = 0$ . Therefore, the highest common factor between $10$ and $5$ is $r_{1}$ (that of the previous step), that is to say, $5$ .

Besides, the last equality says to us that: $h c f (10, 5) = s_{1} \cdot 10 + t_{1} \cdot 5 = 0 \cdot 10 + 1 \cdot 5 = 0$