Prove that $q=4^n+1$ is prime iff $3^{\frac{(q-1)}2}=-1\bmod q$ 
Let $q=4^n+1$ where $n$ is a positive integer. Prove that $q$ is a prime if and only if $3^{\frac{(q-1)}2}=-1\bmod q$. (Niven 3.2.15)

I am not getting any clue to solve the problem. Help Needed.
Thank You.
 A: Suppose q is prime. 
$ \Big( \frac{3}{q} \Big) = \Big( \frac{q}{3} \Big)$ using quadratic reciprocity law as $gcd \hspace{1mm}(3, q) = 1$.
Then, $ \Big( \frac{q}{3} \Big) = \Big( \frac{4^n + 1 \hspace{2mm} mod \hspace{1mm}3}{3} \Big) = \Big( \frac{2}{3} \Big) = -1  $.
Now by Euler's Criterion, $\Big( \frac{3}{q} \Big) \equiv  3 ^{\frac{q-1}{2}} (mod \hspace{1mm} q) $. 
Conversely, assuming $ 3 ^{\frac{q-1}{2}} \equiv -1 (mod \hspace{1mm} q)$.
Squaring on both the sides, $ 3 ^{q-1} \equiv 1 (mod \hspace{1mm} q)$. 
This implies, $ord_{q}(3)  \mid (q-1) $ where $q-1 = 2^{2n}$. However, $ord_{q}(3)  \nmid \frac{q-1}{2}$. So, $ord_{q}(3) = 2^{2n} = q-1$.
By Euler's theorem, $3 ^ {\phi(q)} \equiv 1  (mod \hspace{1mm} q) $ and so $(q-1) \mid \phi(q)$.  For any $q$, $\phi(q) \leq (q-1).$
So, $\phi(q) = (q-1)$ which is possible only when $q$ is prime.
A: As Geoff Robinson suggested in the comments, one direction is not hard. Let me show the other direction.
Assume $3^{2^n} \equiv -1 \pmod{q}$. We want to show that $q=4^n +1$ is a prime. Suppose it is not. Take the smallest prime divisor of $q$ and call it $p$. We have
$$
3^{2^n} \equiv -1 \pmod{p}.
$$
This implies
$$
3^{2^{n+1}} \equiv 1  \quad \mbox{and} \quad 3^{p-1} \equiv 1 \pmod{p}. 
$$
If $d$ is the degree of $3$ in$\pmod{p}$, we have
$$
d \ | \ 2^{n+1} \quad \mbox{and} \quad d \ | \ p-1.
$$
Since $3^{2^n} \equiv -1 \pmod{p}$, $d$ can't be a divisor of $2^n$. Therefore
$$
d=2^{n+1} \quad \mbox{and} \quad 2^{n+1} \ | \ p-1
$$
So, for some $k\in \mathbb{N}^+$ we can write
$$
p = k2^{n+1}+1
$$
Now, remember $p$ was the smallest prime divisor of $q$. Since $q$ is not a prime number it should have at least another divisor greater than or equal to $p$. But, 
$$
q=4^n +1 \  < \ (2^{n+1} + 1)^2 \ < \ p^2
$$
Contradiction.
