Determining $\gcd(94, 27)$

Question

I want to determine $\gcd(94, 27)$. Using the Euclidean algorithm, I got \begin{align} 94 &= 27 (3) + 13 \\ \implies 27 &= 13 (2) + 1 \\ \implies \;\;2 &= 2 (1) \end{align}

Does this mean the GCD is $2$? Clearly $2$ doesn't divide $27$, so what am I doing wrong?

Answer 1

As mentioned in the comments, the last non-zero remainder is the GCD, not the quotient corresponding to the expression with zero remainder. To highlight, that is the red/boxed number below: \begin{align} 94 &= 27 (3) + 13 \\ 27 &= 13 (2) + \color{red}{\boxed{1}} \\ 13 &= 13 (1) + 0 \end{align}

For another example, consider $\gcd(45, 81)$: \begin{align} 81 &= (1)45 + 36 \\ 45 &= (1)36 + \color{red}{\boxed{9}} \\ 36 &= (4)9 + 0 \end{align}

Answer 2

Using the shorthand notation for gcd: $$(94, 27) = (13,27) = (27,13) = (1, 13) = 1,$$ so $94$ and $27$ are relatively prime. In your work, you incorrectly pulled the $2$ from the second line to work with; you wanted the $13$.