Results 1 to 2 of 2

Math Help - p=2^k+1 and (a/p)=-1 imply a is primitive modulo p

  1. #1
    Member
    Joined
    Jul 2007
    Posts
    90

    p=2^k+1 and (a/p)=-1 imply a is primitive modulo p

    Hello! I've been working on this little proof but I never got it. I'm pretty sure it's real simple but I'm having trouble and I'd appreciate it if someone could help me.

    If p=2^k+1 is prime and (a/p)=-1 modulo p, show that a is a primitive root modulo p.

    By Lagrange's Theorem, a^{2^k}\equiv 1 \bmod{2^k+1} . Therefore, the order of a is a power of 2 and at most 2^k. I know I need to proof that if the order of a is 2^n, where n<k, then we get a contradiction, since for a to be primitive mod p, we need it's order to be 2^k. However, I don't know how to proceed after this nor where to use the fact that a is a quadratic resude mod p.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by rualin View Post
    Hello! I've been working on this little proof but I never got it. I'm pretty sure it's real simple but I'm having trouble and I'd appreciate it if someone could help me.

    If p=2^k+1 is prime and (a/p)=-1 modulo p, show that a is a primitive root modulo p.

    By Lagrange's Theorem, a^{2^k}\equiv 1 \bmod{2^k+1} . Therefore, the order of a is a power of 2 and at most 2^k. I know I need to proof that if the order of a is 2^n, where n<k, then we get a contradiction, since for a to be primitive mod p, we need it's order to be 2^k. However, I don't know how to proceed after this nor where to use the fact that a is a quadratic resude mod p.
     \left(\frac ap\right)=-1\implies a^{2^{k-1}}\equiv-1\bmod{p} by Euler's Criterion.

    Now use this post (replacing  3 with  a ) to show all other proper divisors  d of  \varphi(p) have  a^d\not\equiv1\bmod{p} .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. primitive root modulo p
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 23rd 2010, 02:42 AM
  2. Prove that 2 is a primitive root modulo p.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 21st 2010, 05:51 PM
  3. Primitive roots modulo 101
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 10th 2009, 07:25 PM
  4. powers modulo p and primitive root question
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 16th 2008, 10:57 AM
  5. Primitive root modulo 121
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 8th 2008, 07:09 AM

Search Tags


/mathhelpforum @mathhelpforum