Find Greatest Common Divisor of 2447 and 3997, using Euclidean algorithm.
Answer
The GCD of given numbers is 1.
Explanation
Step 1 :
Divide $ 3997 $ by $ 2447 $ and get the remainder
The remainder is positive ($ 1550 > 0 $), so we will continue with division.
Step 2 :
Divide $ 2447 $ by $ \color{blue}{ 1550 } $ and get the remainder
The remainder is still positive ($ 897 > 0 $), so we will continue with division.
Step 3 :
Divide $ 1550 $ by $ \color{blue}{ 897 } $ and get the remainder
The remainder is still positive ($ 653 > 0 $), so we will continue with division.
Step 4 :
Divide $ 897 $ by $ \color{blue}{ 653 } $ and get the remainder
The remainder is still positive ($ 244 > 0 $), so we will continue with division.
Step 5 :
Divide $ 653 $ by $ \color{blue}{ 244 } $ and get the remainder
The remainder is still positive ($ 165 > 0 $), so we will continue with division.
Step 6 :
Divide $ 244 $ by $ \color{blue}{ 165 } $ and get the remainder
The remainder is still positive ($ 79 > 0 $), so we will continue with division.
Step 7 :
Divide $ 165 $ by $ \color{blue}{ 79 } $ and get the remainder
The remainder is still positive ($ 7 > 0 $), so we will continue with division.
Step 8 :
Divide $ 79 $ by $ \color{blue}{ 7 } $ and get the remainder
The remainder is still positive ($ 2 > 0 $), so we will continue with division.
Step 9 :
Divide $ 7 $ by $ \color{blue}{ 2 } $ and get the remainder
The remainder is still positive ($ 1 > 0 $), so we will continue with division.
Step 10 :
Divide $ 2 $ by $ \color{blue}{ 1 } $ and get the remainder
The remainder is zero => GCD is the last divisor $ \color{blue}{ \boxed { 1 }} $.
We can summarize an algorithm into a following table.
| 3997 | : | 2447 | = | 1 | remainder ( 1550 ) | ||||||||||||||||||
| 2447 | : | 1550 | = | 1 | remainder ( 897 ) | ||||||||||||||||||
| 1550 | : | 897 | = | 1 | remainder ( 653 ) | ||||||||||||||||||
| 897 | : | 653 | = | 1 | remainder ( 244 ) | ||||||||||||||||||
| 653 | : | 244 | = | 2 | remainder ( 165 ) | ||||||||||||||||||
| 244 | : | 165 | = | 1 | remainder ( 79 ) | ||||||||||||||||||
| 165 | : | 79 | = | 2 | remainder ( 7 ) | ||||||||||||||||||
| 79 | : | 7 | = | 11 | remainder ( 2 ) | ||||||||||||||||||
| 7 | : | 2 | = | 3 | remainder ( 1 ) | ||||||||||||||||||
| 2 | : | 1 | = | 2 | remainder ( 0 ) | ||||||||||||||||||
| GCD = 1 | |||||||||||||||||||||||
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.