Thread: Cyclic group - Primitive roots of unity

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.

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.

Let me give you hint for part 2.
Let $\displaystyle w^{ik}=w^{ik}$
$\displaystyle w^{(i-j)k}=1$
Thus, $\displaystyle n|(i-j)k$ as order of $\displaystyle w$ is $\displaystyle n$
Under $\displaystyle (k, n) = 1$ this implies $\displaystyle n|(i-j)$. But is that possible if $\displaystyle i \neq j$ and both $\displaystyle i,j \in [0,n-1]$. Hence can you conclude order of $\displaystyle w^k$ is n. Hence it is a generator.

For the reverse side. Claim $\displaystyle (a^{k})^{n/(n,k)}=1$. But if $\displaystyle a^{k}$ is generator its order = $\displaystyle n$. What can you then claim about $\displaystyle (n,k)$?

Originally Posted by aman_cc

Let me give you hint for part 2.
Let $\displaystyle w^{ik}=w^{ik}$
$\displaystyle w^{(i-j)k}=1$
Thus, $\displaystyle n|(i-j)k$ as order of $\displaystyle w$ is $\displaystyle n$
Under $\displaystyle (k, n) = 1$ this implies $\displaystyle n|(i-j)$. But is that possible if $\displaystyle i \neq j$ and both $\displaystyle i,j \in [0,n-1]$. Hence can you conclude order of $\displaystyle w^k$ is n. Hence it is a generator.

For the reverse side. Claim $\displaystyle (a^{k})^{n/(n,k)}=1$. But if $\displaystyle a^{k}$ is generator its order = $\displaystyle n$. What can you then claim about $\displaystyle (n,k)$?

I'm guessing $\displaystyle w^{ik}=w^{ik}$ was supposed to be $\displaystyle w^{ik}=w^{jk}$ for $\displaystyle i, j \in [0,n-1]$ like you said. So no it's not possible to have $\displaystyle n|(i-j)$ as the highest possible value $\displaystyle i-j$ could take would be $\displaystyle n-1$. But I don't see how we can conclude that $\displaystyle w^k$ is of order $\displaystyle n$ for that reason.

Also for the reverse, I see how $\displaystyle (n,k)$ would need to be equal to 1, if $\displaystyle (a^{k})^{n/(n,k)}=1$ was true. But how can I make that claim? Because $\displaystyle (a^{k})^{n/(n,k)} = (a^{kn})^{1/(n,k)} = 1^{1/(n,k)}$, where I got the last equality since $\displaystyle a^k$ is a generator, therefore this: $\displaystyle 1^{1/(n,k)}$ doesn't necessarily have to be 1, since it's the $\displaystyle (n,k)$-th root of 1.

Sorry if I missed something obvious, these are just the gaps in my understanding.

Originally Posted by utopiaNow

I'm guessing $\displaystyle w^{ik}=w^{ik}$ was supposed to be $\displaystyle w^{ik}=w^{jk}$ for $\displaystyle i, j \in [0,n-1]$ like you said. So no it's not possible to have $\displaystyle n|(i-j)$ as the highest possible value $\displaystyle i-j$ could take would be $\displaystyle n-1$. But I don't see how we can conclude that $\displaystyle w^k$ is of order $\displaystyle n$ for that reason.

So, each of $\displaystyle i \in [0,n-1]$ we will get different $\displaystyle w^{ik}$. Thus we get 'n' different elements. Thus we have generated the original group just by using powers of $\displaystyle w^{k}$. Hence it is a generator.

Also for the reverse, I see how $\displaystyle (n,k)$ would need to be equal to 1, if $\displaystyle (a^{k})^{n/(n,k)}=1$ was true. But how can I make that claim? Because $\displaystyle (a^{k})^{n/(n,k)} = (a^{kn})^{1/(n,k)} = 1^{1/(n,k)}$, where I got the last equality since $\displaystyle a^k$ is a generator, therefore this: $\displaystyle 1^{1/(n,k)}$ doesn't necessarily have to be 1, since it's the $\displaystyle (n,k)$-th root of 1.

Sorry if I missed something obvious, these are just the gaps in my understanding.

$\displaystyle (a^{k})^{n/(n,k)}=1$
=> $\displaystyle n|{n/(n,k)}$ as $\displaystyle n$ is order of $\displaystyle a^k$.

Hope you know that any generator of a finite set will have order equal to the order of the set. I have used that fact here.
I have also used the fact that if $\displaystyle a^x = 1$ then order of 'a' divides x.

" this: 1^{1/(n,k)} doesn't necessarily have to be 1, since it's the (n,k)-th root of 1."

Also I guess we should not confuse concepts. Whatever I have done is just based on Group Theory Axioms. It has no link to the fact that the elements are n-root of unity. It really makes no difference to our work in the present context.