Results 1 to 5 of 5

Thread: Cyclic group - Primitive roots of unity

  1. #1
    Junior Member utopiaNow's Avatar
    Joined
    Mar 2009
    Posts
    72
    Thanks
    1

    [Solved]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.
    Last edited by utopiaNow; Oct 12th 2009 at 12:54 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by utopiaNow View Post
    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)$?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member utopiaNow's Avatar
    Joined
    Mar 2009
    Posts
    72
    Thanks
    1
    Quote Originally Posted by aman_cc View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by utopiaNow View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    " 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Dec 2nd 2011, 08:23 AM
  2. [SOLVED] Roots of Unity as a group
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Aug 27th 2011, 04:05 PM
  3. Primitive Roots of Unity and GCD
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 1st 2010, 05:43 PM
  4. Galois group, cyclic real roots :)
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 26th 2009, 11:48 AM
  5. Roots of unity isomorphic to cyclic group?
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Nov 23rd 2008, 11:19 PM

Search Tags


/mathhelpforum @mathhelpforum