Question

Find Greatest Common Divisor of 7255 and 2000, using Euclidean algorithm.

Answer

The GCD of given numbers is 5.

Explanation

Step 1 :
Divide $7255$ by $2000$ and get the remainder

7255 : 2000 = 3 ( remainder is 1255)

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

Step 2 :
Divide $2000$ by $1255$ and get the remainder

2000 : 1255 = 1 ( remainder is 745)

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

Step 3 :
Divide $1255$ by $745$ and get the remainder

1255 : 745 = 1 ( remainder is 510)

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

Step 4 :
Divide $745$ by $510$ and get the remainder

745 : 510 = 1 ( remainder is 235)

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

Step 5 :
Divide $510$ by $235$ and get the remainder

510 : 235 = 2 ( remainder is 40)

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

Step 6 :
Divide $235$ by $40$ and get the remainder

235 : 40 = 5 ( remainder is 35)

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

Step 7 :
Divide $40$ by $35$ and get the remainder

40 : 35 = 1 ( remainder is 5)

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

Step 8 :
Divide $35$ by $5$ and get the remainder

35 : 5 = 7 ( remainder is 0)

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

We can summarize an algorithm into a following table.

This solution can be visualized using a Venn diagram.

0,0

7255

2000

1451

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

This page was created using

GCD Calculator