1. A proof with primes and quadratic residues

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.

2. $\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.

3. Originally Posted by chiph588@

Therefore for a fixed $\displaystyle x$, there exists a unique $\displaystyle y$ such that $\displaystyle xy \equiv 3 \mod{q}$.
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.

4. 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$.

5. Thank you so much. By the way, how did you get from
$\displaystyle \left(\frac{4^n+1}{3}\right) = \left(\frac{1^n+1}{3}\right)$ ?