The GCD of given numbers is 6.
Step 1 :
Divide $ 63018702 $ by $ 11388300 $ and get the remainder
The remainder is positive ($ 6077202 > 0 $), so we will continue with division.
Step 2 :
Divide $ 11388300 $ by $ \color{blue}{ 6077202 } $ and get the remainder
The remainder is still positive ($ 5311098 > 0 $), so we will continue with division.
Step 3 :
Divide $ 6077202 $ by $ \color{blue}{ 5311098 } $ and get the remainder
The remainder is still positive ($ 766104 > 0 $), so we will continue with division.
Step 4 :
Divide $ 5311098 $ by $ \color{blue}{ 766104 } $ and get the remainder
The remainder is still positive ($ 714474 > 0 $), so we will continue with division.
Step 5 :
Divide $ 766104 $ by $ \color{blue}{ 714474 } $ and get the remainder
The remainder is still positive ($ 51630 > 0 $), so we will continue with division.
Step 6 :
Divide $ 714474 $ by $ \color{blue}{ 51630 } $ and get the remainder
The remainder is still positive ($ 43284 > 0 $), so we will continue with division.
Step 7 :
Divide $ 51630 $ by $ \color{blue}{ 43284 } $ and get the remainder
The remainder is still positive ($ 8346 > 0 $), so we will continue with division.
Step 8 :
Divide $ 43284 $ by $ \color{blue}{ 8346 } $ and get the remainder
The remainder is still positive ($ 1554 > 0 $), so we will continue with division.
Step 9 :
Divide $ 8346 $ by $ \color{blue}{ 1554 } $ and get the remainder
The remainder is still positive ($ 576 > 0 $), so we will continue with division.
Step 10 :
Divide $ 1554 $ by $ \color{blue}{ 576 } $ and get the remainder
The remainder is still positive ($ 402 > 0 $), so we will continue with division.
Step 11 :
Divide $ 576 $ by $ \color{blue}{ 402 } $ and get the remainder
The remainder is still positive ($ 174 > 0 $), so we will continue with division.
Step 12 :
Divide $ 402 $ by $ \color{blue}{ 174 } $ and get the remainder
The remainder is still positive ($ 54 > 0 $), so we will continue with division.
Step 13 :
Divide $ 174 $ by $ \color{blue}{ 54 } $ and get the remainder
The remainder is still positive ($ 12 > 0 $), so we will continue with division.
Step 14 :
Divide $ 54 $ by $ \color{blue}{ 12 } $ and get the remainder
The remainder is still positive ($ 6 > 0 $), so we will continue with division.
Step 15 :
Divide $ 12 $ by $ \color{blue}{ 6 } $ and get the remainder
The remainder is zero => GCD is the last divisor $ \color{blue}{ \boxed { 6 }} $.
We can summarize an algorithm into a following table.
63018702 | : | 11388300 | = | 5 | remainder ( 6077202 ) | ||||||||||||||||||||||||||||
11388300 | : | 6077202 | = | 1 | remainder ( 5311098 ) | ||||||||||||||||||||||||||||
6077202 | : | 5311098 | = | 1 | remainder ( 766104 ) | ||||||||||||||||||||||||||||
5311098 | : | 766104 | = | 6 | remainder ( 714474 ) | ||||||||||||||||||||||||||||
766104 | : | 714474 | = | 1 | remainder ( 51630 ) | ||||||||||||||||||||||||||||
714474 | : | 51630 | = | 13 | remainder ( 43284 ) | ||||||||||||||||||||||||||||
51630 | : | 43284 | = | 1 | remainder ( 8346 ) | ||||||||||||||||||||||||||||
43284 | : | 8346 | = | 5 | remainder ( 1554 ) | ||||||||||||||||||||||||||||
8346 | : | 1554 | = | 5 | remainder ( 576 ) | ||||||||||||||||||||||||||||
1554 | : | 576 | = | 2 | remainder ( 402 ) | ||||||||||||||||||||||||||||
576 | : | 402 | = | 1 | remainder ( 174 ) | ||||||||||||||||||||||||||||
402 | : | 174 | = | 2 | remainder ( 54 ) | ||||||||||||||||||||||||||||
174 | : | 54 | = | 3 | remainder ( 12 ) | ||||||||||||||||||||||||||||
54 | : | 12 | = | 4 | remainder ( 6 ) | ||||||||||||||||||||||||||||
12 | : | 6 | = | 2 | remainder ( 0 ) | ||||||||||||||||||||||||||||
GCD = 6 |
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.