Results 1 to 6 of 6

Math Help - primitive roots

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    11

    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.
    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 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.
    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 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?
    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 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.
    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: July 10th 2011, 05:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 24th 2010, 01:15 PM
  3. primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 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: October 28th 2007, 01:37 PM

Search Tags


/mathhelpforum @mathhelpforum