# How to prove $4^n+1$ is prime number if $3^{\frac{q-1}{2}} \equiv-1 \mod q$?

Let $q=4^n+1$. I need to prove that if $3^{\frac{q-1}{2}} \equiv-1 \mod q$, then $q$ is prime number.

How to prove it? thanks.

-
For a prime divisor $p$ of $q$, consider the order of $3$ in $\mathbb{Z}/(p)$. – Daniel Fischer Jul 7 '13 at 21:11
could you explain? – noot Jul 7 '13 at 21:17
could you write down the steps? – noot Jul 7 '13 at 21:19
What part(s) of my hint did you understand? Do you know what $\mathbb{Z}/(p)$ is, and what the order of an element in a group is? – Daniel Fischer Jul 7 '13 at 21:22
@DanielFischer Do you see why they ask for $4^n+1$? The proof by group order/primitive element works fine for $2^n+1$ as well ... – Hagen von Eitzen Jul 7 '13 at 21:27

The order of $3$ in the multiplicative group $(\mathbb Z/q\mathbb Z)^\times$ is a divisor of $q-1=2^{2n}$ because $3^{q-1}\equiv (-1)^2\equiv 1\pmod q$, but it is not a divisor of $\frac{q-1}{2}=2^{2n-1}$ because $3^{\frac{q-1}{2}}\equiv -1\not\equiv 1\pmod q$. Hence the order of $3$ is exactly $q-1$, especially, $(\mathbb Z/q\mathbb Z)^\times$ has at least (hence exactly) $q-1$ elements, i.e. none of the numbers $1\le k<q$ has a factor in common with $q$.
Well, how do you know that $Z/qZ$ is a multiplicative group at the beginning? If q is not prime, then it is not a group. – noot Jul 7 '13 at 21:30
@noot $(\mathbb{Z}/q\mathbb{Z})^\times$ is the multiplicative group of units in the ring $\mathbb{Z}/q\mathbb{Z}$. – Daniel Fischer Jul 7 '13 at 21:33
$(\mathbb Z/q\mathbb Z)^\times$ is always a multiplicative group, it is the group of units of the ring $\mathbb Z/q\mathbb Z$ and has $\phi(q)$ elements. – Hagen von Eitzen Jul 7 '13 at 21:33