Relationship between primitive roots of a prime

[thomas430]

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 a \equiv g^s \equiv h^t mod p. Show that s \equiv t 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 :)

 

[Hurkyl]

h is a power of g.

 

[thomas430]

If k is the index of h, then
h \equiv g^k \: mod \: p

and:
g^s \equiv (\left g^k )\right ^t \: mod \: p

Is that the right idea?

 

[thomas430]

So...

g = h^k, \:for\: (k,p-1)=1

substituting:

g^s \equiv \left( g^k \right)^t \: mod \: p
or
g^s \equiv \left( g^t \right)^k \: mod \: p

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


Is that correct? What would come next?

 

[ramsey2879]

So...

g = h^k, \:for\: (k,p-1)=1

substituting:

g^s \equiv \left( g^k \right)^t \: mod \: p
or
g^s \equiv \left( g^t \right)^k \: mod \: p

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


Is that correct? What would come next?

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?