Results 1 to 6 of 6

Math Help - Index Arithmetic

  1. #1
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Index Arithmetic

    The question asks to show that if p is an odd prime, and r is a primitive root of p, then ind_r (p-1) = (p-1)/2

    I don't even know where to start -- r^(p-1) = r^(phi(p)) which is congruent to one modulo p. Writing this out, I would have that r^(p-1) = kp +1.

    I'm just starting on modular arithmetic today, so forgive me for my lack of knowledge...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jan 2009
    Posts
    56

    Re: Index Arithmetic

    Use Fermat little theorem,  r^{p-1} =1 mod p and factorise  (r^{\frac{p-1}{2}}-1)(r^{\frac{p-1}{2}}+1)=0 mod p.
    gcd(r,p)=1, now because r is primitve root of p,  \phi(p) =p-1 is the lowest power such that r^k =1 mod p, which means that:
     r^{\frac{p-1}{2}}= -1 mod p = (p-1) mod p
    Now if there's a lowers integer s.t  r^k = p-1 mod p then  r^{2k} =1 mod p where k is smaller than (p-1)/2, and thus 2k is smaller than p-1, contradiction.
    From this follows your claim.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Re: Index Arithmetic

    Thanks Invisibleman! Admittedly, though, I'm confused as to how you can jump to r^(p-1 /2) congruent to -1 mod p. Is that a common identity?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Index Arithmetic

    Quote Originally Posted by jsndacruz View Post
    The question asks to show that if p is an odd prime, and r is a primitive root of p, then ind_r (p-1) = (p-1)/2

    I don't even know where to start -- r^(p-1) = r^(phi(p)) which is congruent to one modulo p. Writing this out, I would have that r^(p-1) = kp +1.

    I'm just starting on modular arithmetic today, so forgive me for my lack of knowledge...

    r is primitive root of p therefor \text{ind}_r1=p-1.

    Now,  p-1= \text{ind}_r(-1)(-1)\overset{Theorem}{\equiv}

    \equiv\text{ind}_r(-1)+\text{ind}_r(-1)=2\text{ind}_r(-1)(\mod p-1).

    Therefor:

    \text{ind}_r(-1)\equiv \frac{p-1}{2}(\mod p-1)

    and by definition of the index...

    \text{ind}_r(-1)= \frac{p-1}{2}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2009
    Posts
    56

    Re: Index Arithmetic

    Quote Originally Posted by jsndacruz View Post
    Thanks Invisibleman! Admittedly, though, I'm confused as to how you can jump to r^(p-1 /2) congruent to -1 mod p. Is that a common identity?
    because if r^((p-1)/2) is congruent to 1 then we have a contradiction to the fact that p-1 is the smallest power that r^k is congruent to 1.
    After this I am using the fact that (r^((p-1)/2)-1)(r^((p-1)/2)+1) = 0 mod p to deduce that r^((p-1)/2) = -1 mod p.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Re: Index Arithmetic

    Ahh that makes sense InvisibleMan. I didn't see that step when I was running through it. Thanks so much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Index Arithmetic Questions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 10th 2010, 05:54 PM
  2. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 8th 2009, 01:36 AM
  3. Index Arithmetic
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 17th 2009, 02:27 PM
  4. index
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 11th 2008, 04:36 PM
  5. 10-sec vol index
    Posted in the Statistics Forum
    Replies: 0
    Last Post: June 16th 2008, 02:47 PM

Search Tags


/mathhelpforum @mathhelpforum