Question

Use the Euclidean algorithm to determine the greatest common divisor of 2288 and 4875

Answer 1

13

Explanation:

We have to find greatest common divisor of two number 2288 and 4875.

Now, greatest common divisor of two number is defined as the highest common factor that divides both the number.

We can use the Euclidean algorithm to do so.

Since 4875 is the larger of the two number

4875 ÷ 2288: Quotient = 2, Remainder = 299

2288 ÷ 299: Quotient = 7, Remainder = 195

299 ÷ 195: Quotient = 1, Remainder = 104

195 ÷ 104: Quotient = 1, Remainder = 91

104 ÷ 91: Quotient = 1, Remainder = 13

91 ÷ 13: Quotient =7, Remainder = 0

Hence, we stop here and the greatest common divisor = 13