Cyclic group - Primitive roots of unity

**utopiaNow** · October 11th 2009, 09:47 PM

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.

**aman_cc** · October 12th 2009, 12:21 AM

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)$ ?

**utopiaNow** · October 12th 2009, 01:39 AM

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.

**aman_cc** · October 12th 2009, 01:51 AM

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.

**aman_cc** · October 12th 2009, 02:03 AM

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

Thread: Cyclic group - Primitive roots of unity

LinkBack

Thread Tools

Display

[Solved]Cyclic group - Primitive roots of unity

Similar Math Help Forum Discussions

Basis of primitive nth roots of unity when n is squarefree?

[SOLVED] Roots of Unity as a group

Primitive Roots of Unity and GCD

Galois group, cyclic real roots :)

Roots of unity isomorphic to cyclic group?

Search Tags