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
    @Bill Dubuque: My experience is precisely the same as yours. It is much easier to write a program to implement the Extended Euclidean $A$lgorithm. 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