About reversing the Euclidean Algorithm, Lemma of Bézout

Question

From the book Discrete Mathematics for Computing 2nd Edition in eBook:

I know how to perform the Euclidean Algorithm and GCM(a,b). I am however, deeply confused by this:

$$1 = 415 - 69(421 - 1 \times 415)$$ $$ = 70 \times 415 - 69 \times 421$$

---

How is this expression constructed $70 \times 415 - 69 \times 421$?

---

N.B. I am still new to this and learning, I am using the following book(s):

Discrete Mathematics for Computing / Edition 2
by Peter Grossman [eBook]

Discrete Mathematics for Computing / Edition 3
by Peter Grossman [Physical copy]

Answer 1

As far as I see, the calculations from the quotation concern to construct an integer solution $(x,y)$ of the Diophantine equation $2093x+836y=1$. To do this, we apply first the Euclidean algorithm to find the greatest common divisor to numbers $r_1=2093$ and $r_2=836$ and then go backwards. Namely, the Euclidean algorithm yields:

$r_3=421=2093-2\times 836=r_1-2\times r_2$

$r_4=415=836-1\times 421=r_2-1\times r_3$

$r_5=6=421-1\times 415=r_3-1\times r_4$

$r_6=1=415-69\times 6=r_4-69\times r_5$.

Next we go backwards:

$1=r_6=r_4-69\times r_5=415-69\times 6$

$1=r_4-69\times r_5=r_4-69\times (r_3-1\times r_4)=-69\times r_3+70\times r_4=-69\times 421+70\times 415$

$1=-69\times r_3+70\times r_4=-69\times r_3+70\times (r_2-1\times r_3)=70\times r_2-139\times r_3=70\times 836-139\times 421$

$1=70\times r_2-139\times r_3=70\times r_2-139\times (r_1-2\times r_2)=-139\times r_1+348\times r_2=-139\times 2093+348\times 836$

That is we constructed an integer solution $(x,y)=(-139,348)$ of the equation $2093x+836y=1$.

Answer 2

You already brought up the Euclidean algorithm. For $n,m\in\mathbb{Z}$ with $\operatorname{gcd}(n,m)=1$ you get from "reversing" the algorithm an expression of $1=an+bm$.

Example:

$\operatorname{gcd}(13,23)=1$.

We have

$23=1\cdot 13+10$

$13=1\cdot 10+3$

$10=3\cdot 3+1$

Now use the last equation to get an expression in $1$ and substitute into the other equations to express this in terms of $23$ and $13$.

So $1=10-3\cdot 3$.

Now $13=1\cdot 10+3\Leftrightarrow 3=13-10$ (we solve for the "remainder" for the substitution)

Now plug this in for $3$.

$1=10-3\cdot (13-10)=10-3\cdot 13+3\cdot 10=4\cdot 10-3\cdot 13$.

Proceed and solve the first equation for $10$.

$10=23-13$.

Plug this in:

$1=4(23-13)-3\cdot 13=4\cdot 23-4\cdot 13-3\cdot 13=4\cdot 23-7\cdot 13$.

Answer 3

How is this expression constructed $70 \times 415 - 69 \times 421$?

Using colors might be helpful.

$$\begin{align}1& = \color{red}{415} - 69(\color{blue}{421} - 1 \times \color{red}{415}) \\\\&=\color{red}{415} - 69\times \color{blue}{421} +69 \times\color{red}{415} \\\\&=\color{red}{415}+69 \times \color{red}{415} - 69\times \color{blue}{421} \\\\&=(1+69)\times \color{red}{415}- 69\times \color{blue}{421} \\\\&=70 \times \color{red}{415} - 69 \times \color{blue}{421}\end{align}$$

---

To get a solution $(x,y)$ of the equation $\color{purple}{2093}x+\color{orange}{836}y=1$, they started with $$\color{blue}{421}=\color{purple}{2093}-2\times \color{orange}{836}\tag1$$ $$\color{red}{415}=\color{orange}{836}-1\times \color{blue}{421}\tag2$$ $$\color{green}6=\color{blue}{421}-1\times \color{red}{415}\tag3$$ $$1=\color{red}{415}-69\times \color{green}6\tag4$$

They have $$\begin{align}1&=\color{red}{415}-69\times \color{green}6 \\\\&=\color{red}{415}-69\times (\color{blue}{421}-1\times \color{red}{415}) \\\\&=70 \times \color{red}{415} - 69 \times \color{blue}{421} \\\\&=70 \times (\color{orange}{836}-1\times \color{blue}{421})- 69 \times \color{blue}{421} \\\\&=70\times \color{orange}{836}-139\times \color{blue}{421} \\\\&=70\times \color{orange}{836}-139\times (\color{purple}{2093}-2\times \color{orange}{836}) \\\\&=\color{purple}{2093}\times (-139)+\color{orange}{836}\times 348\end{align}$$

Therefore, $(x,y)=(-139,348)$ is a solution of the equation $\color{purple}{2093}x+\color{orange}{836}y=1$.