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.

If $n$ is not prime, the equation $(x+y)(x-y) = 0$ will have more solutions because of zero divisors. Therefore, fewer than half the numbers in $\Z/n$ wil be squares. For example, there are only 11 nonzero squares in $\Z/80$ and 191 nonzero squares in $\Z/5040$.

So what's the connection with the Jacobi symbol? If $p$ is a prime and $a\in \Z/p$ is nonzero, then $(a/p) = 1$ if and only if $a$ is a square in $\Z/p$; that is if and only if $a$ is a quadratic residue modulo $p$.

Why is this true? If $x^2 = a$ then $(a/p) = (x/p)(x/p) = 1$. Remember, the function $(-/p)$ is multiplicative because multiplying by $a$ and then by $b$ is just composing the corresponding permutations. So, if $a$ is a square then $(a/p) = 1$.

On the other hand, suppose $(a/p) = 1$. Now, in $\Z/p$ there is a primitive element $g$: that is, $g$ is an element whose powers generate $\Z/p^\times$. Since we have already observed that there are nonzero numbers in $\Z/p$ that are not squares, this implies that $(g/p) = -1$. Write $a = g^k$ for some $k$ so that $(a/p) = (g/p)^k = 1$. This means that $k$ is even, and so $a = (g^{k/2})^2$. Thus $a$ is a square.

Recall that in the previous post we said that if $m$ and $n$ are relatively prime odd numbers then

$$(m/n)(n/m) = (-1)^{(m-1)(n-1)/4}.$$This in particular holds when $m$ and $n$ are distinct odd primes, and so this formula relates whether $p$ is a square modulo $q$ to whether $q$ is a square modulo $p$. This interpretation is what's usually known as Gauss's law of quadratic reciprocity!

For example, is the prime $p=13$ a square modu.lo $q=1018021$? Since $(p-1)(q-1)/4$ is even, the law of quadratic reciprocity tells us that 13 is a square modulo 1018021 if and only if $1018021\equiv 4\pmod{13}$ is a square modulo 13. And it is! Gauss was indeed a cool dude.