Originally Posted by

**utopiaNow** Let $\displaystyle 1, w, w^2 ,..., w^{n - 1}$ form a cyclic group $\displaystyle G$ of order $\displaystyle n$. Where $\displaystyle w$ is the principle primitive n-th root of unity. Show that $\displaystyle w^k$ also generates $\displaystyle G$ if and only if $\displaystyle (k, n) = 1$. (Hint: If $\displaystyle (k, n) = 1$ that is $\displaystyle k$ and $\displaystyle n$ are relatively prime then 1 can be written as a linear combination of $\displaystyle k$ and $\displaystyle n$.)

My attempt: Need to prove $\displaystyle w^k \textrm{ generates } G \Leftrightarrow (k,n) = 1$

$\displaystyle \Rightarrow$(Contradiction) Assume $\displaystyle w^k$ generates $\displaystyle G$, that is $\displaystyle 1,w^k, w^{2k},\ldots,w^{(n-1)k}$ form the cyclic group $\displaystyle G$. Suppose $\displaystyle (k,n)\neq 1$, Then I get stuck here and can't get my algebraic manipulations to lead me to a discernible contradiction.

$\displaystyle \Leftarrow$ For this implication I'm guessing we'll have to use the hint, but I'm not sure how it could prove useful. I used the hint to get: $\displaystyle ak + bn = 1$, for some integers $\displaystyle a, b$. Then $\displaystyle w = w^{ak + bn} = w^{ak}(w^{n})^b = w^{ak}$. So I have $\displaystyle w = w^{ak}$. But does that tell me that $\displaystyle w^{ak}$ is a generator of $\displaystyle G$, for some $\displaystyle a$?

Any suggestions would be appreciated. Thanks in advance.