Question

Find Greatest Common Divisor of 139024789 and 93278890, using Euclidean algorithm.

Answer

The GCD of given numbers is 1.

Explanation

Step 1 :
Divide $139024789$ by $93278890$ and get the remainder

139024789 : 93278890 = 1 ( remainder is 45745899)

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

Step 2 :
Divide $93278890$ by $45745899$ and get the remainder

93278890 : 45745899 = 2 ( remainder is 1787092)

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

Step 3 :
Divide $45745899$ by $1787092$ and get the remainder

45745899 : 1787092 = 25 ( remainder is 1068599)

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

Step 4 :
Divide $1787092$ by $1068599$ and get the remainder

1787092 : 1068599 = 1 ( remainder is 718493)

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

Step 5 :
Divide $1068599$ by $718493$ and get the remainder

1068599 : 718493 = 1 ( remainder is 350106)

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

Step 6 :
Divide $718493$ by $350106$ and get the remainder

718493 : 350106 = 2 ( remainder is 18281)

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

Step 7 :
Divide $350106$ by $18281$ and get the remainder

350106 : 18281 = 19 ( remainder is 2767)

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

Step 8 :
Divide $18281$ by $2767$ and get the remainder

18281 : 2767 = 6 ( remainder is 1679)

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

Step 9 :
Divide $2767$ by $1679$ and get the remainder

2767 : 1679 = 1 ( remainder is 1088)

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

Step 10 :
Divide $1679$ by $1088$ and get the remainder

1679 : 1088 = 1 ( remainder is 591)

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

Step 11 :
Divide $1088$ by $591$ and get the remainder

1088 : 591 = 1 ( remainder is 497)

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

Step 12 :
Divide $591$ by $497$ and get the remainder

591 : 497 = 1 ( remainder is 94)

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

Step 13 :
Divide $497$ by $94$ and get the remainder

497 : 94 = 5 ( remainder is 27)

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

Step 14 :
Divide $94$ by $27$ and get the remainder

94 : 27 = 3 ( remainder is 13)

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

Step 15 :
Divide $27$ by $13$ and get the remainder

27 : 13 = 2 ( remainder is 1)

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

Step 16 :
Divide $13$ by $1$ and get the remainder

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

139024789

93278890

1361

102149

9327889

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

This page was created using

GCD Calculator