Discrete Math - Bézout Coefficients

6,566

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

Share:
6,566

Related videos on Youtube

Tyridel
Author by

Tyridel

Updated on August 01, 2022

Comments

  • Tyridel
    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
    Tyridel about 12 years
    Ooooohhhh, 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
    Zev Chonoles about 12 years
    Yup, that's it! :)
  • Tyridel
    Tyridel about 12 years
    Wow, thanks a ton! Every time I think i have a handle on things...discrete math takes it to a whole new level :P