Results 1 to 5 of 5

Math Help - 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 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.
    Last edited by utopiaNow; October 12th 2009 at 01: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 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)?
    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 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.
    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 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.
    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: December 2nd 2011, 09:23 AM
  2. [SOLVED] Roots of Unity as a group
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: August 27th 2011, 05:05 PM
  3. Primitive Roots of Unity and GCD
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 1st 2010, 06:43 PM
  4. Galois group, cyclic real roots :)
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 26th 2009, 12:48 PM
  5. Roots of unity isomorphic to cyclic group?
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: November 24th 2008, 12:19 AM

Search Tags


/mathhelpforum @mathhelpforum