1
$\begingroup$

A group (S, $\odot$) is called cyclic if there exists g $\in$ S such that for every a $\in$ S there exists an integer n such that a = g $\odot$ g ... $\odot$ g (n times). If such a g $\in$ S exists, it is called a generator.

Is the group $\mathbb{Z}^{*}_{13}$= {1, 2 ... 11, 12} together with multiplication modulo 13 then cyclic? I can't seem to find the generators

$\endgroup$
  • $\begingroup$ You really didn't need to define a group, or even define cyclic group. $\endgroup$ – Thomas Andrews Nov 19 '13 at 21:27
  • $\begingroup$ A group is cyclic if and only if it is generated by a single element. If there is no single element which generates the group, it is not cyclic. Can you find an element that generates $\mathbb{Z}_{13}^*$? $\endgroup$ – D Wiggles Nov 19 '13 at 21:28
  • $\begingroup$ Allright, i'll edit it! $\endgroup$ – user108287 Nov 19 '13 at 21:28
0
$\begingroup$

Without some background in number theory, all you can do is try various numbers. Obviously $1$ doesn't work. So try $2$. We get lucky, $2$ works. For let us find the various positive powers of $2$, reduced modulo $13$. We get, in order, $$2,4,8,3,6,12,11,9,5,10,7,1.$$

Remark: There are other generators, a total of $4$ of them. It turns out that they are $2^1$, $2^5$, $2^7$, and $2^{11}$ (modulo $13$).

At this early stage, if you want all the generators, it is best to compute. Let us test $3$. The various powers, modulo $13$, are $3$, $9$, $1$, and now things start all over again, so we certainly won't get everything.

Next let's try $4$. The powers of $4$ will be the even powers of $2$, so we can look back on the work we did with $2$ and see that we will only get $4$, $3$, $12$, $9$, $10$, and $1$.

Quite a few left. Let's try $5$. It turns out that $5$ is no good, because $5^4$ gives $1$. Continue.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. Isn't it so that in fact, if p is prime, the generators of Z$_p$ are 1, 2, ..., $p - 1$? So that would mean all the numbers from 1 to 12 are generators. $\endgroup$ – user108287 Nov 19 '13 at 21:50
  • 1
    $\begingroup$ No. If $p$ is prime, and you look at the numbers $0$ to $p-1$, under addition modulo $p$, then $1,2,\dots,p-1$ are indeed all generators. However, your group is a different one, different number of elements, $12$ instead of $13$, and the operation is multiplication modulo $p$. $\endgroup$ – André Nicolas Nov 19 '13 at 21:55
  • $\begingroup$ You are welcome. Concrete computational experience is very important, else this stuff may remain a bunch of mysterious "rules." $\endgroup$ – André Nicolas Nov 19 '13 at 21:58
0
$\begingroup$

Try to determine the order of each element. Iff there is no element of order 12, the group isn't cyclic.

$\endgroup$
0
$\begingroup$

It is cyclic. You can take for example $2$ as generator: $$1=2^{11},2=2^1,3=2^4,4=2^2,5=2^8,6=2^5$$ $$7=2^{10},8=2^3,9=2^7,10=2^9,11,12=2^6$$ In fact $\mathbb{Z}_p^*$ is prime for every prime $p$.

$\endgroup$

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.