Let \((a,b)=d\) and let \((a+kb,b)=e\).
If \(d\) divides \(a\) and \(b\), then it divides any linear combination of \(a\) and \(b\), including \(a+kb\).
$$ d|a, d|b \implies d|(a+kb) $$
If \(e\) divides \(a+kb\), then:
$$\begin{gather} \frac{a+kb}{e} = \text{some integer} \\ \frac{a}{e} + k\frac{b}{e} = \text{some integer} \end{gather}$$
Since \(e|b\):
$$\begin{gather} \frac{a}{e} + \text{some integer} = \text{some integer} \end{gather}$$
This shows that \(a/e\) is an integer, or that \(e|a\).
We have shown that \((a,b)\) divides \((a+kb,b)\), and that \((a+kb,b)\) divides \((a,b)\). If \((a,b)|(a+kb,b)\) and \((a+kb,b)|(a,b)\), then \((a,b) = (a+kb,b)\).