Euclidean algorithm

In previous post, we have learned about Bézout's Lemma. Today, we will learn about Euclidean algorithm. This algorithm is used to determine the coefficients in the Bézout's equation.

Let us recall Bézout's lemma. 

Bézout's Lemma. Let $a$ and $b$ be two integers and $d$ their greatest common divisor. Then there exist two integers $x$ and $y$ such that $$d = a ~x + b ~y.$$

We use Euclidean algorithm to calculate the greatest common divisor $d$ of the two numbers $a$ and $b$, and determine the two values of $x$ and $y$ in Bézout's equation  $$d = a ~x + b ~y.$$

We will see that Euclidean algorithm is motivated from a very simple and natural idea.




First, let us look at how we can calculate the greatest common divisor of a pair of integers $a$ and $b$.

Suppose that $a = 45$, $b = 155$. How can we find their greatest common divisor?


There is a very natural method to find the greatest common divisor, that is to make the pair of numbers become smaller and smaller. We know that the greatest common divisor of the pair $(a,b)$ is exactly the same as the greatest common divisor of a smaller pair $(a, b-a)$.

In this example, we have $a = 45$, $b = 155$. We can make the number $b$ become smaller as $$b-a = 110.$$ The greatest common divisor of the pair $(45, 155)$ is exactly the same as the greatest common divisor of the pair $(45, 110)$.

The number $b-a=110$ can be made even smaller by $$(b - a) - a = 110-45 = 65,$$ and smaller by $$b - 3a = 65-45 = 20.$$

Thus, we obtain a smaller pair $(45, 20)$. In general, if we take $b$ and divide it by $a$, suppose the result is  $$b = aq + r,$$  where $r$ is the remainder, then the greatest common divisor of the pair $(a,b)$ is equal to that of the smaller pair $(a,r)$.

This is the main idea of the Euclidean algorithm.

Let us do it again from the beginning. We have $$155 = 45 \times 3 + 20,$$ so $\gcd (45, 155) = \gcd (45, 20)$. Make the pair smaller by $$45 = 20 \times 2 + 5,$$ so $\gcd (45, 20) = \gcd (20,5)$. Continuing, $$20 = 5 \times 4 + 0,$$ thus, $\gcd (20,5) = 5$. So we have found the greatest common divisor, it is the number $5$.




Now let us show how to determine the values of $x$, $y$ in Bézout's equation  $$d = a ~x + b ~y.$$

Step 1. We perform the above division to determine the greatest common divisor $d$.

$$155 = 45 \times 3 + 20,$$ $$45 = 20 \times 2 + 5,$$ $$20 = 5 \times 4 + 0,$$ thus, $d=\gcd (45,155) = 5$

Step 2. From bottom up, we transform each equation $b = aq + r$ to become $r = b - aq$ (the last equation has remainder equal to $0$ so we do not need to write)

$$d = 5 = 45 - 20 \times 2,$$ $$20 = 155 - 45 \times 3,$$

Step 3. We express $d$ as follows

$$d = 5 = 45 - 20 \times 2$$ $$= 45 - (155 - 45 \times 3) \times 2$$ $$= 45 \times 7 - 155 \times 2,$$

Finally, we have written $d$ in the form of $ax + by$.


Let us go through another example. Suppose now $a = 1000$, $b = 2013$.

Step 1. Perform the division $b = aq + r$ to make the pair become smaller $(b,a) \to (a,r)$
$${\bf 2013} = {\bf 1000} \times 2 + {\bf 13},$$ $${\bf 1000} = {\bf 13} \times 76 + {\bf 12},$$ $${\bf 13} = {\bf 12} \times 1 + {\bf 1},$$ $${\bf 12} = {\bf 1} \times 12 + 0,$$ thus, $d=\gcd (1000,2013) = 1$

Step 2. From bottom up, write the equations $r = b - aq$ (skipping the last one)
$$d = {\bf 1} = {\bf 13} - {\bf 12} \times 1,$$ $${\bf 12} = {\bf 1000} - {\bf 13} \times 76,$$ $${\bf 13} = {\bf 2013} - {\bf 1000} \times 2,$$  

Step 3. Express $d$ as follows

finally we obtain $$d = {\bf 1} = {\bf 2013} \times 77 - {\bf 1000} \times 155$$

Bézout's lemma and Euclidean algorithm are useful in solving Diophantine equations. We will turn to this topic in our future post. For now, let us look at the following problem as an example.

Problem. Find all natural number $n$ such that the last three digits of the number $2013 n$ is $999$.


Analysis. In the above problem, we need to solve the equation $$2013 n = 999 = -1 \pmod{1000}.$$

Let us temporarily ignore about modulo and just consider a normal equation of real numbers $$ax = b,$$ this equation has root $$x = \frac{b}{a}.$$ We determine this root by multiplying both sides of the equation by the inverse of $a$.

In the same way, we can solve the modulo equation $$ax = b \pmod{p},$$ by multiplying both sides of the equation with the inverse of $a$.

The inverse of $a$ in modulo $p$ is the number $c$ such that $$ac = 1 \pmod{p}.$$

By multiplying both sides of the equation with $c$ we obtain $$ac x = bc \pmod{p}.$$ Since $ac = 1 \pmod{p}$ it follows that $$x = bc \pmod{p}.$$

In our problem, $$2013 n = -1 \pmod{1000}.$$
We need to find the inverse of $2013$ in modulo $1000$. We need to use Bézout's equation $${\bf 2013} \times 77 - {\bf 1000} \times 155 = 1.$$
Take modulo $1000$, we obtain $$2013 \times 77 = 1 \pmod{1000}.$$
So the inverse of $2013$ in modulo $1000$ is $77$.


Solution. The last three digits of the number $2013 n$ is $999$ if and only if $$2013 n = 999 = -1 \pmod{1000}.$$

From Bézout's equation  $${\bf 2013} \times 77 - {\bf 1000} \times 155 = 1,$$ we have $$2013 \times 77 = 1 \pmod{1000}.$$

Multiplying both sides of the following equation with $77$ $$2013 n = -1 \pmod{1000},$$ we obtain $$2013 \times 77 n = -77 \pmod{1000}.$$

Since $2013 \times 77 = 1 \pmod{1000}$, it follows that $$n = -77 = 923 \pmod{1000}.$$

Therefore, the integer $n$ satisfies the problem is $n = 923 + 1000 k$.

Let us verify. Take $k=0$, we have $n=923$, and $$2013 \times 923 = 1857999.$$





Let us stop here for now. In the future we will come back to this topic and will look at applications of Bézout's lemma and Euclidean algorithm in more details.

Hope to see you again next time.




Homework.

1. Use Euclidean algorithm to establish Bézout's equation for two numbers $2012$ and $999$.

2. Solve the following equation of integer unknowns $$2012 a + 999 b = 5.$$

3. Solve the following equation of integer unknowns $$2012 x = 999 y + 99 z + 9.$$