Question

Find Greatest Common Divisor of 1530099 and 171259, using Euclidean algorithm.

Answer

The GCD of given numbers is 1.

Explanation

Step 1 :
Divide $1530099$ by $171259$ and get the remainder

1530099 : 171259 = 8 ( remainder is 160027)

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

Step 2 :
Divide $171259$ by $160027$ and get the remainder

171259 : 160027 = 1 ( remainder is 11232)

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

Step 3 :
Divide $160027$ by $11232$ and get the remainder

160027 : 11232 = 14 ( remainder is 2779)

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

Step 4 :
Divide $11232$ by $2779$ and get the remainder

11232 : 2779 = 4 ( remainder is 116)

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

Step 5 :
Divide $2779$ by $116$ and get the remainder

2779 : 116 = 23 ( remainder is 111)

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

Step 6 :
Divide $116$ by $111$ and get the remainder

116 : 111 = 1 ( remainder is 5)

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

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

111 : 5 = 22 ( remainder is 1)

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

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

5 : 1 = 5 ( 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

1530099

171259

197

863

15569

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

This page was created using

GCD Calculator