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 $a$ and $b$ are positive integers, $b \ne 0$ , 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$

$\cdots$

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

then for large $k$ , say $k=t$ , we have $r_{t-1}=r_tq_{t+1}$ and $(a,b)=r_t$ .

Let $a=4075$ , $b=875$ .

$4075=4(875)+575$

$875=1(575)+300$

$575=1(300)+275$

$300=1(275)+25$

$300=25(12)+0$

By the Euclidean Algorithm, the last nonzero remainder is $25$ .

$\gcd(875,4075)=25$