# Alg7.10

Prove that if $G=\,$ and $|G|=n\,$ then the following are equivalent:
(a) $|a^{r}|=n\,$ which means $a^{r}\,$ is a generator of $G\,$.
(b) $(r,n)=1\,$ i.e. $r$ and $n\,$ are relatively prime.
(c) $\exists s\in G\,$ such that $rs\equiv 1({\mathrm {mod}}\,\,n)\,$.
$(a\implies c)\,$ If $a^{r}\,$ is a generator then the element $a\,$ can be written $(a^{r})^{k}=a\implies rk\equiv 1({\mathrm {mod}}\,\,n)\,$.
$(c\implies b)\,$ Assume $(r,n)=d>1\,$. Then $r'ds\equiv 1({\mathrm {mod}}\,\,n'd)\implies r'ds-1=kn'd\,,k\in {\mathbb {Z}}\,$. Since $d\,$ divides the right side of the equation it has to divide both terms on the left, which is contradiction of $d>1\,$.
$(b\implies a)\,$ $(r,n)=1\implies qr+sn=1\,$ for some $q,s\in {\mathbb {Z}}\,$. Then $a=a^{{qr+sn}}=a^{{qr}}=(a^{r})^{q}\,$ so any element $a\,$ can be written as a power of $a^{r}\,$ which means $a^{r}\,$ is a generator and therefore $|a^{r}|=n\,$.