1. ## primitive roots

Hi, I am having a tough time with this question.

Let $\displaystyle e$ and $\displaystyle f$ be primitive roots modulo an odd prime $\displaystyle p$ and let $\displaystyle a$ be an interger co-prime to p.
Using $\displaystyle a \equiv e^g \equiv f^h (mod \ p)$, prove $\displaystyle g \equiv h (mod \ 2)$.

Then show that $\displaystyle e^{p-2}$ is a primitive root modulo $\displaystyle p$.

For the first part I know that $\displaystyle g \equiv h (mod \ 2)$ means that $\displaystyle g$ and $\displaystyle h$ are either both odd or both even. But I need some help with this question.

Thank You for any help.

2. ## Re: primitive roots

Originally Posted by alexgeek101
Hi, I am having a tough time with this question.

Let $\displaystyle e$ and $\displaystyle f$ be primitive roots modulo an odd prime $\displaystyle p$ and let $\displaystyle a$ be an interger co-prime to p.
Using $\displaystyle a \equiv e^g \equiv f^h (mod \ p)$, prove $\displaystyle g \equiv h (mod \ 2)$.

Then show that $\displaystyle e^{p-2}$ is a primitive root modulo $\displaystyle p$.

For the first part I know that $\displaystyle g \equiv h (mod \ 2)$ means that $\displaystyle g$ and $\displaystyle h$ are either both odd or both even. But I need some help with this question.

Thank You for any help.
The primitive roots $\displaystyle e$ and $\displaystyle g$ are quadratic nonresidue of $\displaystyle p$; using the Legnedre Sybmol this means $\displaystyle (e/p)=(f/p)=-1$. Then $\displaystyle (e^g/p)=(e/p)\cdots(e/p)=(-1)^g$ and similarly $\displaystyle (f^h/p)=(-1)^h$.
But $\displaystyle e^g\equiv f^h\pmod p$ and therefore $\displaystyle (-1)^g=(e^g/p)=(f^h/p)=(-1)^h$, from which we see that $\displaystyle g$ and $\displaystyle h$ have the same parity.

3. ## Re: primitive roots

Originally Posted by melese
The primitive roots $\displaystyle e$ and $\displaystyle g$ are quadratic nonresidue of $\displaystyle p$; using the Legnedre Sybmol this means $\displaystyle (e/p)=(f/p)=-1$. Then $\displaystyle (e^g/p)=(e/p)\cdots(e/p)=(-1)^g$ and similarly $\displaystyle (f^h/p)=(-1)^h$.
But $\displaystyle e^g\equiv f^h\pmod p$ and therefore $\displaystyle (-1)^g=(e^g/p)=(f^h/p)=(-1)^h$, from which we see that $\displaystyle g$ and $\displaystyle h$ have the same parity.
At the start you mean 'primitive roots $\displaystyle e$ and $\displaystyle f$ ....'
So since $\displaystyle (-1)^g=(-1)^h$, this implies that $\displaystyle g \equiv h (mod \ 2)$.
Thanks heaps, that makes total sense.

Any thoughts on the second part of the question?

4. ## Re: primitive roots

Originally Posted by alexgeek101
Any thoughts on the second part of the question?

EDIT: Sorry I was wrong. And my computer is playing up!

5. ## Re: primitive roots

Originally Posted by Juneu436
EDIT: Sorry I was wrong. And my computer is playing up!
Well thanks anyway June for taking the time to look at it.

6. ## Re: primitive roots

Originally Posted by alexgeek101
Hi, I am having a tough time with this question.

Let $\displaystyle e$ and $\displaystyle f$ be primitive roots modulo an odd prime $\displaystyle p$ and let $\displaystyle a$ be an interger co-prime to p.
Using $\displaystyle a \equiv e^g \equiv f^h (mod \ p)$, prove $\displaystyle g \equiv h (mod \ 2)$.

Then show that $\displaystyle e^{p-2}$ is a primitive root modulo $\displaystyle p$.

For the first part I know that $\displaystyle g \equiv h (mod \ 2)$ means that $\displaystyle g$ and $\displaystyle h$ are either both odd or both even. But I need some help with this question.

Thank You for any help.
Let $\displaystyle m>0$ and $\displaystyle a$ be integers, with $\displaystyle (a,m)=1$.
Here's a general theorem: If the order of $\displaystyle a$ modulo $\displaystyle m$ is $\displaystyle d$, then the order of $\displaystyle a^k$ modulo $\displaystyle m$ is $\displaystyle d/(k,d)$, for $\displaystyle k\geq1$.

It follows that the values of $\displaystyle k$ for which $\displaystyle a^k$ has order $\displaystyle d$ modulo $\displaystyle m$ are exactly those satisfying $\displaystyle d/(k,d)=d$, or equivalently $\displaystyle (k,d)=1$; in other words $\displaystyle k$ relatively prime to $\displaystyle d$.

In our problem, the fact that $\displaystyle e$ is a primitive root of $\displaystyle p$ means that $\displaystyle e$ has order $\displaystyle \phi(p)=p-1$ modulo $\displaystyle p$.

So, $\displaystyle e^k$ has order $\displaystyle p-1$ exactly for integers $\displaystyle k$ satisfying $\displaystyle (k,p-1)=1$. It's clear that $\displaystyle p-2$ is one of them since $\displaystyle (p-2,p-1)=1$ and therefore $\displaystyle e^{p-2}$ has order $\displaystyle p-1$ modulo $\displaystyle p$, i.e. $\displaystyle e^{p-2}$ is a primitive root of $\displaystyle p$.