Results 1 to 4 of 4

Math Help - Primitive root

  1. #1
    Member
    Joined
    Nov 2007
    Posts
    108

    Primitive root

    I'm having difficulty with solving this problem, hope somebody could help.
    Suppose (a,p)=1 where a is an integer and p is prime.
    1) Show A={ m, 2m, 3m,..., (p-1)m} is is reduced residue system mod p.
    2) Let C_k=1^k +2^k+...(p-1)^k. Use part 1) to show that
    m^kC_k \equiv C_k mod p
    3) Let the number m be the primitive root g mod p. Prove that C_k\equiv 0 mod p if p-1 doesn't divide k.

    For the first part, can we pick a reduced residue system mod p, {1,2,3,...,p-1} then try to show that A={m,2m,3m,...,(p-1)m} again a r.r.s mod p. We know that {km} where k=1,2,...,p-1 are relatively prime to p. Then it suffices to show that no two elements from A are congruent mod p. Am I on the right track on this? I really have no idea on the last two questions.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by namelessguy View Post
    Suppose (m,p)=1 where a is an integer and p is prime.
    1) Show A={ m, 2m, 3m,..., (p-1)m} is is reduced residue system mod p.
    Show that mi \equiv mj (\bmod p) \implies i\equiv j (\bmod p) and so m,2m,...,(p-1)m are all distinct. Therefore by pigeonholing they are a reduced residue system.

    2) Let C_k=1^k +2^k+...(p-1)^k. Use part 1) to show that
    m^kC_k \equiv C_k mod p
    Because you get m^k C_k = (m)^k + (2m)^k + ... + (m(p-1))^k. And that is a permutation of 1^k + ... + (p-1)^k mod p by #1.

    3) Let the number m be the primitive root g mod p. Prove that C_k\equiv 0 mod p if p-1 doesn't divide k.
    We get C_k(g^k -1 ) \equiv 0 (\mod p). And g^k -1 \not \equiv 0 (\bmod p) if p-1\not | k since it is a primitive root.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2007
    Posts
    108
    Thanks for you help, theperfecthacker, but can you elaborate on the second question. I don't really get your answer for that part.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    What you showed in #1 is that each of m, 2m, \hdots, (p-1)m is congruent to one of 1, 2, 3, \hdots, p-1. This means that if you took all the least residues of the first list, you will eventually get the list of all numbers from 1 up to p-1 in some order:

    \begin{array}{rcll}m^{k}C_{k}  & \equiv & m^k (1^k + 2^k + \hdots + (p-1)^k) & (\text{mod } p) \\ & \equiv & {\color{red}m}^k + ({\color{red}2m})^k + ({\color{red}3m})^k \hdots + ({\color{red}(p-1)m})^k & (\text{mod } p) \\ & \equiv & ({\color{red}1})^k + ({\color{red}2})^k + \hdots + ({\color{red}p-1})^k & (\text{mod } p) \end{array}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: February 27th 2011, 05:59 PM
  2. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 8th 2010, 08:49 AM
  3. Primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 07:47 PM
  4. primitive root
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 28th 2008, 08:36 AM
  5. primitive root
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 30th 2006, 02:21 PM

Search Tags


/mathhelpforum @mathhelpforum