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{align}
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{align}$$
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 (23 – 7 \cdot 3) &= -1 \cdot 23 + 8 \cdot 3 \\
&= -1 \cdot 23 + 8 \cdot (25 – 1 \cdot 23) &= 8 \cdot 26 – 9 \cdot 23 \\
&= 8 \cdot 26 – 9 \cdot (75 – 2 \cdot 26) &= -0 \cdot 75 + 26 \cdot 26 \\
&= -0 \cdot 75 + 26 \cdot (101 – 1 \cdot 75) &= 26 \cdot 101 – 35 \cdot 75 \\
&= 26 \cdot 101 – 35 \cdot (4620 – 45 \cdot 101) &= -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 algrebraic 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? Tried googling another source (that would be more clear) with no luck. Found calculators, so i know the answer in the back of the book is correct… just not sure how to get there. I've been doing so much discrete math this week my brain is kinda fried :S
Any help would be appreciated.
Thanks
Best Answer
Using the distributive property, which says that for any $a,b,c$, $$a(b+c)=ab+ac,$$ we can see that $$3 - 1 \cdot (23 - 7 \cdot 3) = 3+(-1)\cdot(23+(-7)(3))=$$ $$3+(-1)(23)+(-1)(-7)(3)=(-1)(23)+3+(7)(3)=-1\cdot 23 + 8 \cdot 3$$ In our case, we had $a=-1$, $b=23$, and $c=-21=(-7)(3)$.