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


    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]

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

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

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


    [tex]g^s \equiv \left( g^k \right)^t \: mod \: p[/tex]
    [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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook