Question

Find Greatest Common Divisor of 7469 and 4369, using Euclidean algorithm.

Answer

The GCD of given numbers is 1.

Explanation

Step 1 :
Divide $7469$ by $4369$ and get the remainder

7469 : 4369 = 1 ( remainder is 3100)

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

Step 2 :
Divide $4369$ by $3100$ and get the remainder

4369 : 3100 = 1 ( remainder is 1269)

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

Step 3 :
Divide $3100$ by $1269$ and get the remainder

3100 : 1269 = 2 ( remainder is 562)

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

Step 4 :
Divide $1269$ by $562$ and get the remainder

1269 : 562 = 2 ( remainder is 145)

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

Step 5 :
Divide $562$ by $145$ and get the remainder

562 : 145 = 3 ( remainder is 127)

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

Step 6 :
Divide $145$ by $127$ and get the remainder

145 : 127 = 1 ( remainder is 18)

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

Step 7 :
Divide $127$ by $18$ and get the remainder

127 : 18 = 7 ( remainder is 1)

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

Step 8 :
Divide $18$ by $1$ and get the remainder

18 : 1 = 18 ( remainder is 0)

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

We can summarize an algorithm into a following table.

This solution can be visualized using a Venn diagram.

0,0

7469

4369

257

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

This page was created using

GCD Calculator