Discrete Math - Bézout Coefficients
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)$.
Related videos on Youtube
Tyridel
Updated on August 01, 2022Comments
-
Tyridel over 1 year
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
-
Tyridel about 12 yearsOoooohhhh, i was thinking of the problem in terms of algebra. What they are doing is saying that your multiplying 7 * 3, and adding another 3, so why not group it, and make it 8 * 3?
-
Zev Chonoles about 12 yearsYup, that's it! :)
-
Tyridel about 12 yearsWow, thanks a ton! Every time I think i have a handle on things...discrete math takes it to a whole new level :P