I am trying to prove the following theorem on finitely generated free abelian groups (which thus for simplicity may be assumed to be $\Bbb Z^n$):
Let $\alpha \in \Bbb Z^n$ be such that for all $k > 1$, $\alpha \notin k \Bbb Z^n$.
Then there exists a basis for $\Bbb Z^n$ containing $\alpha$.
It is easy to see that for $\alpha = (\alpha_1, \ldots, \alpha_n)$ to satisfy the premises, it is necessary and sufficient that $\gcd(\alpha_1, \ldots, \alpha_n) = 1$, since $k \Bbb Z^n = (k \Bbb Z)^n$.
It is also easy to solve the problem if for some $i$, $\alpha_i = 1$.
In general, I have tried to write up some matrix equations (the problem is equivalent to the existence of a matrix $M \in \mathrm{GL}(n, \Bbb Z)$ with first column $\alpha$) but I haven't been able to work it out; there may be an inductive argument possible but if so, I failed to find it.
Your help is much appreciated.