Let $\displaystyle q = 4^n + 1 \mbox{ where } n$ is a positive integer. Prove that $\displaystyle q$ is a prime if and only if $\displaystyle 3^{\frac{q-1}{2}} \equiv -1 \mbox{ (mod q)}$.
I have no clue on how to start.
Let $\displaystyle q = 4^n + 1 \mbox{ where } n$ is a positive integer. Prove that $\displaystyle q$ is a prime if and only if $\displaystyle 3^{\frac{q-1}{2}} \equiv -1 \mbox{ (mod q)}$.
I have no clue on how to start.
$\displaystyle (3,q)=1 $ since $\displaystyle q \equiv 1 \not\equiv 3 \mod{4} $.
Therefore for a fixed $\displaystyle x $, there exists a unique $\displaystyle y $ such that $\displaystyle xy \equiv 3 \mod{q} $.
Hence if we partition $\displaystyle \{1,...,q-1\} $ into $\displaystyle \{c,d\} $ such that $\displaystyle cd \equiv 3 \mod{q} $, we get $\displaystyle (q-1)! \equiv 3^{\frac{q-1}{2}} \mod{q} $.
By Wilson's Theorem we have $\displaystyle (q-1)! \equiv -1 \mod{q} \Longleftrightarrow q $ is prime.
I'm not exactly sure this is right so if someone wants to confirm this, that would be great.
your idea is good but the above conclusion is unfortunately not true at least when $\displaystyle q$ is not prime (choose $\displaystyle x$ to be any divisor of $\displaystyle q$). you probably meant $\displaystyle 3y \equiv 1 \mod q$ has a unique solution
modulo $\displaystyle q,$ which is correct but not very useful here.
Well one way is easy. If $\displaystyle q $ is prime then $\displaystyle \left(\frac{3}{q}\right) \equiv 3^{\frac{q-1}{2}} \mod{q} $ by Euler's Criterion.
$\displaystyle \left(\frac{3}{q}\right) = \left(\frac{3}{4^n+1}\right) = \left(\frac{4^n+1}{3}\right) = \left(\frac{1^n+1}{3}\right) = \left(\frac{2}{3}\right) = -1 $.