# Thread: Another GCD using Euclid's Algorithm

1. ## 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)

2. $\displaystyle \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?

3. Sorry I forgot to mention that I have to express it as ma + nb

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