"Term Rewriting and All That" - Exercise 3.10
If we can find $(z_1, z_2)$ such that $a z_1 + b z_2 = 1$ then we can take $(k z_1, k z_2)$ to obtain an arbitrary number $k (a z_1 + b z_2) = k \in \mathbb{Z}$ and then it is proved that $g_{(a, b)}$ is onto. However, every linear combination of two numbers $(a, b)$ is a multiple of their $gcd$. So, $g_{(a, b)}$ is onto if and only if $gcd(a, b) = 1$.