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