Results 1 to 5 of 5

Math Help - Primitive roots mod p

  1. #1
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163

    Primitive roots mod p

    Here's a fun challenge problem!

    Show that the product of all primitive roots modulo  p is congruent to  (-1)^{\phi(p-1)} modulo  p .

    Show that the sum of all primitive roots modulo  p is congruent to  \mu(p-1) modulo  p .
    Last edited by chiph588@; March 26th 2010 at 06:29 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Here is a hint. If a is a primitive root, then all primitive roots of mod p are a^k where 1\leq k\leq n and (k,n)=1.

    Quote Originally Posted by chiph588@ View Post
    Show that the product of all primitive roots modulo  p is congruent to  (-1)^{\phi(p-1)} modulo  p .
    So we approach this by the hint, let a be a primitive root. Then the product of all primitive roots mod p is \prod_{1\leq k \leq n}^{(k,n)=1} a^k. Now for every primitive root a^k we see that a^{p-k} is a primitive root also. Therefore, we can pair the primitive roots with their inverses. We just need to be careful, we need to know that a^k is not paired with itself. But a^k \not \equiv a^{p-k}(\bmod p) if p>2. Thus, if p>2 we get 1 and if p=2 then we get -1. And so it is correct to write (-1)^{\phi(p-1)} because \phi(m) is even for m\geq 3.


    Show that the sum of all primitive roots modulo  p is congruent to  \mu(p-1) modulo  p .
    This one should be approached like the one above. But this one is tricker. Let us focus on an easier case first, say p\equiv 1(\bmod 4). Now a is a primitive then p-a is a primitive root too (prove this). And so the entire sum can be paired to cancel out mod p. And so we are left with zero. Notice that if p\equiv 1(\bmod 4) then 4 divides p-1 and so \mu(p-1)=0. Now you need to consider other cases.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Another approach for the second question. (this also works for the first one)

    First a little Theorem that always comes in handy.

    Theorem
    : Let <br />
F\left( n \right) = \sum\limits_{\left( {k,n} \right) = 1;{\text{ }}1 \leqslant k \leqslant n} {f\left( {\tfrac{k}<br />
{n}} \right)} <br />
then <br />
\sum\limits_{\left. d \right|n} {F\left( d \right)}  = \sum\limits_{k = 1}^{n} {f\left( {\tfrac{k}<br />
{n}} \right)} <br />
with <br />
n \in \mathbb{Z}^+<br />

    Proof.

    We will show first that all of the terms of the RHS are appear once and only once on the LHS.

    So, consider: <br />
f\left( {\tfrac{k}<br />
{n}} \right)<br />
with <br />
1 \leqslant k \leqslant n<br />
then <br />
\tfrac{k}<br />
{n} = \frac{{\tfrac{k}<br />
{{\left( {k,n} \right)}}}}<br />
{{\tfrac{n}<br />
{{\left( {k,n} \right)}}}} = \tfrac{{k'}}<br />
{{n'}}<br />
where <br />
k' = \tfrac{k}<br />
{{\left( {k,n} \right)}} \wedge n' = \tfrac{n}<br />
{{\left( {k,n} \right)}}<br />
note also that this implies: <br />
\left( {k',n'} \right) = 1 \wedge \left. {n'} \right|n<br />
, hence it corresponds to one of the terms (and only one) in <br />
F\left( {n'} \right)<br />
(we are considering each of the terms as if they were different elements)

    Conversly, it's easy to see that each of the terms on the LHS of our identity appears once only on the RHS. \square

    _______________________________________

    Now let's go to our problem, let g be a primitive root module p, then our sum is congruent to <br />
S =\sum\limits_{\left( {k,p - 1} \right) = 1;{\text{ }}1 \leqslant k \leqslant p-1} {g^k } <br />
module p (since the exponents must be coprime with <br />
\phi \left( p \right) = p - 1<br />
for them to be primitive roots, and that is sufficient). So consider in general: <br />
S_n  = \sum\limits_{\left( {k,n} \right) = 1;{\text{ }}1 \leqslant k \leqslant n} {a^{\tfrac{k}<br />
{n}} } <br />
then we'll set <br />
n = p - 1 \wedge a = g^{p - 1} <br />

    We have: <br />
\sum\limits_{\left. d \right|n} {S_d }  = \sum\limits_{k = 1}^n {a^{\tfrac{k}<br />
{n}} }  = \tfrac{{a^{\tfrac{1}{n}} - a^{\tfrac{{n + 1}}<br />
{n}} }}<br />
{{1 - a^{\tfrac{1}<br />
{n}} }}<br />
hence by Möbius inversion formula: <br />
S_n  = \sum\limits_{\left. d \right|n} {\tfrac{{a^{\tfrac{1}{d}} - a^{1 + \tfrac{1}<br />
{d}} }}<br />
{{1 - a^{\tfrac{1}<br />
{d}} }} \cdot \mu \left( {\tfrac{n}<br />
{d}} \right)} <br />

    Thus: <br />
S = \sum\limits_{\left. d \right|\left( {p - 1} \right)} {\left( {\tfrac{{g^{\tfrac{{p - 1}}<br />
{d}}  - g^{\left( {\tfrac{{p - 1}}<br />
{d}} \right) \cdot \left( {d + 1} \right)} }}<br />
{{1 - g^{\tfrac{{p - 1}}<br />
{d}} }}} \right) \cdot \mu \left( {\tfrac{{p - 1}}<br />
{d}} \right)}<br />
<br />
 = \sum\limits_{\left. d \right|\left( {p - 1} \right)} {g^{\tfrac{{p - 1}}<br />
{d}}  \cdot \left( {\tfrac{{1 - g^{p - 1} }}<br />
{{1 - g^{\tfrac{{p - 1}}<br />
{d}} }}} \right) \cdot \mu \left( {\tfrac{{p - 1}}<br />
{d}} \right)} <br />

    Next note that: <br />
\left. p \right|\left( {1 - g^{p - 1} } \right)<br />
and <br />
  p  \not| ( 1-g^{\tfrac{p-1}{d}} )<br />
when <br />
\left. d \right|\left( {p - 1} \right) \wedge d \ne 1<br />
simply because g is a primitive root.

    Thus: <br />
S \equiv g^{\tfrac{{p - 1}}<br />
{1}}  \cdot \left( {\tfrac{{1 - g^{p - 1} }}<br />
{{1 - g^{\tfrac{{p - 1}}<br />
{1}} }}} \right) \cdot \mu \left( {\tfrac{{p - 1}}<br />
{1}} \right) \equiv \mu \left( {p - 1} \right)\left( {\bmod .p} \right)<br />
 \square
    Last edited by PaulRS; February 10th 2009 at 08:49 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by ThePerfectHacker View Post
    Here is a hint. If a is a primitive root, then all primitive roots of mod p are a^k where 1\leq k\leq n and (k,n)=1.
    What's  n ?

    You mean  \phi(p) , right?


    And isn't the inverse of  a^k congruent to  a^{p-k-1} because  a^k a^{p-k-1} = a^{p-1} \equiv 1 \mod{p} ?
    Last edited by chiph588@; February 11th 2009 at 10:14 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by chiph588@ View Post
    What's  n ?

    You mean  \phi(p) , right?
    If a is primitive root say for p=11 then all other primitive roots are congruent with a,a^3,a^7,a^9 because we need to have a^k where (k,n)=1 here n=\phi(11) = \phi(10) so we have (k,10)=1 which happens with k=1,3,7,9.

    And isn't the inverse of  a^k congruent to  a^{p-k-1} because  a^k a^{p-k-1} = a^{p-1} \equiv 1 \mod{p} ?
    I meant that . But the idea is still okay, again if p=11 then product of primitive roots is congruent to a\cdot a^3 \cdot a^7\cdot a^9. Now pair the inverses a\to a^9 , a^3\to a^7 and everything collapses to 1 mod p.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 10th 2011, 06:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 17th 2008, 09:09 PM
  3. Primitive roots
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 15th 2007, 10:19 AM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 21st 2006, 08:05 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2006, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum