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?

Question

I&#039;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&#039;ve tried just about every algebraic trick I know, but I can&#039;t seem to find what they are actually doing.I think I&#039;m just missing some really simple algebra logic, but maybe I&#039;m not understanding the steps to get Bézout coefficients?

Bianca Chung · Accepted Answer

Step 1Using 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  ⋅  3Step 2In our case, we had   a  =  −  1,   b  =  23, and   c  =  −  21  =  (  −  7  )  (  3  )