Results 1 to 2 of 2

Math Help - Primitive roots

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    25

    Primitive roots

    Question:
    Prove: If p and q=2p+1 are both odd primes, then -4 is a primitive root of q.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Note that when q=2p+1 then \phi(q-1)=p-1=\tfrac{{q - 1}}<br />
{2} - 1 (1) . There are \phi(q-1) primitive roots and \tfrac{{q - 1}}<br />
{2} non-quadratic residues, and each primitive root is a non-quadratic residue (because otherwise it'd only generate quadratic residues). Thus (1) means that all non-quadratic residues but 1 of them, are primitive roots.

    We can show that the only non-quadratic residue that is not a primitive root is -1. Note that q \equiv 3\left( {\bmod .4} \right) (consider p=1,3(mod.4) ), thus -1 is a non-quadratic residue mod. q. But {\left( { - 1} \right)^2} \equiv 1\left( {\bmod .q} \right) thus -1 is not a primitive root.

    Now just check that - 4 is a non-quadratic residue module q (easy because 4 is a square and -1 is a non-quadratic residue), and then check that  - 4 \not\equiv  - 1\left( {\bmod .q} \right) and we are done.
    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, 06:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 17th 2008, 09:09 PM
  3. Primitive roots
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 15th 2007, 10:19 AM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 21st 2006, 08:05 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2006, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum