Alg7.10

From Exampleproblems

Prove that if $G=<a>\,$ 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\isin G\,$ such that $rs\equiv 1(\mathrm{mod} \,\,n)\,$ .

Proof:

$(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\isin \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\isin\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\,$ .