# About reversing the Euclidean Algorithm, Lemma of Bézout

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]

• Count how many $415$s are in that expression. (Answer: $1+69$.) Commented Mar 13 at 18:13
• $415-69(-1\times415)=(1-(-69))(415)=70\times415$ Commented Mar 13 at 18:14
• You combine the $415$ terms and separate them from the $421$ term Commented Mar 13 at 18:24
• Imagine if it was $x-69(y-x)$. Can you see how that equals $70x-69y$? Commented Mar 13 at 19:47
• Wow. A fifty point bounty for a canonical explanation for a line or two of elementary high school algebra. That should attract lots of identical answers. Commented Mar 16 at 15:47

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$$.

• How do you go from: $= 415 - 69 \times 421 + 69 \times 415$ to $= 415 + 69 \times 415 - 69 \times 421$ and from this to: $= (1 + 69) \times 415 - 69 \times 421$ ? I don't understand the steps and transitions that's happening there! Commented Mar 17 at 7:32
• @Alix Blaine : Since we have that $A-B+C$ is equal to $A+C-B$, setting $A=415,B=69\times 421$ and $C=69\times 415$ gives $$415−69×421+69×415$$$$=415+69×415−69×421$$ Next, since we have that $E\times D+F\times D-G$ is equal to $(E+F)\times D-G$, setting $D=415,E=1,F=69$ and $G=69\times 421$ gives $$415+69×415−69×421$$$$=1\times 415+69\times 415-69\times 421$$$$=(1+69)\times 415-69\times 421$$ Commented Mar 17 at 8:04
• So you are doing some re-writing? Commented Mar 17 at 9:35
• Any link where I can learn about this? Commented Mar 17 at 9:36
• @Alix Blaine : "you are doing some re-writing?" Yes, I am. "Any link where I can learn about this?" You might want to see this. "How to you arrive here: $1×415+69×415−69×421$" Since we have that $A+B−C$ is equal to $1×A+B−C$ (just rewriting $A$ as $1\times A$), setting $A=415,B=69×415$ and $C=69×421$, we have $$415+69×415−69×421$$ $$=1×415+69×415−69×421$$ Commented Mar 17 at 14:27

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$$.

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$$.

• Hi, I am super confused by $r_n$ in your examples. Commented Mar 16 at 11:06
• Can you simplify this with those numbers from the book example? Commented Mar 16 at 11:07
• @AlixBlaine The $r_n$'s are consecutive remainders of the Euclidean algorithm. They are used to indicate what is going on. Yes, we can skip them, but then the calculations will become a distributivity exercise. :-) Commented Mar 16 at 11:23
• What do you mean by "a distributivity exercise"? Commented Mar 16 at 11:27
• @AlixBlaine A sequence of arithmetic transformations, based on the distributive law, for instance: $1=415-69\times 6=415-69\times (421-415)=-69\times 421+70\times 415= -69\times 421+70\times (836-1\times 421)=70\times 836-139\times 421= 70\times 836-139\times (2093-2\times 836)=-139\times 2093+348\times 836.$ I think, this does not explain a lot what is going on and from where we obtained the respective numbers. Commented Mar 16 at 11:35