$\gcd(8,16)$ with Euclidean algorithm

Question

Using the Euclidean algorithm, where the last nonzero remainder is the gcd, I proceed directly to this result

$16=2\cdot 8+0$

which doesn't have a last nonzero remainder! But clearly $\gcd(8,16)=8$. Why did $8$ not show up in my standard Euclidean procedure above?

Answer 1

I think you have misunderstood the final step of the Euclidean algorithm. Once you reach $0$, it is the smallest of the two other numbers in the final step that is the $\gcd$. And in this case, the two other numbers are $8$ and $16$.

You always reach $0$ at some point. That is how you know you are finished. Once you have reached $0$ you need to take a step back to find the $\gcd$.

I like to apply the Euclidean algorithm the following way: $$ \gcd(16,8)=\gcd(16-2\cdot 8,8)\\ =\gcd(0,8) $$ together with the general assumption that $\gcd(0,n)=n$. This way, it's easier to immediately spot which number is actually the $\gcd$, without having to analyze the terms of the final line.