Find Greatest Common Divisor of 34336550 and 120400, using Euclidean algorithm.
Answer
The GCD of given numbers is 50.
Explanation
Step 1 :
Divide $ 34336550 $ by $ 120400 $ and get the remainder
The remainder is positive ($ 22550 > 0 $), so we will continue with division.
Step 2 :
Divide $ 120400 $ by $ \color{blue}{ 22550 } $ and get the remainder
The remainder is still positive ($ 7650 > 0 $), so we will continue with division.
Step 3 :
Divide $ 22550 $ by $ \color{blue}{ 7650 } $ and get the remainder
The remainder is still positive ($ 7250 > 0 $), so we will continue with division.
Step 4 :
Divide $ 7650 $ by $ \color{blue}{ 7250 } $ and get the remainder
The remainder is still positive ($ 400 > 0 $), so we will continue with division.
Step 5 :
Divide $ 7250 $ by $ \color{blue}{ 400 } $ and get the remainder
The remainder is still positive ($ 50 > 0 $), so we will continue with division.
Step 6 :
Divide $ 400 $ by $ \color{blue}{ 50 } $ and get the remainder
The remainder is zero => GCD is the last divisor $ \color{blue}{ \boxed { 50 }} $.
We can summarize an algorithm into a following table.
| 34336550 | : | 120400 | = | 285 | remainder ( 22550 ) | ||||||||||
| 120400 | : | 22550 | = | 5 | remainder ( 7650 ) | ||||||||||
| 22550 | : | 7650 | = | 2 | remainder ( 7250 ) | ||||||||||
| 7650 | : | 7250 | = | 1 | remainder ( 400 ) | ||||||||||
| 7250 | : | 400 | = | 18 | remainder ( 50 ) | ||||||||||
| 400 | : | 50 | = | 8 | remainder ( 0 ) | ||||||||||
| GCD = 50 | |||||||||||||||
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.