# $(\mathbb{Z} \times \mathbb{Z}) / \langle (a, b ) \rangle$ is isomorphic to $\mathbb{Z} \times \mathbb{Z} _d$, where $d = \gcd(a,b)$

$\frac{\mathbb{Z} \times \mathbb{Z}}{\langle (a, b ) \rangle}$ is isomorphic to $\mathbb{Z} \times \mathbb{Z} _d$, where $d = \gcd(a,b)$.

Here, $\langle (a, b ) \rangle$ is a group generated by $( a, b) \in \mathbb{Z} \times \mathbb{Z}$ .

I tried to use the First isomorphism theorem, putting a homomorphism map $\phi : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z} \times \mathbb{Z}_d$ by $(x, y) \mapsto (bx-ay, xy)$.

Then ker $\phi = \langle (a, b ) \rangle$ and so $\frac{\mathbb{Z} \times \mathbb{Z}}{\langle(a,b)\rangle}$ is isomorphic to Im $\phi = \mathbb{Z} \times \mathbb{Z} _d$

Is my approach right? I'm not sure. Thanks!

• Well isn't this just the fact that $\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}_n$? Then treat the first component as the identity. – fretty Jun 13 '13 at 21:59
• @fretty In the case, doesn't the first component of Im $\phi$ become the identity? maybe I don't fully understand your comment... – user73309 Jun 13 '13 at 22:04
• How do you define $\mathbb{Z}_d$ if $d = (a, b)$? – Ink Jun 13 '13 at 22:06
• I think you guys are confused -- he's asking about the quotient of $\mathbb{Z} \times \mathbb{Z}$ by the cyclic subgroup generated by the element $(a, b)$. – Daniel McLaury Jun 13 '13 at 22:07
• @fretty, you're misreading the question because he's using the same notation for two different things. The first $(a, b)$ is a point of $\mathbb{Z} \times \mathbb{Z}$. Only the second $(a, b)$ is the gcd. – Daniel McLaury Jun 13 '13 at 22:08

You are on the right track with respect to the method, but your proposed homomorphism is none. By the extended Euklidean algorithm, there are integers $u,v\in\mathbb Z$ such that $ua+vb=d$. The homomorphism \begin{align}\phi\colon\mathbb Z\times\mathbb Z&\to\mathbb Z\times (\mathbb Z/d\mathbb Z)\\(x,y)&\mapsto(\frac bdx-\frac ady,ux+vy+d\mathbb Z)\end{align} is onto because $\phi(v,-u)=(1,0+d\mathbb Z)$ and $\phi(\frac ad,\frac bd)=(0,1+d\mathbb Z)$. Note that $\phi(x,y)=(0,0+d\mathbb Z)$ implies $(x,y)=c\cdot(a,b)$ with $c\in\mathbb Q$ from the first component, i.e. $(x,y)=c'\cdot (\frac ad,\frac bd)$ with $c'\in\mathbb Z$; but then the second component is $c'+d\mathbb Z$ (because $u\frac ad+v\frac bd=1$), so that $\ker\phi\subseteq \langle(a,b)\rangle$. From $\phi(a,b)=0$ we finally obtain $\ker \phi=\langle(a,b)\rangle$ and that $\phi$ induces an isomorphism $$(\mathbb Z\times \mathbb Z)/\langle (a,b)\rangle\cong \mathbb Z\times (\mathbb Z/d\mathbb Z).$$

• Why not call $a'=a/d$ and $b'=b/d$ to ease notation? – Álvaro Lozano-Robledo Jun 23 '13 at 12:37

I'd recommend just drawing the picture. Start out with a grid of dots representing $\mathbb{Z} \times \mathbb{Z}$. Then highlight the (one-dimensional) sub-grid corresponding to the subgroup $\langle (a, b)\rangle$ for some small values of $a$ and $b$; these are the points that get identified with $(0, 0)$ when you form the quotient. In a different color, highlight all the points that get identified with $(1, 0)$ -- which is the previous thing shifted one unit to the right -- and so forth, until you see the pattern.

As for your suggested strategy: is that a homomorphism?

• I have tired drawing a picture. However in the case of 'infinite' set, it is not easy to find a proper homo map. – user73309 Jun 13 '13 at 22:10
• I was wrong! definitely it is not homo. the second term does not work. – user73309 Jun 13 '13 at 22:12
• What does the set of representatives for $(\mathbb{Z} \times \mathbb{Z}) / \langle(a, b)\rangle$ look like in your picture? – Daniel McLaury Jun 13 '13 at 22:12
• (You get the right homomorphism by looking at the geometry of that picture.) – Daniel McLaury Jun 13 '13 at 22:14
• Does $(x, y) \mapsto (x - a\lceil {x \over a} \rceil, y - b\lceil {y \over b}\rceil)$ work? – user73309 Jun 16 '13 at 14:38

This is a bit of an unusual approach, and possibly not suitable for beginner group theorists, but I'll go ahead and present it anyway in case someone finds it interesting:

You can consider elements of $\mathbb{Z}\times\mathbb{Z}$ as two-dimensional vectors, and apply matrix transformations just as you'd do in linear algebra. Transformations by matrices give group homomorphisms (a linear map is just a special kind of homomorphism, after all), and moreover, using matrices of determinant 1 give rise to isomorphisms (as you can show by explicitly calculating the inverse). My strategy here is to come up with a neat isomorphism from $\mathbb Z^2$ to itself that maps $(a,b)$ to $(0,d)$, so that the question becomes simple.

I know from number theory that the GCD of two integers can be written as a linear combination of them, so I'll go ahead and do that: $d = xa + yb$ for some $x$ and $y$. So I'm imagining the second row of my isomorphism matrix will probably be $(x\ \ y)$, so that $(a,b)$ maps to something with second component $d$. I want the first component to be 0, so I want some zero linear combination of $a$ and $b$. Well, the most obvious is $b$ lots of $a$ and $-a$ lots of $b$. So here's the candidate matrix: $\begin{pmatrix} b & -a \\ x & y \end{pmatrix}$

Not bad – it induces a homomorphism that maps $(a,b)$ to $(0,d)$ just like we wanted. Problem, though: it's not an isomorphism! Calculate the determinant and you get $yb + xa = d$, where we wanted 1. Hmm... multiplying a row or column by $1/d$ would sort that out, but of course we need integer entries, so we can't just put that anywhere we like. But let's not forget $d$ is the GCD of $a$ and $b$, so certainly $d$ divides both of them – or in other words, both $b/d$ and $-a/d$ are integers! And indeed, the below matrix is an isomorphism: $\begin{pmatrix} b/d & -a/d \\ x & y \end{pmatrix}$

That lets you go from $\mathbb Z^2/\langle (a,b) \rangle$ to $\mathbb Z^2/\langle (0,d) \rangle$. And it's pretty clear (e.g. by the first isomorphism theorem, but this time with a much simpler $\phi$) that the latter is just $\mathbb Z \times \mathbb Z_d$.

Footnote: it's actually not so hard to see that every homomorphism from $\mathbb Z^2$ to itself can be represented as a matrix, so if you already have intuition about when maps can and cannot be linear transformations, you may be able to bring that over to this case. For example, your proposed homomorphism multiplies together two input terms, which is not a very linear thing to do!

Let $(a,b)\in \mathbb{Z}\times \mathbb{Z}$, with $\gcd(a,b)=d$, so that $(a,b)=d(a',b')$ for some other integers $a',b'$, with $\gcd(a',b')=1$. Then, there are integers $e$ and $f$, such that $a'f-b'e=1$. Thus, $(a',b')$ and $(e,f)$ form a basis of $\mathbb{Z}\times \mathbb{Z}$ while $\Lambda = \langle (a,b), (e,f) \rangle$ forms a sublattice (subgroup) of $\mathbb{Z}\times\mathbb{Z}$ with index $d$.

In particular, \begin{align*} \mathbb{Z}\times \mathbb{Z}/\langle (a,b) \rangle & \cong \mathbb{Z}\times \mathbb{Z}/\langle d(a',b') \rangle \\ &\cong \langle (a',b')\rangle \times \langle (e,f) \rangle/\langle d(a',b') \rangle \\ &\cong \left(\langle (a',b')\rangle /\langle d(a',b') \rangle \right) \times \langle (e,f) \rangle \\ & \cong \mathbb{Z}/d\mathbb{Z} \times \langle (e,f)\rangle \\ & \cong \mathbb{Z}/d\mathbb{Z}\times \mathbb{Z}. \end{align*}

• There's no real need to take the departure via $a',b'$. The extended Euklidean algorithm privides us with $e.f\in\mathbb Z$ such that $ae-bf=\gcd(a,b)$ immediately. – Hagen von Eitzen Jun 23 '13 at 10:29
• I wanted to specify $a'$ and $b'$ so that $(a',b')$ and $(e,f)$ form a basis of $\mathbb{Z}\times \mathbb{Z}$. – Álvaro Lozano-Robledo Jun 23 '13 at 12:37

It is easy using the classification of finitely generated abelian groups.

For $(a,b)=0$ the claim is trivial, so let's assume $(a,b) \neq 0$. The rank of the quotient is $2-1=1$, therefore the free part is $\cong \mathbb{Z}$. The torsion subgroup contains the class of $(a/d,b/d)$ (since the class of $d(a/d,b/d) = (a,b)$ vanishes). It is not hard to show that its order is $d$ and that it generates the torsion subgroup. Hence, the quotient is $\mathbb{Z} \oplus \mathbb{Z}/d$.

You are missing a few things from your proof:

$\phi$ should be a surjective (onto) map to $\mathbb Z \times \mathbb Z_d$. In fact, this is not the case because $bx - ay$ will only yield members of $d \mathbb Z$ (which is in turn isomorphic to $\mathbb Z$, but the point is still that you need another step).

• More importantly, the map he has above isn't a homomorphism. – Daniel McLaury Jun 13 '13 at 22:58
• Also, $(a, 0)$ isn't an element of $\langle(a, b)\rangle$. – Daniel McLaury Jun 13 '13 at 22:59
• @DanielMcLaury good catch. – Omnomnomnom Jun 13 '13 at 23:03