Prove with Euclid's Algortihm

Question

I have this problem and I'm not 100% how to complete it. Here's the question:

Let $m$ and $k$ be positive integers with $m > 1, k > 1$. Show that $\gcd(m, mk - 1)=1$. (Hint: use Euclid's algorithm.)

I get the hint, so I set it up like this: $$mk-1=m+1$$However, I'm not sure where to go from here. Thanks.

Answer 1

Hint: \begin{align*} mk-1&=m\cdot(k-1)+m-1 \\ m&=1\cdot(m-1)+1. \end{align*}