Easy# What is $\gcd(143, 39)$?

NUMTH-E91RNP

The Euclidean Algorithm is a way to find the greatest common divisor of two nonzero integers by repetitive usage of the division algorithm. Let $x, y \in \mathbb{Z} \backslash \{ 0 \}$. Then, we get the following sequence of quotients and remainders:

$$\begin{align*} x &= q_0 y + r_0\\\ y &= q_1 r_0 + r_1 \\\ r_0 &= r_1 q_2 + r_2\\\ &\vdots\\\ r_{m - 2} &= q_m r_{m - 1} + r_m\\\ r_{m - 1} &= q_{m + 1} r_{m}\end{align*}$$

...where $r_m$ is the final nonzero remainder. Then, $\gcd(x, y) = r_m$.

What is $\gcd(143, 39)$? Determine the correct answer by utilizing the Euclidean Algorithm.