Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$.

share|cite|improve this answer
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
This is as nice and simple a quasi-solution (i.e., several hints for the OP to proof/solve) as one could expect.+1 – DonAntonio Jul 7 '13 at 22:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.