# Relationship between primitive roots of a prime

1. Nov 17, 2009

### 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 :)

2. Nov 17, 2009

### Hurkyl

Staff Emeritus
h is a power of g.

3. Nov 17, 2009

### 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?

4. Nov 18, 2009

### 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?

5. Nov 19, 2009

### ramsey2879

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