Question

Find Greatest Common Divisor of 3501 and 400680, using Euclidean algorithm.

Answer

The GCD of given numbers is 9.

Explanation

Step 1 :
Divide $400680$ by $3501$ and get the remainder

400680 : 3501 = 114 ( remainder is 1566)

The remainder is positive ( $1566 > 0$ ), so we will continue with division.

Step 2 :
Divide $3501$ by $1566$ and get the remainder

3501 : 1566 = 2 ( remainder is 369)

The remainder is still positive ( $369 > 0$ ), so we will continue with division.

Step 3 :
Divide $1566$ by $369$ and get the remainder

1566 : 369 = 4 ( remainder is 90)

The remainder is still positive ( $90 > 0$ ), so we will continue with division.

Step 4 :
Divide $369$ by $90$ and get the remainder

369 : 90 = 4 ( remainder is 9)

The remainder is still positive ( $9 > 0$ ), so we will continue with division.

Step 5 :
Divide $90$ by $9$ and get the remainder

90 : 9 = 10 ( remainder is 0)

The remainder is zero => GCD is the last divisor $9$ .

We can summarize an algorithm into a following table.

This solution can be visualized using a Venn diagram.

0,0

3501

400680

389

The GCD equals the product of the numbers at the intersection.

This page was created using

GCD Calculator