Question

Find Greatest Common Divisor of 1369 and 2597, using Euclidean algorithm.

Answer

The GCD of given numbers is 1.

Explanation

Step 1 :
Divide $2597$ by $1369$ and get the remainder

2597 : 1369 = 1 ( remainder is 1228)

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

Step 2 :
Divide $1369$ by $1228$ and get the remainder

1369 : 1228 = 1 ( remainder is 141)

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

Step 3 :
Divide $1228$ by $141$ and get the remainder

1228 : 141 = 8 ( remainder is 100)

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

Step 4 :
Divide $141$ by $100$ and get the remainder

141 : 100 = 1 ( remainder is 41)

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

Step 5 :
Divide $100$ by $41$ and get the remainder

100 : 41 = 2 ( remainder is 18)

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

Step 6 :
Divide $41$ by $18$ and get the remainder

41 : 18 = 2 ( remainder is 5)

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

Step 7 :
Divide $18$ by $5$ and get the remainder

18 : 5 = 3 ( remainder is 3)

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

Step 8 :
Divide $5$ by $3$ and get the remainder

5 : 3 = 1 ( remainder is 2)

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

Step 9 :
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 10 :
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

1369

2597

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

This page was created using

GCD Calculator