Question
Find Greatest Common Divisor of 1160718174 and 316258250, using repeated division.
Answer
The GCD of given numbers is 1078.
Explanation
Step 1 : Place the numbers inside division bar:.
| 1160718174 | 316258250 |
Step 2 : Divide numbers by 2.
| 2 | 1160718174 | 316258250 |
| 580359087 | 158129125 |
Step 3 : Divide numbers by 7.
| 2 | 1160718174 | 316258250 |
| 7 | 580359087 | 158129125 |
| 82908441 | 22589875 |
Step 4 : Divide numbers by 7.
| 2 | 1160718174 | 316258250 |
| 7 | 580359087 | 158129125 |
| 7 | 82908441 | 22589875 |
| 11844063 | 3227125 |
Step 5 : Divide numbers by 11.
| 2 | 1160718174 | 316258250 |
| 7 | 580359087 | 158129125 |
| 7 | 82908441 | 22589875 |
| 11 | 11844063 | 3227125 |
| 1076733 | 293375 |
Step 6 : Number 1076733 and 293375, cannot be divided any more. The GCD is:
$$ GCD = 2\cdot7\cdot7\cdot11 = 1078 $$This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.
This page was created using
GCD Calculator