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

I am struggling with the following question.

Suppose I have a group $H$ which is a subgroup of $\mathbb{Z}\oplus\mathbb{Z}$, such that any element $\begin{bmatrix} a \\[0.3em] b \end{bmatrix}$ is defined as: if $b=0$, then $a=0$. How can I prove that $H$ has a basis with exactly one element?

share|cite|improve this question
A clearer way to state this problem would be to say that $H$ is a subgroup of ${\mathbb Z} \oplus {\mathbb Z}$ having zero intersection with the first direct factor. – Derek Holt May 1 '12 at 12:23
What is exactly the meaning of a one element basis? I am under the impression that it is a set with only one element in it; like (x). But the answers here suggest that one element basis is of the type (x,y). I am a bit confused with this. – CasterT May 9 '12 at 15:23
This is because elements of $\mathbb{Z}\oplus \mathbb{Z}$ are pairs $(x,y)$ with $x,y\in \mathbb{Z}$. – Tara B May 9 '12 at 16:03
@CasterT: The comment above is addressed to you. – Tara B May 9 '12 at 22:09

I understand what you mean. Here's my suggestion: take the element of the subgroup whose first coordinate has the smallest positive value: $(a,b)\in H$ such that $a>0$ and $a \leq a'$ for all $(a',b')\in H$ such that $a' > 0$. This exists because $\mathbb{Z}_+$ is well ordered.

Claim: $(a,b)$ is your generator.

You have to show that, for all $(a',b')\in H$, there exists $n\in \mathbb{Z}$ such that $(a',b') = n(a,b)$. Proceed by contradiction. Your assumption on $H$ and the choice of $a$ imply that $b\neq 0$ too. (It could be negative.) A little arithmetic should yield the contradiction.

Note: I haven't written out the argument, but this is how all such problems proceed.

share|cite|improve this answer

I think Tara somewhat gave the answer. If I understand you correctly you have some given subgroup $H$ with the property that if $(a,0)\in H$ then $a=0$. This is slightly different from what you wrote.

You use closure under addition and Bézout's identity for your proof. Assume we have two generators $(a,b)$ and $(c,d)$. Then $d(a,b)-b(c,d)$ must be in $H$ (the product is here understood as the d-fold resp. b-fold sum). But this is just $(da-bc,0)$, thus $da=bc$. Now you have Bézout's identity, i.e. there exist $x,y$ such that $xb+yd=gcd(b,d)=:g$. Write $b=gb'$ and $d=gd'$, then we have $b'(xa+yc,g)=(a,b)$ and $d'(xa+yc,g)=(c,d)$ by the equality $d'a=b'c$. Hence $H$ is generated by one element.

share|cite|improve this answer

This is more or less just another version of the answers already given, but I don't use Bézout's identity or contradiction.

Let $H$ be a subgroup of $\mathbb{Z}\oplus \mathbb{Z}$ such that for any $(a,b)\in H$, if $b=0$ then $a=0$. Another way of saying this is that $(a,0)\in H$ implies $a=0$. So what we are really saying is that the intersection of $H$ with the first direct factor is trivial, as Derek said.

Now suppose $(a_1,b), (a_2,b)\in H$. Since $H$ is a group under addition, $(a_1,b) - (a_2,b) = (a_1 - a_2, 0)\in H$ and hence $a_1 = a_2$. So for each $b\in \mathbb{Z}$, there is at most one $a\in \mathbb{Z}$ such that $(a,b)\in H$.

Now let $b$ be the minimum positive integer such that $(a,b)\in H$ for some $a\in \mathbb{Z}$. Suppose $(a',b')\in H$, and write $b' = bq + r$ with $q\in \mathbb{Z}$, $0\leq r<b$. Then $(a',b') - q(a,b) = (a'-qa, r)\in H$, so $r=0$ by the minimality of $b$. But then since $q(a,b) = (qa,b')\in H$, we must have $a' = qa$ by the uniqueness of $a'$. Hence $(a',b') = q(a,b)$, so every element of $H$ is a multiple of $(a,b)$ and hence $(a,b)$ generates $H$.

share|cite|improve this answer

If you mean that $H$ is a subgroup of $\mathbb{Z}\oplus\mathbb{Z}$ where each $h=\left[\matrix{a\\b}\right]\in H$ satisfies the condition $b=0\implies a=0$, then you have a tractable problem.

In this case, a hint is to consider the smallest positive value that $a$ can have over all such $h$ above.

You could define $\alpha=\inf_{h\in H}|\pi_1(h)|$ where $\pi_1:H\to\mathbb{Z}$ is the "projection" homomorphism $h\mapsto a$ taking each $h$ to its first ordinate. Or, if this seems to abstract, start by observing that the set $A=\{a~|~h\in H\}$ is itself a subgroup of $\mathbb{Z}$, then let $A^+=\{a\in A~|~a > 0\}$ and $\alpha=\inf A^+$.

Then, let $g=\left[\matrix{\alpha\\\beta}\right]$ be a (the) element of $H$ having this minimal positive first ordinate. You will be able to show that $g$ is in fact unique and that it generates $H$, i.e. each $h=ng$ for some $n\in\mathbb{Z}$.

Intuitively, you can visualize this as a (parallelogramic) lattice in $\mathbb{Z}^2$, or as an additive subgroup (in fact, an ideal) $I=\left<\alpha+i\beta\right>$ in the ring of Gaussian integers.

To make the formal proof, you could use Bézout's identity as Simon Markett does. Or, you can notice that the minimality condition defining $\alpha$ is in fact an equivalent way of defining the greatest common divisor. Then, notice that $\pm\alpha$ are the unique generators of $H_1=\pi_1(\mathbb{Z})$ which is a cyclic subgroup of the first $\mathbb{Z}$ in $\mathbb{Z}\oplus\mathbb{Z}$, for if some $h$ had $a\not\equiv0\pmod\alpha$, then replacing $a$ with its remainder $r$ would produce an element of $H$ with smaller first ordinate, condtradicting the minimality of $\alpha$.

Lastly, we need to show that $\beta$ as defined above (which may be negative) generates $H_2=\pi_2(H)$, i.e. has minimal absolute value over all second ordinates $b$ of $h\in H$. However we already know that $H_2$ is a cyclic subgroup of $\mathbb{Z}$, and if its generator $\beta'$ were smaller in absolute value than $\beta$, then we would have $\beta'|\beta\implies\beta=n\beta'$ and hence $g=ng'$ for some $g'=\left[\matrix{\alpha'\\\beta'}\right]\in H$ with second ordinate $\beta'$ and some $n\ne0,~\pm1$. But then we would have $\alpha=n\alpha'=|n\alpha'|>|\alpha'|$, contradicting the minimality of $\alpha$.

The key insight in this last step is that the minimality (in absolute value) of $\alpha$ and $\beta$ are linked, or coupled. Thus, we could started by defining $\beta$ as well from a minimality condition, analogously to $\alpha$, and then proving that one of $\left[\matrix{\alpha\\\pm\beta}\right]$ generates $H$.

share|cite|improve this answer
you beat me to the punch! – Jerry Gagelman May 1 '12 at 12:28
@JerryGagelman: actually, I think yours is correct and mine not. I was too hasty! – bgins May 1 '12 at 12:31

I have one more question from Tara B. In your answer you have mentioned "Since H is a group under addition, $(a_1,b)−(a_2,b)=(a_1−a_2,0) \in H$". Isn't it for a group under subtraction we can write the above? I am still in the process of learning these, so I have a lot of questions.

share|cite|improve this answer
No. Subtraction is not associative, so you can't have a 'group under subtraction'. If $G$ is a group under addition, then for any $x,y\in G$, we have $-y\in G$, since $-y$ is the inverse of $y$, and so $x + (-y)\in G$. We can write $x-y$ as shorthand for $x + (-y)$. – Tara B May 10 '12 at 19:04
By the way, it's quite unconventional to write a question as an 'answer' to another question, but I realise that you may not have many options open to you as a new user, so I guess it's okay. – Tara B May 10 '12 at 19:05

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.