# 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

-

1
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

1
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

2
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

1
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
show 1 more comment

## 2 Answers

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 61, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9246519804000854, "perplexity_flag": "head"}