Find Greatest Common Divisor of 589432167 and 3498762, using Euclidean algorithm.
Answer
The GCD of given numbers is 3.
Explanation
Step 1 :
Divide $ 589432167 $ by $ 3498762 $ and get the remainder
The remainder is positive ($ 1640151 > 0 $), so we will continue with division.
Step 2 :
Divide $ 3498762 $ by $ \color{blue}{ 1640151 } $ and get the remainder
The remainder is still positive ($ 218460 > 0 $), so we will continue with division.
Step 3 :
Divide $ 1640151 $ by $ \color{blue}{ 218460 } $ and get the remainder
The remainder is still positive ($ 110931 > 0 $), so we will continue with division.
Step 4 :
Divide $ 218460 $ by $ \color{blue}{ 110931 } $ and get the remainder
The remainder is still positive ($ 107529 > 0 $), so we will continue with division.
Step 5 :
Divide $ 110931 $ by $ \color{blue}{ 107529 } $ and get the remainder
The remainder is still positive ($ 3402 > 0 $), so we will continue with division.
Step 6 :
Divide $ 107529 $ by $ \color{blue}{ 3402 } $ and get the remainder
The remainder is still positive ($ 2067 > 0 $), so we will continue with division.
Step 7 :
Divide $ 3402 $ by $ \color{blue}{ 2067 } $ and get the remainder
The remainder is still positive ($ 1335 > 0 $), so we will continue with division.
Step 8 :
Divide $ 2067 $ by $ \color{blue}{ 1335 } $ and get the remainder
The remainder is still positive ($ 732 > 0 $), so we will continue with division.
Step 9 :
Divide $ 1335 $ by $ \color{blue}{ 732 } $ and get the remainder
The remainder is still positive ($ 603 > 0 $), so we will continue with division.
Step 10 :
Divide $ 732 $ by $ \color{blue}{ 603 } $ and get the remainder
The remainder is still positive ($ 129 > 0 $), so we will continue with division.
Step 11 :
Divide $ 603 $ by $ \color{blue}{ 129 } $ and get the remainder
The remainder is still positive ($ 87 > 0 $), so we will continue with division.
Step 12 :
Divide $ 129 $ by $ \color{blue}{ 87 } $ and get the remainder
The remainder is still positive ($ 42 > 0 $), so we will continue with division.
Step 13 :
Divide $ 87 $ by $ \color{blue}{ 42 } $ and get the remainder
The remainder is still positive ($ 3 > 0 $), so we will continue with division.
Step 14 :
Divide $ 42 $ by $ \color{blue}{ 3 } $ and get the remainder
The remainder is zero => GCD is the last divisor $ \color{blue}{ \boxed { 3 }} $.
We can summarize an algorithm into a following table.
| 589432167 | : | 3498762 | = | 168 | remainder ( 1640151 ) | ||||||||||||||||||||||||||
| 3498762 | : | 1640151 | = | 2 | remainder ( 218460 ) | ||||||||||||||||||||||||||
| 1640151 | : | 218460 | = | 7 | remainder ( 110931 ) | ||||||||||||||||||||||||||
| 218460 | : | 110931 | = | 1 | remainder ( 107529 ) | ||||||||||||||||||||||||||
| 110931 | : | 107529 | = | 1 | remainder ( 3402 ) | ||||||||||||||||||||||||||
| 107529 | : | 3402 | = | 31 | remainder ( 2067 ) | ||||||||||||||||||||||||||
| 3402 | : | 2067 | = | 1 | remainder ( 1335 ) | ||||||||||||||||||||||||||
| 2067 | : | 1335 | = | 1 | remainder ( 732 ) | ||||||||||||||||||||||||||
| 1335 | : | 732 | = | 1 | remainder ( 603 ) | ||||||||||||||||||||||||||
| 732 | : | 603 | = | 1 | remainder ( 129 ) | ||||||||||||||||||||||||||
| 603 | : | 129 | = | 4 | remainder ( 87 ) | ||||||||||||||||||||||||||
| 129 | : | 87 | = | 1 | remainder ( 42 ) | ||||||||||||||||||||||||||
| 87 | : | 42 | = | 2 | remainder ( 3 ) | ||||||||||||||||||||||||||
| 42 | : | 3 | = | 14 | remainder ( 0 ) | ||||||||||||||||||||||||||
| GCD = 3 | |||||||||||||||||||||||||||||||
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.