# Generators and subgroups of $\mathbf Z_{15}$

Could you help me with following excercise?

Find all generators of additive group Z15.

Find all sub-groups of additive group Z15.

Could you please explain how to do that and post a solution?

Thanks, Mark

-
In case this is a homework, please add the tag (homework). In any ways, what did you try? In which step did you get stuck? –  user2468 Mar 6 '12 at 17:33
To get started, can you think of one generator for $\mathbf Z_{15}$? Is $2$ a generator? Is $3$? –  Dylan Moreland Mar 6 '12 at 17:35
It might be time consuming, but if you're completely lost try writing out the addition table. –  you Mar 6 '12 at 17:39
Also, what do you know about the size of subgroups as compared to the size of the original group? –  JavaMan Mar 6 '12 at 17:50
The answer is the $10$ (equivalence classes of) numbers from $0$ to $14$ that are relatively prime to $15$. This can be verified painfully, by hand, one at a time. There is of course a shortcut theorem that tells me this, but computing is good. It is easy to verify the others don't work. Start with $1$. Sure. What about $2$? Keep adding $2$ to itself, modulo $15$. For a mild shortcut, note that $2+2+\cdots +2$ (eight of them) is $1$. But since $1$ is a generator, $\dots$. –  André Nicolas Mar 6 '12 at 18:05

An element $\overline{a}$ in $\mathbf{Z}_m$ generates if and only if its order is $m$. If $0\leq a\lt m$, then the order of $\overline{a}$ is the least positive integer $k$ such that $m|ka$. Since $a|ka$ for every integer $k$, it follows that the order of $\overline{a}$ is the smallest integer $k$ such that $ka=\mathrm{lcm}(m,a)$.

Under what conditions is $k=m$?

Since $\mathbf{Z}_m$ is cyclic, every subgroup is cyclic. Can you show that if $\overline{a}$ and $\overline{b}$ have the same order, then they generate the same subgroup?

-

I'll work with $\mathbf Z_6$. The differences are superficial and translating everything to the situation of $\mathbf Z_{15}$ will be good practice.

For $x \in \mathbf Z$ to be a generator for $\mathbf Z_6$, it is necessary and sufficient that some multiple of $x$ be congruent to $1 \bmod 6$, i.e. that $6 \mid (ax - 1)$ for some integer $a$. To expand this further, there exists an integer $b$ such that $b6 = ax - 1$, so $1 = ax - b6$. What does Bézout now tell you about $a$ and $6$?

It should follow that the classes of $1$ and $5$ are the possible generators.

For finding subgroups, you can do something analogous to how we characterize the subgroups of $\mathbf Z$. In fact, certain theorems make this more than an analogy. If $H$ is a subgroup of $\mathbf Z_6$, then let $y$ be the smallest integer among $\{1, \ldots, 6\}$ whose residue modulo $6$ is in $H$. Again using Bézout, show that $y$ must divide $6$ and that it generates $H$.

You should find that there are four subgroups, generated by the classes of $1$, $2$, $3$, and $6$.

-