Results 1 to 7 of 7

Math Help - Sum of primitive roots module p

  1. #1
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374

    Sum of primitive roots module p

    Let p be a prime, show that the sum of all the primitive roots module p is congruent to u(p-1) module p. u is the mobius function.
    I am considering the polymonial \Pi (x-g^k) in Z/pZ[x], where g is a primitive root, and the product is taken over all k such that g^k is also a primitive root. and...???

    Any help or new idea would be appriciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    A couple ideas.

    Idea 1: Let g be a primitive root module p.

    What you want to compute is: \displaystyle\sum_{(k,p-1)=1; 1\leq k \leq p-1} g^k in module p.

    Idea 2: Let f:\mathbb{Q}^+\to \mathbb{R} and F(n) = \displaystyle\sum_{(k,n)=1; 1\leq k \leq n} f \left( \frac{k}{n}\right)

    Then it can be shown that: \sum_{k|n} F(k) = \sum_{k=1}^n f\left(\frac{k}{n}\right) - prove this!.

    Mixing these 2 well works, I leave you the rest.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    I have proved the idea 2 by argument on the fractions k/n, where all k are between 1 and n.
    But I don't see how idea 2 is applied to this problem.
    Will you expain the details, please? or give a hint. Thanks again for you new idea.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    First, we begin ignoring the module (and then eventually we will take the module).

    We want to be able to compute F(n) = \displaystyle\sum_{(k,n)=1; 1\leq k \leq n} f \left( \frac{k}{n}\right) where  f \left( \frac{k}{n}\right) = a^{\tfrac{k}{n}} for a fixed a\in \mathbb{R}

    We know that \sum_{k|n} F(k) = \sum_{k=1}^n a^{\tfrac{k}{n}} =  \displaystyle\frac{a^{\tfrac{1}{n}} - a^{\tfrac{1}{n} + 1}}{1-a^{\tfrac{1}{n}}}

    Now we apply Möbius inversion formula: F(n) =  \sum_{d|n}{\mu\left(\frac{n}{d}\right)\cdot \frac{a^{\tfrac{1}{d}} - a^{\tfrac{1}{d} + 1}}{1-a^{\tfrac{1}{d}}} }

    Set n = p-1 and a = g^{p-1}

    Thus: F(p-1) = \displaystyle\sum_{d|(p-1)}{\mu\left(\frac{p-1}{d}\right)\cdot g^{\frac{p-1}{d}} \cdot  \frac{1 - g^{p-1}}{1- g^{\frac{p-1}{d}}} - no module involved yet.

    But now, g^{p-1} \equiv 1 (\bmod. p) and g^{\tfrac{p-1}{d}} \not\equiv 1 (\bmod. p) for all d|(p-1) such that d>1 ( since g is a primitive root) and so in those cases we have that \frac{1 - g^{p-1}}{1- g^{\frac{p-1}{d}}} is a multiple of p (it's not difficult to see it's an integer).

    Hence F(p-1)\equiv \mu(p-1) \cdot g^{p-1} \cdot  \frac{1 - g^{p-1}}{1- g^{p-1}} (\bmod. p), therefore F(p-1) \equiv \mu(p-1) (\bmod.p)

    But F(p-1)(\bmod.p) is what we wanted to compute! - by idea 1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    but then 1-g^(p-1) is equivlent to 0 mod p. what is 0/0 mod p? I think, it can be any nonzero element in Z/pZ, or even 0 itself. It is not well defined, and I am not convinced that it equals 1. why not 2 ?
    we can't just ignore the fraction part, right? I believe, you have noticed that, too.
    Although a little disagreement appears, thank you all the same.
    I am expecting your reply on this disagreement.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Ooops, I misunderstand you solution.
    I uderstand it completely now.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Shanks View Post
    but then 1-g^(p-1) is equivlent to 0 mod p. what is 0/0 mod p?
    I made the mistake of not writing that that term equals 1 before taking the module, all the same, it is still equal to 1. In fact, the whole thing of "not taking module yet" was to try not to confuse you with these sort of issues.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 4th 2010, 11:14 PM
  2. Primitive roots mod p
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 11th 2009, 03:03 PM
  3. Help With primitive roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 28th 2007, 02:37 PM
  4. Primitive roots
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 15th 2007, 10:19 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2006, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum