Find Greatest Common Divisor of 1243564 and 45267964, using Euclidean algorithm.
Answer
The GCD of given numbers is 28.
Explanation
Step 1 :
Divide $ 45267964 $ by $ 1243564 $ and get the remainder
The remainder is positive ($ 499660 > 0 $), so we will continue with division.
Step 2 :
Divide $ 1243564 $ by $ \color{blue}{ 499660 } $ and get the remainder
The remainder is still positive ($ 244244 > 0 $), so we will continue with division.
Step 3 :
Divide $ 499660 $ by $ \color{blue}{ 244244 } $ and get the remainder
The remainder is still positive ($ 11172 > 0 $), so we will continue with division.
Step 4 :
Divide $ 244244 $ by $ \color{blue}{ 11172 } $ and get the remainder
The remainder is still positive ($ 9632 > 0 $), so we will continue with division.
Step 5 :
Divide $ 11172 $ by $ \color{blue}{ 9632 } $ and get the remainder
The remainder is still positive ($ 1540 > 0 $), so we will continue with division.
Step 6 :
Divide $ 9632 $ by $ \color{blue}{ 1540 } $ and get the remainder
The remainder is still positive ($ 392 > 0 $), so we will continue with division.
Step 7 :
Divide $ 1540 $ by $ \color{blue}{ 392 } $ and get the remainder
The remainder is still positive ($ 364 > 0 $), so we will continue with division.
Step 8 :
Divide $ 392 $ by $ \color{blue}{ 364 } $ and get the remainder
The remainder is still positive ($ 28 > 0 $), so we will continue with division.
Step 9 :
Divide $ 364 $ by $ \color{blue}{ 28 } $ and get the remainder
The remainder is zero => GCD is the last divisor $ \color{blue}{ \boxed { 28 }} $.
We can summarize an algorithm into a following table.
| 45267964 | : | 1243564 | = | 36 | remainder ( 499660 ) | ||||||||||||||||
| 1243564 | : | 499660 | = | 2 | remainder ( 244244 ) | ||||||||||||||||
| 499660 | : | 244244 | = | 2 | remainder ( 11172 ) | ||||||||||||||||
| 244244 | : | 11172 | = | 21 | remainder ( 9632 ) | ||||||||||||||||
| 11172 | : | 9632 | = | 1 | remainder ( 1540 ) | ||||||||||||||||
| 9632 | : | 1540 | = | 6 | remainder ( 392 ) | ||||||||||||||||
| 1540 | : | 392 | = | 3 | remainder ( 364 ) | ||||||||||||||||
| 392 | : | 364 | = | 1 | remainder ( 28 ) | ||||||||||||||||
| 364 | : | 28 | = | 13 | remainder ( 0 ) | ||||||||||||||||
| GCD = 28 | |||||||||||||||||||||
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.