Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

\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

share|improve this question
    
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. –  Bill Dubuque Apr 23 '11 at 15:45
    
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. –  André Nicolas Apr 23 '11 at 15:48
    
@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. –  André Nicolas Apr 23 '11 at 16:18
add comment

2 Answers

up vote 2 down vote accepted

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\:.$

share|improve this answer
    
i appreciate your help in showing the alternative methods. but i need to show workings for back-sub in my tutorials. –  optimus Apr 24 '11 at 1:39
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.