The GCD of given numbers is 1.
Step 1 :
Divide $ 761457 $ by $ 614573 $ and get the remainder
The remainder is positive ($ 146884 > 0 $), so we will continue with division.
Step 2 :
Divide $ 614573 $ by $ \color{blue}{ 146884 } $ and get the remainder
The remainder is still positive ($ 27037 > 0 $), so we will continue with division.
Step 3 :
Divide $ 146884 $ by $ \color{blue}{ 27037 } $ and get the remainder
The remainder is still positive ($ 11699 > 0 $), so we will continue with division.
Step 4 :
Divide $ 27037 $ by $ \color{blue}{ 11699 } $ and get the remainder
The remainder is still positive ($ 3639 > 0 $), so we will continue with division.
Step 5 :
Divide $ 11699 $ by $ \color{blue}{ 3639 } $ and get the remainder
The remainder is still positive ($ 782 > 0 $), so we will continue with division.
Step 6 :
Divide $ 3639 $ by $ \color{blue}{ 782 } $ and get the remainder
The remainder is still positive ($ 511 > 0 $), so we will continue with division.
Step 7 :
Divide $ 782 $ by $ \color{blue}{ 511 } $ and get the remainder
The remainder is still positive ($ 271 > 0 $), so we will continue with division.
Step 8 :
Divide $ 511 $ by $ \color{blue}{ 271 } $ and get the remainder
The remainder is still positive ($ 240 > 0 $), so we will continue with division.
Step 9 :
Divide $ 271 $ by $ \color{blue}{ 240 } $ and get the remainder
The remainder is still positive ($ 31 > 0 $), so we will continue with division.
Step 10 :
Divide $ 240 $ by $ \color{blue}{ 31 } $ and get the remainder
The remainder is still positive ($ 23 > 0 $), so we will continue with division.
Step 11 :
Divide $ 31 $ by $ \color{blue}{ 23 } $ and get the remainder
The remainder is still positive ($ 8 > 0 $), so we will continue with division.
Step 12 :
Divide $ 23 $ by $ \color{blue}{ 8 } $ and get the remainder
The remainder is still positive ($ 7 > 0 $), so we will continue with division.
Step 13 :
Divide $ 8 $ by $ \color{blue}{ 7 } $ and get the remainder
The remainder is still positive ($ 1 > 0 $), so we will continue with division.
Step 14 :
Divide $ 7 $ 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.
761457 | : | 614573 | = | 1 | remainder ( 146884 ) | ||||||||||||||||||||||||||
614573 | : | 146884 | = | 4 | remainder ( 27037 ) | ||||||||||||||||||||||||||
146884 | : | 27037 | = | 5 | remainder ( 11699 ) | ||||||||||||||||||||||||||
27037 | : | 11699 | = | 2 | remainder ( 3639 ) | ||||||||||||||||||||||||||
11699 | : | 3639 | = | 3 | remainder ( 782 ) | ||||||||||||||||||||||||||
3639 | : | 782 | = | 4 | remainder ( 511 ) | ||||||||||||||||||||||||||
782 | : | 511 | = | 1 | remainder ( 271 ) | ||||||||||||||||||||||||||
511 | : | 271 | = | 1 | remainder ( 240 ) | ||||||||||||||||||||||||||
271 | : | 240 | = | 1 | remainder ( 31 ) | ||||||||||||||||||||||||||
240 | : | 31 | = | 7 | remainder ( 23 ) | ||||||||||||||||||||||||||
31 | : | 23 | = | 1 | remainder ( 8 ) | ||||||||||||||||||||||||||
23 | : | 8 | = | 2 | remainder ( 7 ) | ||||||||||||||||||||||||||
8 | : | 7 | = | 1 | remainder ( 1 ) | ||||||||||||||||||||||||||
7 | : | 1 | = | 7 | remainder ( 0 ) | ||||||||||||||||||||||||||
GCD = 1 |
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.