Question

Find Greatest Common Divisor of 6897 and 11155, using Euclidean algorithm.

Answer

The GCD of given numbers is 1.

Explanation

Step 1 :
Divide $11155$ by $6897$ and get the remainder

11155 : 6897 = 1 ( remainder is 4258)

The remainder is positive ( $4258 > 0$ ), so we will continue with division.

Step 2 :
Divide $6897$ by $4258$ and get the remainder

6897 : 4258 = 1 ( remainder is 2639)

The remainder is still positive ( $2639 > 0$ ), so we will continue with division.

Step 3 :
Divide $4258$ by $2639$ and get the remainder

4258 : 2639 = 1 ( remainder is 1619)

The remainder is still positive ( $1619 > 0$ ), so we will continue with division.

Step 4 :
Divide $2639$ by $1619$ and get the remainder

2639 : 1619 = 1 ( remainder is 1020)

The remainder is still positive ( $1020 > 0$ ), so we will continue with division.

Step 5 :
Divide $1619$ by $1020$ and get the remainder

1619 : 1020 = 1 ( remainder is 599)

The remainder is still positive ( $599 > 0$ ), so we will continue with division.

Step 6 :
Divide $1020$ by $599$ and get the remainder

1020 : 599 = 1 ( remainder is 421)

The remainder is still positive ( $421 > 0$ ), so we will continue with division.

Step 7 :
Divide $599$ by $421$ and get the remainder

599 : 421 = 1 ( remainder is 178)

The remainder is still positive ( $178 > 0$ ), so we will continue with division.

Step 8 :
Divide $421$ by $178$ and get the remainder

421 : 178 = 2 ( remainder is 65)

The remainder is still positive ( $65 > 0$ ), so we will continue with division.

Step 9 :
Divide $178$ by $65$ and get the remainder

178 : 65 = 2 ( remainder is 48)

The remainder is still positive ( $48 > 0$ ), so we will continue with division.

Step 10 :
Divide $65$ by $48$ and get the remainder

65 : 48 = 1 ( remainder is 17)

The remainder is still positive ( $17 > 0$ ), so we will continue with division.

Step 11 :
Divide $48$ by $17$ and get the remainder

48 : 17 = 2 ( remainder is 14)

The remainder is still positive ( $14 > 0$ ), so we will continue with division.

Step 12 :
Divide $17$ by $14$ and get the remainder

17 : 14 = 1 ( remainder is 3)

The remainder is still positive ( $3 > 0$ ), so we will continue with division.

Step 13 :
Divide $14$ by $3$ and get the remainder

14 : 3 = 4 ( remainder is 2)

The remainder is still positive ( $2 > 0$ ), so we will continue with division.

Step 14 :
Divide $3$ by $2$ and get the remainder

3 : 2 = 1 ( remainder is 1)

The remainder is still positive ( $1 > 0$ ), so we will continue with division.

Step 15 :
Divide $2$ by $1$ and get the remainder

2 : 1 = 2 ( remainder is 0)

The remainder is zero => GCD is the last divisor $1$ .

We can summarize an algorithm into a following table.

This solution can be visualized using a Venn diagram.

0,0

6897

11155

The GCD equals the product of the numbers at the intersection.

This page was created using

GCD Calculator