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.

Printable View

- May 2nd 2013, 12:00 PMkamuiEulcidean 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. - May 2nd 2013, 01:17 PMemakarovRe: 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 PMSorobanRe: Eulcidean Algorithim for GCD
ello, kamui!

Quote:

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'tlearn the Euclidean Algorithm.*really*

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$