Prove that $q=4^n+1$ is prime iff $3^{\frac{(q-1)}2}=-1\bmod q$

Question

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.

Answer 1

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.