Question

Find Greatest Common Divisor of 7684 and 4148, using Euclidean algorithm.

Answer

The GCD of given numbers is 68.

Explanation

Step 1 :
Divide $7684$ by $4148$ and get the remainder

7684 : 4148 = 1 ( remainder is 3536)

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

Step 2 :
Divide $4148$ by $3536$ and get the remainder

4148 : 3536 = 1 ( remainder is 612)

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

Step 3 :
Divide $3536$ by $612$ and get the remainder

3536 : 612 = 5 ( remainder is 476)

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

Step 4 :
Divide $612$ by $476$ and get the remainder

612 : 476 = 1 ( remainder is 136)

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

Step 5 :
Divide $476$ by $136$ and get the remainder

476 : 136 = 3 ( remainder is 68)

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

Step 6 :
Divide $136$ by $68$ and get the remainder

136 : 68 = 2 ( remainder is 0)

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

We can summarize an algorithm into a following table.

This solution can be visualized using a Venn diagram.

0,0

7684

4148

113

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

This page was created using

GCD Calculator