The GCD of given numbers is 28.
Step 1 :
Divide by and get the remainder
The remainder is positive (), so we will continue with division.
Step 2 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 3 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 4 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 5 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 6 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 7 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 8 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 9 :
Divide by and get the remainder
The remainder is zero => GCD is the last divisor .
We can summarize an algorithm into a following table.
45267964 | : | 1243564 | = | 36 | remainder ( 499660 ) | ||||||||||||||||
1243564 | : | 499660 | = | 2 | remainder ( 244244 ) | ||||||||||||||||
499660 | : | 244244 | = | 2 | remainder ( 11172 ) | ||||||||||||||||
244244 | : | 11172 | = | 21 | remainder ( 9632 ) | ||||||||||||||||
11172 | : | 9632 | = | 1 | remainder ( 1540 ) | ||||||||||||||||
9632 | : | 1540 | = | 6 | remainder ( 392 ) | ||||||||||||||||
1540 | : | 392 | = | 3 | remainder ( 364 ) | ||||||||||||||||
392 | : | 364 | = | 1 | remainder ( 28 ) | ||||||||||||||||
364 | : | 28 | = | 13 | remainder ( 0 ) | ||||||||||||||||
GCD = 28 |
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.