# Math Help - Cyclic group - Primitive roots of unity

1. ## [Solved]Cyclic group - Primitive roots of unity

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

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

$\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: $ak + bn = 1$, for some integers $a, b$. Then $w = w^{ak + bn} = w^{ak}(w^{n})^b = w^{ak}$. So I have $w = w^{ak}$. But does that tell me that $w^{ak}$ is a generator of $G$, for some $a$?

Any suggestions would be appreciated. Thanks in advance.

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

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

$\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: $ak + bn = 1$, for some integers $a, b$. Then $w = w^{ak + bn} = w^{ak}(w^{n})^b = w^{ak}$. So I have $w = w^{ak}$. But does that tell me that $w^{ak}$ is a generator of $G$, for some $a$?

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

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

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

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

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

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

4. Originally Posted by utopiaNow
I'm guessing $w^{ik}=w^{ik}$ was supposed to be $w^{ik}=w^{jk}$ for $i, j \in [0,n-1]$ like you said. So no it's not possible to have $n|(i-j)$ as the highest possible value $i-j$ could take would be $n-1$. But I don't see how we can conclude that $w^k$ is of order $n$ for that reason.
So, each of $i \in [0,n-1]$ we will get different $w^{ik}$. Thus we get 'n' different elements. Thus we have generated the original group just by using powers of $w^{k}$. Hence it is a generator.

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

Sorry if I missed something obvious, these are just the gaps in my understanding.
$(a^{k})^{n/(n,k)}=1$
=> $n|{n/(n,k)}$ as $n$ is order of $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 $a^x = 1$ then order of 'a' divides x.

5. " 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.