Find all generators for the cyclic group $\mathbb{Z}_9 \times \mathbb{Z}_{10}$.

Question

As usual, this is probably a lot easier than I'm making it out to be. I just don't know... where to start. I know that if I have one generator, $g$, of a cyclic group of order $m$, then all the other generators are $g^k$, where $(k,n)=1$.

Is the order of $\mathbb{Z}_9 \times \mathbb{Z}_{10}$... 90? Does $(1,1)$ generate the group?

Am I stumbling in the right direction here?

Answer 1

OK, let's just check hands on! Let $(n,m)$ be an element of $\mathbb{Z}_9\times \mathbb{Z}_{10}$. We define the orbit of this element as $O(n,m)=\{(kn, km)|k\in \mathbb{Z}\}$, more intuitively just $(n,m), (2n,2m), (3m,3m), \cdots$. The orbit of $(n,m)$ is the whole group if and only if $(n,m)$ is a generator.

So let's check: If $n=0,3,6,$ then the orbit cannot be the whole thing. For $0$ becuase $k.0 = 0$, for $3$ becuase $3.3=9\mod{9}=0$ and for $6$ because $3\times 6=18\mod{3}=0$.

For $m = 0,2, 4, 5, 6, 8$ you have the same problem in $\mathbb{Z}_{10}$. Hence the only viable candidates for generating have $m=1, 3,7,9$ and $n=1,2,4,5,7,8$. Define $$S=\{(n,m)|n=1,2,4,5,7,8, m=1,3,7,9\}$$

Next thing is to check which of these are actually generators. We need to check how long does it take $(n,m)$ to come back to itself. Or what is the first $k$ such that $(n,m) = (kn,km)$ in $\mathbb{Z}_9\times \mathbb{Z}_{10}$. Now if $(k-1)n\mod{9}=0$ and as we saw none of the candidates have any common factor with $9$, so $k-1=9\ell$. Also similar we must have $(k-1)=10\ell'$. Meaning $9\ell=10\ell'$. Again since $9$ and $10$ have no common factor, the smallest $\ell=10$ and $\ell'=9$. $k-1=90$, meaning $k=91$. Since the order of the group is $90$, this means all elements in $S$ are generators. We have $6\times 4=24$ generators.

Now let me ask you this, with this in mind, can you generalize this for $\mathbb{Z}_q\times\mathbb{Z}_{r}$ with $(q,r)=1$ ($q,r$ have no common factors)? Can you generalize this even further?

Answer 2

The natural map $\mathbb{Z}_{90}\rightarrow \mathbb{Z}_9\times\mathbb{Z}_{10}$ given by sending elements of $\mathbb{Z}_{90}$ to their classes mod 9 and 10 is an isomorphism (this is the Chinese remainder theorem). Thus, obviously 1 is a generator of $\mathbb{Z}_{90}$, so its image in $\mathbb{Z}_9\times\mathbb{Z}_{10}$ is $(1,1)$, so yes $(1,1)$ generates the group.

There are not many other generators. Note $\phi(90) = \phi(9)\phi(2)\phi(5) = 6\cdot 1\cdot 4 = 24$. The generators are precisely the image of elements of $\mathbb{Z}_{90}^\times$ in $\mathbb{Z}_9\times\mathbb{Z}_{10}$.