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, $\displaystyle 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.