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 \text{ ( remainder is } \color{blue}{ 45745899 } \text{ ) } $$

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

Step 2 :
Divide $ 93278890 $ by $ \color{blue}{ 45745899 } $ and get the remainder

$$ 93278890 : 45745899 = 2 \text{ ( remainder is } \color{blue}{ 1787092 } \text{ ) } $$

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

Step 3 :
Divide $ 45745899 $ by $ \color{blue}{ 1787092 } $ and get the remainder

$$ 45745899 : 1787092 = 25 \text{ ( remainder is } \color{blue}{ 1068599 } \text{ ) } $$

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

Step 4 :
Divide $ 1787092 $ by $ \color{blue}{ 1068599 } $ and get the remainder

$$ 1787092 : 1068599 = 1 \text{ ( remainder is } \color{blue}{ 718493 } \text{ ) } $$

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

Step 5 :
Divide $ 1068599 $ by $ \color{blue}{ 718493 } $ and get the remainder

$$ 1068599 : 718493 = 1 \text{ ( remainder is } \color{blue}{ 350106 } \text{ ) } $$

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

Step 6 :
Divide $ 718493 $ by $ \color{blue}{ 350106 } $ and get the remainder

$$ 718493 : 350106 = 2 \text{ ( remainder is } \color{blue}{ 18281 } \text{ ) } $$

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

Step 7 :
Divide $ 350106 $ by $ \color{blue}{ 18281 } $ and get the remainder

$$ 350106 : 18281 = 19 \text{ ( remainder is } \color{blue}{ 2767 } \text{ ) } $$

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

Step 8 :
Divide $ 18281 $ by $ \color{blue}{ 2767 } $ and get the remainder

$$ 18281 : 2767 = 6 \text{ ( remainder is } \color{blue}{ 1679 } \text{ ) } $$

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

Step 9 :
Divide $ 2767 $ by $ \color{blue}{ 1679 } $ and get the remainder

$$ 2767 : 1679 = 1 \text{ ( remainder is } \color{blue}{ 1088 } \text{ ) } $$

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

Step 10 :
Divide $ 1679 $ by $ \color{blue}{ 1088 } $ and get the remainder

$$ 1679 : 1088 = 1 \text{ ( remainder is } \color{blue}{ 591 } \text{ ) } $$

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

Step 11 :
Divide $ 1088 $ by $ \color{blue}{ 591 } $ and get the remainder

$$ 1088 : 591 = 1 \text{ ( remainder is } \color{blue}{ 497 } \text{ ) } $$

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

Step 12 :
Divide $ 591 $ by $ \color{blue}{ 497 } $ and get the remainder

$$ 591 : 497 = 1 \text{ ( remainder is } \color{blue}{ 94 } \text{ ) } $$

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

Step 13 :
Divide $ 497 $ by $ \color{blue}{ 94 } $ and get the remainder

$$ 497 : 94 = 5 \text{ ( remainder is } \color{blue}{ 27 } \text{ ) } $$

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

Step 14 :
Divide $ 94 $ by $ \color{blue}{ 27 } $ and get the remainder

$$ 94 : 27 = 3 \text{ ( remainder is } \color{blue}{ 13 } \text{ ) } $$

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

Step 15 :
Divide $ 27 $ by $ \color{blue}{ 13 } $ and get the remainder

$$ 27 : 13 = 2 \text{ ( remainder is } \color{blue}{ 1 } \text{ ) } $$

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

Step 16 :
Divide $ 13 $ by $ \color{blue}{ 1 } $ and get the remainder

$$ 13 : \color{blue}{ \boxed { 1 }} = 13 \text{ ( remainder is } \color{blue}{ 0 } \text{ ) } $$

The remainder is zero => GCD is the last divisor $ \color{blue}{ \boxed { 1 }} $.

We can summarize an algorithm into a following table.

139024789	:	93278890	=	1	remainder ( 45745899 )
		93278890	:	45745899	=	2	remainder ( 1787092 )
				45745899	:	1787092	=	25	remainder ( 1068599 )
						1787092	:	1068599	=	1	remainder ( 718493 )
								1068599	:	718493	=	1	remainder ( 350106 )
										718493	:	350106	=	2	remainder ( 18281 )
												350106	:	18281	=	19	remainder ( 2767 )
														18281	:	2767	=	6	remainder ( 1679 )
																2767	:	1679	=	1	remainder ( 1088 )
																		1679	:	1088	=	1	remainder ( 591 )
																				1088	:	591	=	1	remainder ( 497 )
																						591	:	497	=	1	remainder ( 94 )
																								497	:	94	=	5	remainder ( 27 )
																										94	:	27	=	3	remainder ( 13 )
																												27	:	13	=	2	remainder ( 1 )
																														13	:	1	=	13	remainder ( 0 )
																														GCD = 1

This solution can be visualized using a Venn diagram.

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

This page was created using

GCD Calculator