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?

  • $\begingroup$ Yes, the order is 90. And Yes.$g=(1,1)$ generates. But as a teacher I would be more interested in whether you fully understand why $g$ generates the whole group. But before we head there, the group operation in $\Bbb{Z}_9\times\Bbb{Z}_{10}$ is based on addition, so instead of "powers" of $g$ you should look at ________? $\endgroup$ – Jyrki Lahtonen Nov 4 '15 at 5:30
  • 1
    $\begingroup$ $(a,b)$ generates $\mathbf{Z}_9\times\mathbf{Z}_{10}$ if and only if $a$ generates $\mathbf{Z}_9$ and $b$ generates $\mathbf{Z}_{10}$. (Prove this.) $\endgroup$ – fkraiem Nov 4 '15 at 5:34
  • $\begingroup$ @JyrkiLahtonen multiples? $\endgroup$ – Indigo Nov 4 '15 at 5:38
  • $\begingroup$ Correct. In proving that $g$ generates the whole group it may (?) be illuminating to go via the route that $g_1=(1,0)$ and $g_2=(0,1)$ together surely generate all of it. Why? Therefore it suffices to show that $g_1$ and $g_2$ are both multiples of $g$. Have you done examples that allow you to see why that happens? $\endgroup$ – Jyrki Lahtonen Nov 4 '15 at 5:44
  • $\begingroup$ @JyrkiLahtonen I think I... Might have. Honestly the textbook leaves something to be desired in its explanation of this. $\endgroup$ – Indigo Nov 4 '15 at 5:53

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?

  • $\begingroup$ In the first part, why did you go from $(n,m)$ to $O(m,n)$... is this a typo, or am I missing something important? $\endgroup$ – Indigo Nov 4 '15 at 6:04
  • $\begingroup$ yes of course it is a typo, I'll fix it... $\endgroup$ – Hamed Nov 4 '15 at 6:06

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}$.

  • $\begingroup$ I wouldn't say "not many". But +1. $\endgroup$ – 6005 Nov 4 '15 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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