The GCD of given numbers is 8.
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 still positive (), so we will continue with division.
Step 10 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 11 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 12 :
Divide by and get the remainder
The remainder is still positive (), so we will continue with division.
Step 13 :
Divide by and get the remainder
The remainder is zero => GCD is the last divisor .
We can summarize an algorithm into a following table.
242040 | : | 85672 | = | 2 | remainder ( 70696 ) | ||||||||||||||||||||||||
85672 | : | 70696 | = | 1 | remainder ( 14976 ) | ||||||||||||||||||||||||
70696 | : | 14976 | = | 4 | remainder ( 10792 ) | ||||||||||||||||||||||||
14976 | : | 10792 | = | 1 | remainder ( 4184 ) | ||||||||||||||||||||||||
10792 | : | 4184 | = | 2 | remainder ( 2424 ) | ||||||||||||||||||||||||
4184 | : | 2424 | = | 1 | remainder ( 1760 ) | ||||||||||||||||||||||||
2424 | : | 1760 | = | 1 | remainder ( 664 ) | ||||||||||||||||||||||||
1760 | : | 664 | = | 2 | remainder ( 432 ) | ||||||||||||||||||||||||
664 | : | 432 | = | 1 | remainder ( 232 ) | ||||||||||||||||||||||||
432 | : | 232 | = | 1 | remainder ( 200 ) | ||||||||||||||||||||||||
232 | : | 200 | = | 1 | remainder ( 32 ) | ||||||||||||||||||||||||
200 | : | 32 | = | 6 | remainder ( 8 ) | ||||||||||||||||||||||||
32 | : | 8 | = | 4 | remainder ( 0 ) | ||||||||||||||||||||||||
GCD = 8 |
This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.