# Thread: Eulcidean Algorithim for GCD

1. ## Eulcidean Algorithim for GCD

Find the GCD for 198 and 765

I got as far as $\displaystyle 765= 3 \times 198 +171$
I'm not sure what to do for the next step.

2. ## 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.

3. ## Re: Eulcidean Algorithim for GCD

ello, kamui!

Find the GCD for 198 and 765

I got as far as: $\displaystyle 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:

. . $\displaystyle \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: .$\displaystyle \text{GCD}(198,765) \:=\:9$