Results 1 to 2 of 2

Math Help - primitive root and quadratic residue

  1. #1
    Junior Member
    Joined
    Feb 2006
    From
    Canada
    Posts
    45

    Exclamation primitive root and quadratic residue

    Prove that a primitive root r modulo n cannot be a quadratic residue.

    I've no idea how to prove it, pls help, thx very much!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    I think the proof would be a lot easier if you n was an odd prime. Anyway, if r is a primitive root then,
    \{r,r^2,...,r^{n-1} \}
    Contains all the elements of n
    But since r is a quadradic residue.
    That means r^k is a quadradic residue.
    Then all numbers 1\leq j\leq n are quadradic residues of n, which is surly not possible unless n=1,2.

    Note: By odd primes the proof is extremely simple if r is a quadradic residue then,
    r^{\frac{p-1}{2}}\equiv 1(\mbox{ mod }p)
    But that is not possible because the order of r is p-1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: February 27th 2011, 05:59 PM
  2. Primitive root of 2^n + 1
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 9th 2010, 12:34 PM
  3. Primitive roots & Reduced residue system
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: March 4th 2010, 05:51 AM
  4. primitive root
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 10th 2009, 05:53 PM
  5. Primitive root in quadratic field
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: April 30th 2008, 01:39 PM

Search Tags


/mathhelpforum @mathhelpforum