Find Greatest Common Divisor of 28539 and 5088, using Euclidean algorithm.
Answer
The GCD of given numbers is 3.
Explanation
Step 1 :
Divide $ 28539 $ by $ 5088 $ and get the remainder
The remainder is positive ($ 3099 > 0 $), so we will continue with division.
Step 2 :
Divide $ 5088 $ by $ \color{blue}{ 3099 } $ and get the remainder
The remainder is still positive ($ 1989 > 0 $), so we will continue with division.
Step 3 :
Divide $ 3099 $ by $ \color{blue}{ 1989 } $ and get the remainder
The remainder is still positive ($ 1110 > 0 $), so we will continue with division.
Step 4 :
Divide $ 1989 $ by $ \color{blue}{ 1110 } $ and get the remainder
The remainder is still positive ($ 879 > 0 $), so we will continue with division.
Step 5 :
Divide $ 1110 $ by $ \color{blue}{ 879 } $ and get the remainder
The remainder is still positive ($ 231 > 0 $), so we will continue with division.
Step 6 :
Divide $ 879 $ by $ \color{blue}{ 231 } $ and get the remainder
The remainder is still positive ($ 186 > 0 $), so we will continue with division.
Step 7 :
Divide $ 231 $ by $ \color{blue}{ 186 } $ and get the remainder
The remainder is still positive ($ 45 > 0 $), so we will continue with division.
Step 8 :
Divide $ 186 $ by $ \color{blue}{ 45 } $ and get the remainder
The remainder is still positive ($ 6 > 0 $), so we will continue with division.
Step 9 :
Divide $ 45 $ by $ \color{blue}{ 6 } $ and get the remainder
The remainder is still positive ($ 3 > 0 $), so we will continue with division.
Step 10 :
Divide $ 6 $ by $ \color{blue}{ 3 } $ and get the remainder
The remainder is zero => GCD is the last divisor $ \color{blue}{ \boxed { 3 }} $.
We can summarize an algorithm into a following table.
| 28539 | : | 5088 | = | 5 | remainder ( 3099 ) | ||||||||||||||||||
| 5088 | : | 3099 | = | 1 | remainder ( 1989 ) | ||||||||||||||||||
| 3099 | : | 1989 | = | 1 | remainder ( 1110 ) | ||||||||||||||||||
| 1989 | : | 1110 | = | 1 | remainder ( 879 ) | ||||||||||||||||||
| 1110 | : | 879 | = | 1 | remainder ( 231 ) | ||||||||||||||||||
| 879 | : | 231 | = | 3 | remainder ( 186 ) | ||||||||||||||||||
| 231 | : | 186 | = | 1 | remainder ( 45 ) | ||||||||||||||||||
| 186 | : | 45 | = | 4 | remainder ( 6 ) | ||||||||||||||||||
| 45 | : | 6 | = | 7 | remainder ( 3 ) | ||||||||||||||||||
| 6 | : | 3 | = | 2 | remainder ( 0 ) | ||||||||||||||||||
| GCD = 3 | |||||||||||||||||||||||
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.