Find Greatest Common Divisor of 530778276 and 999983, using Euclidean algorithm.
Answer
The GCD of given numbers is 1.
Explanation
Step 1 :
Divide $ 530778276 $ by $ 999983 $ and get the remainder
The remainder is positive ($ 787286 > 0 $), so we will continue with division.
Step 2 :
Divide $ 999983 $ by $ \color{blue}{ 787286 } $ and get the remainder
The remainder is still positive ($ 212697 > 0 $), so we will continue with division.
Step 3 :
Divide $ 787286 $ by $ \color{blue}{ 212697 } $ and get the remainder
The remainder is still positive ($ 149195 > 0 $), so we will continue with division.
Step 4 :
Divide $ 212697 $ by $ \color{blue}{ 149195 } $ and get the remainder
The remainder is still positive ($ 63502 > 0 $), so we will continue with division.
Step 5 :
Divide $ 149195 $ by $ \color{blue}{ 63502 } $ and get the remainder
The remainder is still positive ($ 22191 > 0 $), so we will continue with division.
Step 6 :
Divide $ 63502 $ by $ \color{blue}{ 22191 } $ and get the remainder
The remainder is still positive ($ 19120 > 0 $), so we will continue with division.
Step 7 :
Divide $ 22191 $ by $ \color{blue}{ 19120 } $ and get the remainder
The remainder is still positive ($ 3071 > 0 $), so we will continue with division.
Step 8 :
Divide $ 19120 $ by $ \color{blue}{ 3071 } $ and get the remainder
The remainder is still positive ($ 694 > 0 $), so we will continue with division.
Step 9 :
Divide $ 3071 $ by $ \color{blue}{ 694 } $ and get the remainder
The remainder is still positive ($ 295 > 0 $), so we will continue with division.
Step 10 :
Divide $ 694 $ by $ \color{blue}{ 295 } $ and get the remainder
The remainder is still positive ($ 104 > 0 $), so we will continue with division.
Step 11 :
Divide $ 295 $ by $ \color{blue}{ 104 } $ and get the remainder
The remainder is still positive ($ 87 > 0 $), so we will continue with division.
Step 12 :
Divide $ 104 $ by $ \color{blue}{ 87 } $ and get the remainder
The remainder is still positive ($ 17 > 0 $), so we will continue with division.
Step 13 :
Divide $ 87 $ by $ \color{blue}{ 17 } $ and get the remainder
The remainder is still positive ($ 2 > 0 $), so we will continue with division.
Step 14 :
Divide $ 17 $ by $ \color{blue}{ 2 } $ and get the remainder
The remainder is still positive ($ 1 > 0 $), so we will continue with division.
Step 15 :
Divide $ 2 $ 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.
| 530778276 | : | 999983 | = | 530 | remainder ( 787286 ) | ||||||||||||||||||||||||||||
| 999983 | : | 787286 | = | 1 | remainder ( 212697 ) | ||||||||||||||||||||||||||||
| 787286 | : | 212697 | = | 3 | remainder ( 149195 ) | ||||||||||||||||||||||||||||
| 212697 | : | 149195 | = | 1 | remainder ( 63502 ) | ||||||||||||||||||||||||||||
| 149195 | : | 63502 | = | 2 | remainder ( 22191 ) | ||||||||||||||||||||||||||||
| 63502 | : | 22191 | = | 2 | remainder ( 19120 ) | ||||||||||||||||||||||||||||
| 22191 | : | 19120 | = | 1 | remainder ( 3071 ) | ||||||||||||||||||||||||||||
| 19120 | : | 3071 | = | 6 | remainder ( 694 ) | ||||||||||||||||||||||||||||
| 3071 | : | 694 | = | 4 | remainder ( 295 ) | ||||||||||||||||||||||||||||
| 694 | : | 295 | = | 2 | remainder ( 104 ) | ||||||||||||||||||||||||||||
| 295 | : | 104 | = | 2 | remainder ( 87 ) | ||||||||||||||||||||||||||||
| 104 | : | 87 | = | 1 | remainder ( 17 ) | ||||||||||||||||||||||||||||
| 87 | : | 17 | = | 5 | remainder ( 2 ) | ||||||||||||||||||||||||||||
| 17 | : | 2 | = | 8 | remainder ( 1 ) | ||||||||||||||||||||||||||||
| 2 | : | 1 | = | 2 | remainder ( 0 ) | ||||||||||||||||||||||||||||
| GCD = 1 | |||||||||||||||||||||||||||||||||
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.