Alg7.10

From Example Problems
Jump to: navigation, search

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\in 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\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\,.

Abstract Algebra

Main Page