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.

Luciano Webster

Luciano Webster

Answered question

2022-07-17

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:
4620 = 45 101 + 75 101 = 1 75 + 26 75 = 2 26 + 23 26 = 1 23 + 3 23 = 7 3 + 2 3 = 1 2 + 1 2 = 2 1
This I understand. Now to find the Bézout coefficients they follow these steps.
1 = 3 1 2 = 3 1 ( 23 7 3 ) = 1 23 + 8 3 = 1 23 + 8 ( 25 1 23 ) = 8 26 9 23 = 8 26 9 ( 75 2 26 ) = 0 75 + 26 26 = 0 75 + 26 ( 101 1 75 ) = 26 101 35 75 = 26 101 35 ( 4620 45 101 ) = 35 4620 + 1601 101
My problem is with the second line, where are they getting this +8 from? I've tried just about every algebraic 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?

Answer & Explanation

Bianca Chung

Bianca Chung

Beginner2022-07-18Added 16 answers

Step 1
Using the distributive property, which says that for any a,b,c,
a ( b + c ) = a b + a c ,
we can see that
3 1 ( 23 7 3 ) = 3 + ( 1 ) ( 23 + ( 7 ) ( 3 ) ) =
3 + ( 1 ) ( 23 ) + ( 1 ) ( 7 ) ( 3 ) = ( 1 ) ( 23 ) + 3 + ( 7 ) ( 3 ) = 1 23 + 8 3
Step 2
In our case, we had a = 1, b = 23, and c = 21 = ( 7 ) ( 3 )

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?