In the last post, we examined the Jacobi symbol: for two relatively prime integers $m$ and $n$, we defined the Jacobi symbol $(m/n)$ to be the sign of the permutation $x\mapsto mx$ on the ring $\Z/n$.
It turns out that the Jacobi symbol plays a part in the theory of quadratic residues. For a number $n$, we say that an element $a\in \Z/n$ is a quadratic residue if it's a square in $\Z/n$.
When $n = p$ is a prime number, the question of which integers are quadratic residues goes back to the ancient days of Gauss. He realized that for an odd prime $p$, half the numbers in the list $1,2,\dots, p-1$ are quadratic residues, and the other half are not quadratic residues (a.k.a. quadratic nonresidues). Indeed, if $x^2 = y^2$ in the field $\Z/p$, then $(x+y)(x-y) = 0$. Therefore, if $x\not= y$, we must have $x=-y$. So it is clear that amongst the numbers $1^2,2^2,\dots,(p-1)^2$, there are exactly $(p-1)/2$ distinct numbers.
This guy means business!
More »
