 Luciano Webster

2022-07-17

I'm taking a discrete math course, and were on Bézout Coefficients right now. I kind of understand the algorithm, the generalization. However the example in the book is throwing me off.
The steps in the Euclidean algorithm to find gcd(101,4620) are:
$\begin{array}{rl}4620& =45\cdot 101+75\\ 101& =1\cdot 75+26\\ 75& =2\cdot 26+23\\ 26& =1\cdot 23+3\\ 23& =7\cdot 3+2\\ 3& =1\cdot 2+1\\ 2& =2\cdot 1\end{array}$
This I understand. Now to find the Bézout coefficients they follow these steps.
$\begin{array}{rll}1& =3-1\cdot 2& \\ & =3-1\cdot \left(23-7\cdot 3\right)& =-1\cdot 23+8\cdot 3\\ & =-1\cdot 23+8\cdot \left(25-1\cdot 23\right)& =8\cdot 26-9\cdot 23\\ & =8\cdot 26-9\cdot \left(75-2\cdot 26\right)& =-0\cdot 75+26\cdot 26\\ & =-0\cdot 75+26\cdot \left(101-1\cdot 75\right)& =26\cdot 101-35\cdot 75\\ & =26\cdot 101-35\cdot \left(4620-45\cdot 101\right)& =-35\cdot 4620+1601\cdot 101\end{array}$
My problem is with the second line, where are they getting this +8 from? I've tried just about every algebraic trick I know, but I can't seem to find what they are actually doing.
I think I'm just missing some really simple algebra logic, but maybe I'm not understanding the steps to get Bézout coefficients? Bianca Chung

Expert

Step 1
Using the distributive property, which says that for any a,b,c,
$a\left(b+c\right)=ab+ac,$
we can see that
$3-1\cdot \left(23-7\cdot 3\right)=3+\left(-1\right)\cdot \left(23+\left(-7\right)\left(3\right)\right)=$
$3+\left(-1\right)\left(23\right)+\left(-1\right)\left(-7\right)\left(3\right)=\left(-1\right)\left(23\right)+3+\left(7\right)\left(3\right)=-1\cdot 23+8\cdot 3$
Step 2
In our case, we had $a=-1$, $b=23$, and $c=-21=\left(-7\right)\left(3\right)$

Do you have a similar question?