# Eulcidean Algorithim for GCD

• May 2nd 2013, 12:00 PM
kamui
Eulcidean Algorithim for GCD
Find the GCD for 198 and 765

I got as far as $765= 3 \times 198 +171$
I'm not sure what to do for the next step.
• May 2nd 2013, 01:17 PM
emakarov
Re: Eulcidean Algorithim for GCD
The next step is: 198 = 1 x 171 + 27. For each new step, you take the two rightmost numbers from the previous step.
• May 2nd 2013, 02:09 PM
Soroban
Re: Eulcidean Algorithim for GCD
ello, kamui!

Quote:

Find the GCD for 198 and 765

I got as far as: $765\:=\: 3 \times 198 +171$

I'm not sure what to do for the next step.

Then I guess you didn't really learn the Euclidean Algorithm.

1. Divide the larger number by the smaller.

2. Divide the divisor by the remainder.

3. Repeat step 2 until a zero remainder is achieved.

4. The GCD is the last divisor.

So we have:

. . $\begin{array}{ccccc}765 \div 198 &=& 3 & \text{rem.}171 \\ 198 \div 171 &=& 1 & \text{rem.}27 \\ 171 \div 27 &=& 6 & \text{rem.}9 \\ 27 \div {\color{red}9} &=& 3 & \text{rem.}0 \end{array}$

Therefore: . $\text{GCD}(198,765) \:=\:9$