most recent 30 from http://mathoverflow.net 2013-05-25T13:59:10Z http://mathoverflow.net/feeds/question/79187 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79187/discrete-math-bezout-coefficients Tyridel 2011-10-26T20:02:00Z 2011-10-26T21:03:29Z

<p>I'm taking a discrete math course, and were on Bezout Coefficients right now. I kind of understand the algorithm, the generalization. However the example in the book is throwing me off.</p> <p>The steps in the Euclidean algorithm to find gcd(101, 4620) are:</p> <p>4620 = 45 * 101 + 75<br> 101 = 1 * 75 + 26<br> 75 = 2 * 26 + 23<br> 26 = 1 * 23 + 3<br> 23 = 7 * 3 + 2<br> 3 = 1 * 2 + 1<br> 2 = 2 * 1</p> <p>This i understand. Now to find the Bezout Coefficients they follow these steps.<br> 1 = 3 - 1 * 2<br> = 3 - 1 * (23 - 7 * 3) = -1 * 23 + 8 * 3<br> = -1 * 23 + 8 * (25 - 1 * 23) = 8 * 26 - 9 * 23<br> = 8 * 26 - 9 * (75 - 2 * 26) = -0 * 75 + 26 * 26<br> = -0 * 75 _ 26 * (101 - 1 * 75) = 26 * 101 - 35 * 75<br> = 26 * 101 - 35 * (4620 - 45 * 101) = -35 * 4620 + 1601 * 101 </p> <p>My problem is with the second line, where are they getting this + 8 from? I think i'm just missing some really simple algebra logic, but i've been doing so much discrete math this week my brain is kinda fried :S</p> <p>Any help would be appreciated.</p> <p>Thanks</p>