Results 1 to 6 of 6

Thread: primitive roots

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    11

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Re: primitive roots

    Quote Originally Posted by alexgeek101 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2011
    Posts
    11

    Re: primitive roots

    Quote Originally Posted by melese View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2011
    Posts
    34

    Re: primitive roots

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



    EDIT: Sorry I was wrong. And my computer is playing up!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2011
    Posts
    11

    Re: primitive roots

    Quote Originally Posted by Juneu436 View Post
    EDIT: Sorry I was wrong. And my computer is playing up!
    Well thanks anyway June for taking the time to look at it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Re: primitive roots

    Quote Originally Posted by alexgeek101 View Post
    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$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jul 10th 2011, 05:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Mar 24th 2010, 01:15 PM
  3. primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Feb 24th 2009, 12:27 PM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2008, 09:00 AM
  5. Help With primitive roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Oct 28th 2007, 01:37 PM

Search Tags


/mathhelpforum @mathhelpforum