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?