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

• July 11th 2010, 07:16 AM
rualin
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.
• July 11th 2010, 07:34 AM
chiph588@
Quote:

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