0
$\begingroup$

\begin{align} 1414 &= 888 \cdot1 + 526 \qquad(1)\\ 888 &= 526 \cdot2 + 362 \qquad(2)\\ 526 &= 362 \cdot1 + 164 \qquad(3)\\ 362 &= 164 \cdot2 + 34 \,\,\,\qquad(4)\\ 164 &= 34 \cdot4 + 28 \quad\qquad(5)\\ 34 &= 28 \cdot1 + 6 \quad\,\,\,\qquad(6)\\ 28 &= 6 \cdot4 + 4 \qquad\qquad(7)\\ 6 &= 4 \cdot1 + 2 \qquad\qquad(8)\\ 4 &= 2 \cdot2 + 0 \qquad\qquad(9)\\ \end{align}

Back-substitute \begin{align} 2 &= 6 - 4 \qquad \qquad\qquad\qquad\qquad\qquad\qquad\,(8) \\ 2 &= 6 - 28 \cdot4 \qquad\qquad\qquad\qquad\qquad\qquad\,\,\,(7)\\ 2 &= 34 - 28 - 28 - 6 \cdot4 \qquad\qquad\qquad\qquad\,\,(6) \\ 2 &= 34 - 164 - 34 \cdot4 - 164 - 34 \cdot4 - 6 \cdot4 \quad(5) \\ 2 &= 34 - 2 \cdot164 - 38 \cdot8 - 6 \cdot4 \\ 2 &= 362 - 2 \cdot164 - 2 \cdot164 - 34 \cdot8 - 6 \cdot4 \,\,\quad(4) \end{align}

I always have problem backsub the equation using euclidean method.

Can anyone advise? I have done similar question but yet as the equations result is long, it gets very messy.

Euclidean algorithm to find the GCD

  • 0
    Why not use the augmented Euclidean algorithm that I mentioned in your linked question? Much experience leads me to believe that students make far fewer errors using this technique vs. back substitution. If you have questions about it please feel free to ask there.2011-04-23
  • 0
    The second line, labelled ($2$), has a typo. You want $888=526 \times 1+362$. The back substitutions are mishandled. Try using parentheses for clarity.2011-04-23
  • 0
    @Bill Dubuque: My experience is precisely the same as yours. It is much easier to write a program to implement the Extended Euclidean Algorithm. And even by hand for the usual small examples, Extended Euclidean Algorithm is easier to carry out correctly. Unfortunately, many homework exercises specify that back substitution must be used.2011-04-23

2 Answers 2

2

It's simpler to use the identity-augmented method I described in your prior post. Here we get:

1414    1    0  888    0    1  526    1   -1  362   -1    2  164    2   -3   34   -5    8   28   22  -35    6  -27   43      4  130 -207    2 -157  250 

Thus $\rm\ \ 2\ =\: -157\cdot 1414\ +\ 250\cdot 888\:.$

  • 0
    i appreciate your help in showing the alternative methods. but i need to show workings for back-sub in my tutorials.2011-04-24
2

Your second line of backsubstitution is wrong-the RHS is -106. You should replace the 4 with 28-6x4, getting 2=6x5-28. Then you should never have more than two terms on the right. The next step is to replace the 6 with 34-28, getting 2=5x34-6x28