Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $(x_1,\dots,x_r)$ be a non-zero element of $\mathbb{Z}^r$, and let $h$ be the highest common factor of $x_1, \dots, x_r$. Show that there is an isomorphism $\mathbb{Z}^r \to \mathbb{Z}^r$ taking $(x_1,\dots,x_r)$ to $(1, 0, 0,\dots,0)$ if and only if $h=1$.

One direction isn't too bad; if $\phi$ is such an isomorphism then $$ \phi\big((x_1,\dots,x_r)\big) = (1,0,\dots,0) $$ $$ \phi\big(h(\tfrac{x_1}{h},\dots,\tfrac{x_r}{h})\big) = (1,0,\dots,0) $$ $$ h \phi\big((\tfrac{x_1}{h},\dots,\tfrac{x_r}{h})\big) = (1,0,\dots,0). $$ But then $h|1$, so we must have $h=1$. I really have no idea how to go about proving the other direction... so any help would be appreciated.

share|cite|improve this question
Homomorphisms can only increase the (absolute value of the) gcd, so isomorphisms must preserve it. – Qiaochu Yuan May 29 '11 at 20:19
up vote 3 down vote accepted

Just go through the extended Euclidean algorithm for expressing $h$ as an integer linear combinantion of $x_1,\ldots,x_r$. Try the case $r=2$ and see how $(x_1,x_2)$ is reduced to $(h,0)$.

share|cite|improve this answer
Okay.. treat me a little like an idiot for the moment because I am still not sure what $\phi$ does. So, assuming $\phi$ takes $(x_1,x_2)$ to $(h,0)$, where $h=ax_1+ bx_2$ for some integers $a,b$, what does it do to other elements? It is actually possible to express $\phi$ algebraically, say? – Fahad Sperinck May 30 '11 at 13:17
@Fadah, $\phi(1,0)=(a,-x_2)$, $\phi(0,1)=(b,x_1)$, for instance. Note that the determinant is 1, which means $\phi$ is invertible. – lhf May 30 '11 at 22:03

If there is an isomorphism $h$ mapping $(x_1,\dots,x_n)$ to $(1,0,\dots,0)$, its inverse $h^{-1}$ maps $(1,0,\dots,0)$ to $(x_1,\dots,x_n)$, and the matrix $A$ of $h^{-1}$ with respect to the canonical basis of $\mathbb Z^n$ then has $(x_1,\dots,x_n)$ as its first column. Since $A$ must have determinant $1$ or $-1$, the $\gcd$ of each of its columns is $1$.

share|cite|improve this answer

Let $H$ be the cyclic subgroup of $\mathbb{Z}^r$ generated by $(x_1,\ldots,x_r)$. If $h=1$, then $t(y_1,\ldots,y_r) = (x_1,\ldots,x_r)$ implies $t = \pm{1}$, and so $\mathbb{Z}^r/H$ is torsion-free and hence free abelian. So $H$ has a complement in $\mathbb{Z}^r$, which must be isomorphic to $\mathbb{Z}^{r-1}$, and the result follows easily.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.