Thread: 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, . 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.

Originally Posted by rualin

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, . 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.

by Euler's Criterion.

Now use this post (replacing with ) to show all other proper divisors of have .