?

Number Theory

Free Version

Upgrade subject to access all content

Easy

What is $\gcd(57870, 11353)$?

NUMTH-92PEJS

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(57870, 11353)$? Determine the correct answer by utilizing the Euclidean Algorithm.

A

$7$

B

$97$

C

$3$

D

$1$