2
$\begingroup$

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?

$\endgroup$
6
  • $\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
    Commented Nov 4, 2015 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
    Commented Nov 4, 2015 at 5:34
  • $\begingroup$ @JyrkiLahtonen multiples? $\endgroup$
    – Indigo
    Commented Nov 4, 2015 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
    Commented Nov 4, 2015 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
    Commented Nov 4, 2015 at 5:53

2 Answers 2

Reset to default
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I wouldn't say "not many". But +1. $\endgroup$
    – Caleb Stanford
    Commented Nov 4, 2015 at 6:18
3
$\begingroup$

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?

$\endgroup$
2
  • $\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
    Commented Nov 4, 2015 at 6:04
  • $\begingroup$ yes of course it is a typo, I'll fix it... $\endgroup$
    – Hamed
    Commented Nov 4, 2015 at 6:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .