# primitive roots

• Oct 1st 2011, 08:34 PM
alexgeek101
primitive roots
Hi, I am having a tough time with this question.

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

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

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

Thank You for any help.
• Oct 1st 2011, 10:09 PM
melese
Re: primitive roots
Quote:

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

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

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

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

Thank You for any help.

The primitive roots $e$ and $g$ are quadratic nonresidue of $p$; using the Legnedre Sybmol this means $(e/p)=(f/p)=-1$. Then $(e^g/p)=(e/p)\cdots(e/p)=(-1)^g$ and similarly $(f^h/p)=(-1)^h$.
But $e^g\equiv f^h\pmod p$ and therefore $(-1)^g=(e^g/p)=(f^h/p)=(-1)^h$, from which we see that $g$ and $h$ have the same parity.
• Oct 1st 2011, 10:36 PM
alexgeek101
Re: primitive roots
Quote:

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

At the start you mean 'primitive roots $e$ and $f$ ....'
So since $(-1)^g=(-1)^h$, this implies that $g \equiv h (mod \ 2)$.
Thanks heaps, that makes total sense.

Any thoughts on the second part of the question?
• Oct 4th 2011, 04:53 AM
Juneu436
Re: primitive roots
Quote:

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

EDIT: Sorry I was wrong. And my computer is playing up!
• Oct 4th 2011, 06:00 AM
alexgeek101
Re: primitive roots
Quote:

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.
• Oct 4th 2011, 11:50 AM
melese
Re: primitive roots
Quote:

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

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

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

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

Thank You for any help.

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

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

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

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