# Thread: A proof with primes and quadratic residues

1. ## A proof with primes and quadratic residues

Let $q = 4^n + 1 \mbox{ where } n$ is a positive integer. Prove that $q$ is a prime if and only if $3^{\frac{q-1}{2}} \equiv -1 \mbox{ (mod q)}$.

I have no clue on how to start.

2. $(3,q)=1$ since $q \equiv 1 \not\equiv 3 \mod{4}$.

Therefore for a fixed $x$, there exists a unique $y$ such that $xy \equiv 3 \mod{q}$.

Hence if we partition $\{1,...,q-1\}$ into $\{c,d\}$ such that $cd \equiv 3 \mod{q}$, we get $(q-1)! \equiv 3^{\frac{q-1}{2}} \mod{q}$.

By Wilson's Theorem we have $(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 $x$, there exists a unique $y$ such that $xy \equiv 3 \mod{q}$.
your idea is good but the above conclusion is unfortunately not true at least when $q$ is not prime (choose $x$ to be any divisor of $q$). you probably meant $3y \equiv 1 \mod q$ has a unique solution

modulo $q,$ which is correct but not very useful here.

4. Well one way is easy. If $q$ is prime then $\left(\frac{3}{q}\right) \equiv 3^{\frac{q-1}{2}} \mod{q}$ by Euler's Criterion.

$\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
$\left(\frac{4^n+1}{3}\right) = \left(\frac{1^n+1}{3}\right)$ ?