Find Greatest Common Divisor of 26513 and 32321, using Euclidean algorithm.
Answer
The GCD of given numbers is 1.
Explanation
Step 1 :
Divide $ 32321 $ by $ 26513 $ and get the remainder
The remainder is positive ($ 5808 > 0 $), so we will continue with division.
Step 2 :
Divide $ 26513 $ by $ \color{blue}{ 5808 } $ and get the remainder
The remainder is still positive ($ 3281 > 0 $), so we will continue with division.
Step 3 :
Divide $ 5808 $ by $ \color{blue}{ 3281 } $ and get the remainder
The remainder is still positive ($ 2527 > 0 $), so we will continue with division.
Step 4 :
Divide $ 3281 $ by $ \color{blue}{ 2527 } $ and get the remainder
The remainder is still positive ($ 754 > 0 $), so we will continue with division.
Step 5 :
Divide $ 2527 $ by $ \color{blue}{ 754 } $ and get the remainder
The remainder is still positive ($ 265 > 0 $), so we will continue with division.
Step 6 :
Divide $ 754 $ by $ \color{blue}{ 265 } $ and get the remainder
The remainder is still positive ($ 224 > 0 $), so we will continue with division.
Step 7 :
Divide $ 265 $ by $ \color{blue}{ 224 } $ and get the remainder
The remainder is still positive ($ 41 > 0 $), so we will continue with division.
Step 8 :
Divide $ 224 $ by $ \color{blue}{ 41 } $ and get the remainder
The remainder is still positive ($ 19 > 0 $), so we will continue with division.
Step 9 :
Divide $ 41 $ by $ \color{blue}{ 19 } $ and get the remainder
The remainder is still positive ($ 3 > 0 $), so we will continue with division.
Step 10 :
Divide $ 19 $ by $ \color{blue}{ 3 } $ and get the remainder
The remainder is still positive ($ 1 > 0 $), so we will continue with division.
Step 11 :
Divide $ 3 $ 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.
| 32321 | : | 26513 | = | 1 | remainder ( 5808 ) | ||||||||||||||||||||
| 26513 | : | 5808 | = | 4 | remainder ( 3281 ) | ||||||||||||||||||||
| 5808 | : | 3281 | = | 1 | remainder ( 2527 ) | ||||||||||||||||||||
| 3281 | : | 2527 | = | 1 | remainder ( 754 ) | ||||||||||||||||||||
| 2527 | : | 754 | = | 3 | remainder ( 265 ) | ||||||||||||||||||||
| 754 | : | 265 | = | 2 | remainder ( 224 ) | ||||||||||||||||||||
| 265 | : | 224 | = | 1 | remainder ( 41 ) | ||||||||||||||||||||
| 224 | : | 41 | = | 5 | remainder ( 19 ) | ||||||||||||||||||||
| 41 | : | 19 | = | 2 | remainder ( 3 ) | ||||||||||||||||||||
| 19 | : | 3 | = | 6 | remainder ( 1 ) | ||||||||||||||||||||
| 3 | : | 1 | = | 3 | remainder ( 0 ) | ||||||||||||||||||||
| GCD = 1 | |||||||||||||||||||||||||
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.