Another GCD using Euclid's Algorithm

Printable View

September 23rd 2008, 07:35 AM
helpinmath

Another GCD using Euclid's Algorithm

Here is another problem that I think I may have gotten right. Can someone help me? What do you get?

(85,65)
September 23rd 2008, 08:45 AM
o_O

$\begin{array}{rcl} 85 & = & (1)({\color{red}65}) + {\color{blue}20} \\ {\color{red}65} & = & (3)({\color{blue}20}) + {\color{magenta}5} \\ {\color{blue}20} & = & 4({\color{magenta}5}) + 0 \end{array}$

So by Euclid's algorithm, (85, 65) = ... = ... ? Can you conclude?
September 23rd 2008, 08:54 AM
helpinmath

Sorry I forgot to mention that I have to express it as ma + nb
September 23rd 2008, 09:03 AM
o_O

Ok well, we can see that (85,65) = (65,20) = (20,5) = (5,0) = 5.

So, going with what I did in my earlier post:
$\begin{array}{rcll}5 & = & 65 - 3(20) & \text{Rearranged the second line} \\ 5 & = & 65 - 3 \left(85 - 65\right) & \text{Used the first line (rearranged)} \\ & \vdots & \end{array}$

Just a matter of simplifying.

All times are GMT -8. The time now is 04:25 AM.