The GCD of given numbers is 5.
Step 1 :
Divide $ 29030 $ by $ 1955 $ and get the remainder
The remainder is positive ($ 1660 > 0 $), so we will continue with division.
Step 2 :
Divide $ 1955 $ by $ \color{blue}{ 1660 } $ and get the remainder
The remainder is still positive ($ 295 > 0 $), so we will continue with division.
Step 3 :
Divide $ 1660 $ by $ \color{blue}{ 295 } $ and get the remainder
The remainder is still positive ($ 185 > 0 $), so we will continue with division.
Step 4 :
Divide $ 295 $ by $ \color{blue}{ 185 } $ and get the remainder
The remainder is still positive ($ 110 > 0 $), so we will continue with division.
Step 5 :
Divide $ 185 $ by $ \color{blue}{ 110 } $ and get the remainder
The remainder is still positive ($ 75 > 0 $), so we will continue with division.
Step 6 :
Divide $ 110 $ by $ \color{blue}{ 75 } $ and get the remainder
The remainder is still positive ($ 35 > 0 $), so we will continue with division.
Step 7 :
Divide $ 75 $ by $ \color{blue}{ 35 } $ and get the remainder
The remainder is still positive ($ 5 > 0 $), so we will continue with division.
Step 8 :
Divide $ 35 $ by $ \color{blue}{ 5 } $ and get the remainder
The remainder is zero => GCD is the last divisor $ \color{blue}{ \boxed { 5 }} $.
We can summarize an algorithm into a following table.
29030 | : | 1955 | = | 14 | remainder ( 1660 ) | ||||||||||||||
1955 | : | 1660 | = | 1 | remainder ( 295 ) | ||||||||||||||
1660 | : | 295 | = | 5 | remainder ( 185 ) | ||||||||||||||
295 | : | 185 | = | 1 | remainder ( 110 ) | ||||||||||||||
185 | : | 110 | = | 1 | remainder ( 75 ) | ||||||||||||||
110 | : | 75 | = | 1 | remainder ( 35 ) | ||||||||||||||
75 | : | 35 | = | 2 | remainder ( 5 ) | ||||||||||||||
35 | : | 5 | = | 7 | remainder ( 0 ) | ||||||||||||||
GCD = 5 |
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.