I often like to use to use the theorem that $(n,k)=1$ if and only if there are integers $x,y$ such that $nx+ky=1$. But then $(n+k)x + k(y-x)=1$, so $(n+k,k)=1$.
On the other hand, if $(n+k,k)=1$, find $x,y$ so that $(n+k)x + ky = 1$, then $nx + k(x+y)=1$, so $(n,k)=1$.
More generally, if $ad-bc=1$, then $(m,n)=1$ if and only if $(am+bn,cm+dn)=1$.
This is because the matrix $A=\left[\begin{matrix} a & b \\c & d\end{matrix}\right]$ has inverse $A^{-1}=\left[\begin{matrix} d & -b \\-c & a\end{matrix}\right]$
But it's obvious that if \left[\begin{matrix} m'\\ n'\end{matrix}\right]=A\left[\begin{matrix} m \\ n\end{matrix}\right] where $A$ is any $2\times 2$ integer matrix, then any common divisor of $m$ and $n$ is necessarily a common divisor of m' and n'. When $ad-bc=1$, $A^{-1}$ is also an integer matrix, so we get that A^{-1}\left[\begin{matrix} m'\\ n'\end{matrix}\right]=\left[\begin{matrix} m \\ n\end{matrix}\right] and therefore any common divisor of m' and n' is a common divisor of $m$ and $n$.
The problem at hand is the special case: $A=\left[\begin{matrix} 1 & 0 \\1 & 1\end{matrix}\right]$
Even more generally, if $x_1,...,x_n$ are integers and $A$ is an $n\times n$ integer matrix with $\det(A)=\pm 1$, and $[y_1,...,y_n]^T = A [x_1,...,x_n]^T$, then $\gcd(y_1,...,y_n)=\gcd(x_1,...,x_n)$.
A particularly lovely way of looking at this is that, if $x=(x_1,...,x_n)$ then $\gcd(x)=\gcd(x_1,..,x_n)$ is equal to the number of integer lattice points on the line segment between $0=(0,...,0)$ and $x$, excluding $0$ but including $x$ (if $x\neq 0$.)
But any integer matrix, $A$, takes lines through zero to lines through zero, and integer lattice points to integer lattice points. If $A$ is $1-1$, then the number of lattice points between $0$ and $Ax$ will thus always be at least as many as the number of lattice points between $0$ and $x$. Thus, $\gcd(Ax)\geq \gcd(x)$. If $A^{-1}$ is also an integer matrix, then $\gcd(x)=\gcd(A^{-1}Ax)\geq \gcd(Ax)$. So $\gcd(Ax)=\gcd(x)$.
This lets us generalize to $m\times n$ matrices $A$ as long as there exists an $n\times m$ matrix $B$ such that $BA=I_n$. Then $A$ is $1-1$ and $B$ is $1-1$ on the image of $A$, so the same argument applies: $\gcd(Ax)\geq \gcd(x)$ and $\gcd(x)=\gcd(BAx)\geq \gcd(Ax)$.