# How do you prove a Quadratic Residue?

Prove or disprove: 28 is a quadratic residue (mod 65).

-

Recall that if $a$ and $m$ are relatively prime, then $a$ is a QR of $m$ if the congruence $$x^2\equiv a \pmod{m}$$ has a solution.

If the congruence $x^2\equiv 28\pmod{65}$ has a solution, then so do the congruences $x^2\equiv 28\pmod{5}$ and $x^2\equiv 28\pmod{13}$. Indeed the converse also holds, by the Chinese Remainder Theorem.

Let's check whether the congruence $x^2\equiv 28\pmod{5}$ has a solution. So we are asking whether $x^2\equiv 3\pmod{5}$ has a solution. Try everything, there are very few things to try. Modulo $5$, $1^2\equiv 1$, $2^2\equiv 4$, $3^2\equiv 4$, $4^2\equiv 1$. No solution to $x^2\equiv 3\pmod{5}$, and therefore no solution to $x^2\equiv 28\pmod{65}$!

Remark: For substantially bigger moduli, we need theory, lots of it. There are good algorithms for determining whether $a$ is a QR modulo a prime.

-

The brute force method is to square every number from $1$ to $65$ and see whether you ever get $28$ as the residue. There are much better methods, but they depend on how much you know about quadratic residues, and you haven't told us.

-