Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Relationship between primitive roots of a prime

  1. Nov 17, 2009 #1
    Hi all,

    I've been staring at this question on and off for about a month:

    Suppose that p is an odd prime, and g and h are primitive roots modulo p. If a is an integer, then there are positive integers s and t such that [tex]a \equiv g^s \equiv h^t[/tex] mod p. Show that [tex]s \equiv t[/tex] mod 2.

    I feel as though understanding this will give me greater insight into primitive roots, but I'm having trouble even getting started.

    Hints, or a push in the right direction would be great!


    Thanks :)
     
  2. jcsd
  3. Nov 17, 2009 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    h is a power of g.
     
  4. Nov 17, 2009 #3
    If k is the index of h, then
    [tex]h \equiv g^k \: mod \: p [/tex]

    and:
    [tex]g^s \equiv (\left g^k )\right ^t \: mod \: p[/tex]

    Is that the right idea?
     
  5. Nov 18, 2009 #4
    So...

    [tex]g = h^k, \:for\: (k,p-1)=1[/tex]

    substituting:

    [tex]g^s \equiv \left( g^k \right)^t \: mod \: p[/tex]
    or
    [tex]g^s \equiv \left( g^t \right)^k \: mod \: p[/tex]

    We know that if p|ab, then p|a or p|b.. so:
    [tex]g^s \equiv g^t \: mod \: p[/tex]


    Is that correct? What would come next?
     
  6. Nov 19, 2009 #5
    decide what are the 2 possibilities for the equation s = kt mod 2 More to the point how many square residues are there for each primative root and which ones are they?
     
    Last edited: Nov 19, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Relationship between primitive roots of a prime
  1. Primitive roots (Replies: 10)

  2. Primitive roots (Replies: 5)

  3. Primitive roots. (Replies: 3)

  4. Primitive root ! (Replies: 2)

Loading...