Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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|improve this answer
    
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? –  Tyridel Oct 26 '11 at 20:55
    
Yup, that's it! :) –  Zev Chonoles Oct 26 '11 at 20:57
    
Wow, thanks a ton! Every time I think i have a handle on things...discrete math takes it to a whole new level :P –  Tyridel Oct 26 '11 at 20:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.