Question

Find Greatest Common Divisor of 1147 and 899, using Euclidean algorithm.

Answer

The GCD of given numbers is 31.

Explanation

Step 1 :
Divide $1147$ by $899$ and get the remainder

1147 : 899 = 1 ( remainder is 248)

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

Step 2 :
Divide $899$ by $248$ and get the remainder

899 : 248 = 3 ( remainder is 155)

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

Step 3 :
Divide $248$ by $155$ and get the remainder

248 : 155 = 1 ( remainder is 93)

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

Step 4 :
Divide $155$ by $93$ and get the remainder

155 : 93 = 1 ( remainder is 62)

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

Step 5 :
Divide $93$ by $62$ and get the remainder

93 : 62 = 1 ( remainder is 31)

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

Step 6 :
Divide $62$ by $31$ and get the remainder

62 : 31 = 2 ( remainder is 0)

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

We can summarize an algorithm into a following table.

This solution can be visualized using a Venn diagram.

0,0

1147

899

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

This page was created using

GCD Calculator