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