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