Bases for $\Bbb Z^n$ containing a given vector 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.
 A: This is well-known and there are several proofs. Here is a proof using the classification of finitely generated abelian groups:
Consider $A:=\mathbb{Z}^n / \langle \alpha \rangle$. Since the rank of $\langle \alpha \rangle$ is $1$, the rank of $A$ is $n-1$. One computes that the torsion subgroup of $A$ is trivial. This implies $A \cong \mathbb{Z}^{n-1}$, i.e. we have an exact sequence $0 \to \langle \alpha \rangle \to \mathbb{Z}^n \to \mathbb{Z}^{n-1} \to 0$. Since $\mathbb{Z}^{n-1}$ is free, the sequence splits and we are done.
A: The result is due to Hermite, circa 1850.  A more traditional proof appears in $\S 1.3.3$ of these notes on Geometry of Numbers.
I have to say though that I like Martin Brandenburg's proof much better and have already incorporated it into other notes of mine.  Notice also that the result holds not just with $\mathbb{Z}$ replaced by any PID (as in the linked notes above) but in fact with $\mathbb{Z}$ replaced by any Bezout domain: an integral domain in which every finitely generated ideal is principal.  To carry over Martin's proof one needs only to know that a finitely generated torsionfree module over a Bezout domain is free; for this, see $\S$ 3.9.2 of my commutative algebra notes.
Finally, this condition is related to -- but not exactly the same as -- several conditions on rings which have been studied by Kaplansky and others.  Indeed there is such a thing as a Hermite ring.  (In fact, unfortunately there are at least three different classes of rings which go by that name, and the relations among them are subtle.  I have always found this a bit confusing.)
Added: Probably more helpful than muttering about Hermite rings is to refer to Corollary 3.2 of this (very nice, as always) note of Keith Conrad.  The condition on a commutative ring $R$ that $\operatorname{GL}_n(R)$ acts transitively on elements $x \in R^n$ whose coordinates generate the unit ideal is equivalent to: all finitely generated stably free $R$-modules are free.  Thus for instance the result holds for polynomial rings in any finite number of indeterminates over a PID by Quillen-Suslin, and it does not hold in any Dedekind domain which is not a PID.
