# Finding $\langle a_1, a_2, …, a_n \rangle$ in $\mathbb{Z}_{20}$

I realize a variation of this problem (probably in fact the same textbook problem from Gallian's text p.72 #40) has been asked here and here but my understanding is still a little cloudy.

I am asked to find $$\langle m,n\rangle$$ in $$\mathbb{Z}_{20}$$ as well as $$\langle l,m,n\rangle$$.

As a concrete example, let $$m=6,n=15$$, so we are trying to find $$\langle 6,15\rangle$$ in $$\mathbb{Z}_{20}$$ . My first thought was appealing to the definition: $$\langle h,k\rangle:= \{h^n,k^n|n\in\mathbb{Z}\}$$ where $$h^n,k^n$$ denotes repeated addition. So $$\langle6,15\rangle=\{6n,15n,9n,21n\space|n\in\mathbb{Z}\}$$

But I found in the first linked post that $$\langle a_1, a_2, ..., a_n \rangle = \langle \operatorname{gcd}(a_1, a_2, ..., a_n) \rangle$$ so instead $$\langle 6,15\rangle=\langle3\rangle.$$

Is there a relatively easy proof of the latter fact as well as intuition as to why it's true?

My first thought was appealing to the definition: $$\langle h,k\rangle:= \{h^n,k^n|n\in\mathbb{Z}\}$$

First of all, repeated addition is usually denoted as $$nk$$, not $$k^n$$. I'll refer to it as such from here on.

Second of all, I don't know where you got that definition, but if that's the definition written in a textbook, you should set fire to the textbook. That is most certainly not the definition.

By definition, if $$S\subseteq G$$ where $$G$$ is a group, the group $$\langle S\rangle$$ is defined as

The smallest subgroup $$H$$ of $$G$$ that includes all of $$S$$.

That means that at the very least, the group will include $$\langle h,k\rangle:= \{nh,nk|n\in\mathbb{Z}\},$$

however it, it is a subgroup, therefore it is closed for addition, and must also include $$h+k$$, $$h+2k$$, $$2h+k$$ and so on.

In general, if you have two elements $$h, k\subseteq \mathbb Z$$, then $$\langle h,k\rangle = \langle\gcd(h,k)\rangle$$ is fairly easy to show. You can first show that $$\langle h,k\rangle = \{xh + yk| x,y\in\mathbb Z\}=H$$. This is easy to show because

1. $$H$$ is clearly a subgroup
2. Clearly, any subgroup that includes $$h$$ and $$k$$ must include all of $$H$$.

Then, proving that $$\langle\gcd(h,k)\rangle=H$$ is done in two steps:

$$\subseteq$$:

If $$g\in \langle h,k\rangle$$, then $$g=xh+yk$$ for some $$x,y\in\mathbb Z$$, but this means that, since $$h=h'\cdot \gcd(h,k)$$ and $$k=k'\cdot\gcd(h,k)$$, we have $$g=(xh'+yk')\gcd(h,k)\in\langle\gcd(h,k)\rangle$$

$$\supseteq$$:

For this step, we remember that the equation $$xh+yk=d$$ has a solution if and only if $$d$$ is a multiple of $$\gcd h,y$$. Therefore, taking $$g\in\langle\gcd(h,k)\rangle$$, we know that $$g=n\cdot \gcd(h,k)$$ for some $$n\in\mathbb Z$$. However, since $$\gcd(h,k)$$ divides itself, there also exists some pair $$x,y\in\mathbb Z$$ such that $$xh+yk=\gcd(h,k)$$. Therefore, $$g=n\cdot\gcd(h,k)=n\cdot(xh+yk)=(nx)h+(ny)k\in \langle h,k\rangle$$, and the proof is concluded.

Note, however, that in your question, you are working not with subgroups of $$\mathbb Z$$, but with subgroups of $$\mathbb Z_{20}$$. A lot of the proofs above would still work, but some of them won't.

So, to actually solve your problem, I suggest you think about how you could combine $$n\cdot 6+m\cdot 15$$ to get $$1$$, because if $$1\in\langle h,k\rangle$$, then clearly, $$\langle h,k\rangle$$ is the entire group.

Alternatively, if you want to work more in general, you can try to prove that in $$\mathbb Z_n$$, you have

$$\langle h,k\rangle = \langle\gcd(h,k,n)\rangle$$

• Thank you for the explicit proof! This clears things up. – user573025 Oct 24 '18 at 7:53
• @livingtolearn-learningtolive Happy to help. Like I said, using the proof I gave you, it is very nice practice to prove the final equality in my post. If you truly understand the original proof, it only takes a couple of modifications. – 5xum Oct 24 '18 at 7:56
• I'm trying to work that proof now, however I'm stuck on moving from $g\equiv(xh'+yk')\cdot\gcd(h,k) \pmod{n}$ to $g=(xh'+yk')\cdot\gcd(h,k,n)$ – user573025 Oct 24 '18 at 8:24

In $$\Bbb Z$$, it is true that $$\langle a_1, a_2, \ldots, a_n\rangle = \langle \gcd(a_1, a_2, \ldots, a_n)\rangle$$. This follows from Bezout's identity in the case of $$n = 2$$, and induction for $$n > 2$$.

In $$\Bbb Z_k$$, you actually have $$\langle a_1, a_2, \ldots, a_n\rangle = \langle \gcd(a_1, a_2, \ldots, a_n, k)\rangle$$. For instance, in $$\Bbb Z_{20}$$ we have $$\langle6, 15\rangle = \langle 1\rangle$$. To see this explicitly, note that $$6+15 = 1$$, so $$1\in \langle 6, 15\rangle$$. And clearly $$6, 15\in\langle 1\rangle$$. Since the two subgroups contain eachother's generators, they must be the same.

One way to prove $$\langle a_1, a_2, \ldots, a_n\rangle = \langle \gcd(a_1, a_2, \ldots, a_n, k)\rangle$$ is to use the result from $$\Bbb Z$$, and use the fact that there is a natural bijective correspondence between subgroups of $$\Bbb Z_k$$ and subgroups of $$\Bbb Z$$ which contain $$\langle k\rangle$$.

$$\langle6,15\rangle=\{6n,15n,9n,21n\space|n\in\mathbb{Z}\}$$, this definition is confusing. You can think $$\langle6,15\rangle=\{6m+15n:m,n\in \Bbb Z\}$$.

$$\textbf{Proof:}$$ $$(\Longrightarrow)$$

$$\langle a_1, a_2, ..., a_n \rangle =\{x_1a_1+\cdots+x_na_n: x_1,\cdots, x_n\in Z\}$$. Let $$\operatorname{gcd}(a_1, a_2, ..., a_n)=d$$.

Then $$d\mid a_i$$ for $$1\leq i\leq n$$. So $$d\mid x_1a_1+\cdots +x_na_n$$ i.e., $$\langle a_1, a_2, ..., a_n \rangle\subset \langle d \rangle$$

$$(\Longleftarrow)$$ $$\operatorname{gcd}(a_1, a_2, ..., a_n)=d$$, so we can find $$x_1,\cdots ,x_n\in \Bbb Z$$ such that $$d=x_1a_1+\cdots+x_na_n$$. It means that $$d\in \langle (a_1, a_2, ..., a_n) \rangle\Rightarrow \langle d\rangle \subset (a_1, a_2, ..., a_n)$$

There are two basic steps here.

The first is based on the fact that the map from $$\mathbb Z$$ to $$\mathbb Z_{20}$$ is a homomorphism. Thus any equation in $$\mathbb Z$$ which is based on the group operation (addition) becomes an equation in $$\mathbb Z_{20}$$ under the homomorphism. Since the greatest common divisor may be found by the use of the Euclidean algorithm, which simply involves repeated use of the group operation, the image of the gcd under the homomorphism is a gcd in the image.

The second is that the gcd in $$\mathbb Z$$ generates a subgroup (here $$3\mathbb Z$$, the multiples of $$3$$), and we can look also at the image of the subgroup - any generator of this image subgroup can be regarded as a gcd - the gcd is not properly unique - even in $$\mathbb Z$$ uniqueness is up to sign, because an infinite cyclic group has two generators. Here, because $$3$$ is coprime to $$20$$, $$3$$ is a generator of $$\mathbb Z_{20}$$.

[It is somewhat conventional and sometimes computationally helpful to take the generator of the whole group to be the image of the (positive) generator in $$\mathbb Z$$ - namely $$1$$. This is because the homomorphism is not just a homomorphism of groups, but also of rings, respecting multiplication. $$1$$ remains the identity while $$3$$ is a unit in the image. But from the point of view of pure group theory this is not strictly necessary.]