# primitive roots

• Oct 1st 2011, 07:34 PM
alexgeek101
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.
• Oct 1st 2011, 09:09 PM
melese
Re: primitive roots
Quote:

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.
• Oct 1st 2011, 09:36 PM
alexgeek101
Re: primitive roots
Quote:

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?
• Oct 4th 2011, 03: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, 05: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, 10:50 AM
melese
Re: primitive roots
Quote:

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$.