Use the Euclidean Algorithm to find the greatest common divisor of 875 and 4075. 

Question 1

Use the Euclidean Algorithm to find the greatest common divisor of 875 and 4075.

Theorem 3. The Euclidean Algorithm. If and are positive integers, , and

$latex a = bq + r,\quad 0 \le r < b$

$latex b = rq_1 + r_1,\quad 0 \le r_1 < r$

$latex r = r_1q_2 + r_2,\quad 0 \le r_2 < r_1$

$latex r_k = r_{k+1}q_{k+2} + r_{k+2},\quad 0 \le r_{k+2} < r_{k+1}$

then for large , say , we have and .

Let , .

By the Euclidean Algorithm, the last nonzero remainder is .