Question

Find Greatest Common Divisor of 73556 and 3444, using Euclidean algorithm.

Answer

The GCD of given numbers is 28.

Explanation

Step 1 :
Divide $73556$ by $3444$ and get the remainder

73556 : 3444 = 21 ( remainder is 1232)

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

Step 2 :
Divide $3444$ by $1232$ and get the remainder

3444 : 1232 = 2 ( remainder is 980)

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

Step 3 :
Divide $1232$ by $980$ and get the remainder

1232 : 980 = 1 ( remainder is 252)

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

Step 4 :
Divide $980$ by $252$ and get the remainder

980 : 252 = 3 ( remainder is 224)

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

Step 5 :
Divide $252$ by $224$ and get the remainder

252 : 224 = 1 ( remainder is 28)

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

Step 6 :
Divide $224$ by $28$ and get the remainder

224 : 28 = 8 ( remainder is 0)

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

We can summarize an algorithm into a following table.

This solution can be visualized using a Venn diagram.

0,0

73556

3444

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

This page was created using

GCD Calculator