Proofread my work: Expressing generators of a cyclic group

Question

The following question comes from Serge Lang's Undergraduate Algebra(pg. 26, 3rd edition). I just learnt the concept of groups and subgroups and I spent an hour or so on tackling part (b) of this problem. Here is the question and my work. Please:

1) Comment on my proof. I appreciate any ideas or corrections.

2) Tell me your proof, so that I can learn from you!:)

Questions:

Let $G$ be a finite cyclic group of order $n$. Let $a$ be a generator. Let $r$ be an integer $\neq 0$, and relatively prime to $n$.

a) Show that $a^r$ is also a generator of $G$.

b) Show that every generator of $G$ can be written in this form.

Proof of (b):

In part (a), we have shown that for any $a^r$, where $r$ is relatively prime to $n$, it is a generator of $G$. It then remains to show that $a^p$ is not a generator of $G$ if $p$ is not relatively prime to $n$.

Consider such an element $a_p \in G=\{e,a,a^2,...,a^p,...,a^{n-1}\}$. Note that $0\leq p < n$. We write $pq=n$ for some $q \in \mathbb{Z}$.

Then, $<a^p>=\{a^p, a^{2p},...,a^{p(q-1)}, a^{pq}=a^n=e\}$. Now, note that the order of $<a^p>$ is $q$ while the order of $G$ is $n$. It follows that $<a^p> \neq G$ as desired.

Thanks in advance.

Answer 1

Another approach for (a):

If $(r,n) = 1$, then there are integers $x,y$ such that $1 = xr + yn$. So $a = a^1 = a^{xr + yn} = (a^r)^x(a^n)^y = (a^r)^x$. Therefore, the subgroup $\langle a^r \rangle$ generated by $a^r$ contains $a$, which means that $\langle a \rangle \subseteq \langle a^r \rangle$. The reverse containment $\langle a^r \rangle \subseteq \langle a \rangle$ is clear, so in fact we have $\langle a^r \rangle = \langle a \rangle$.

Another approach for (b):

If $r$ and $n$ are not relatively prime, then their gcd $d$ is greater than $1$. So $m = n/d$ is an integer which is less than $n$, and $r/d$ is also an integer. Then $(a^r)^m = (a^r)^{(n/d)} = (a^{(r/d)})^n = 1$ where the last equality holds because $g^n = 1$ for any element $g$ of a group which has order $n$. But $(a^r)^m = 1$ means that the order of $a^r$ is at most $m = n/d < n$, so $a^r$ cannot be a generator.

Answer 2

For (a) if $a$ is a generator, you need to show $a^{r}$ is a generator for all $r$ such that $(r,n) = 1$. So assume $a$ is a generator, $(r,n) = 1$ but towards a contradiction, $a^r$ is not a generator. Then the order of $a^r$ is less than $n$, say $p<n$. So $\langle a^{rp} \rangle =\{a^r,a^{2r},\ldots ,a^{pr} = e\}$. Thus $$ \langle a^{rp}\rangle a^{-{rp}} = \{a^r,a^{2r},\ldots, a^{rp}\}a^{-rp} = \underbrace{\{(a^{r})^{-p+1}, (a^{r})^{{-p+2}}\ldots , a^{0}\}}_{p \text{ terms}} = $$ $$ \underbrace{\{e\cdot a, e\cdot a^2,\ldots , a^{0}\}}_{p \text{ terms}} = \underbrace{\{a, a^2, \ldots, e \}}_{p \text{ terms}} $$ a contradiction to the order of $a$ being $n > p$

For (b), there are exactly $\phi(n)$ generators for a cyclic group of order $n$. If there was one generator $q$ that could not be written as $a^r$, where $a$ is the aforementioned generator as before and $r$ is a number coprime with $n$, then there is some $1<s<n$ with $n>\gcd(s,n)>1$ such that $a^s = q$. Then there would be at least $\phi(n)+1$ generators for this cyclic group of order $n$, a contradiction.