Posted by Jason Polak on 27. July 2018 · Write a comment · Categories: number-theory · Tags: , , ,

This is the final post on the Jacobi symbol. Recall that the Jacobi symbol $(m/n)$ for relatively prime integers $m$ and $n$ is defined to be the sign of the permutation $x\mapsto mx$ on the ring $\Z/n$. In the introductory post we saw this definition, some examples, and basic properties for calculation purposes.

In Part 2 we saw that for an odd prime $p$ and an integer $a$ that is relatively prime to $p$, the Jacobi symbol $(a/p) = 1$ if and only if $a$ is a square modulo $p$ (a "quadratic residue"). The basic properties of the Jacobi symbol then give the classic law of quadratic reciprocity.

Now, we're going to see one last application of the Jacobi symbol: primality testing in what's called the Solovay-Strassen primality test. How does it work? It starts with an observation we saw before: in the ring $\Z/p$, there exists a primitive element $g\in \Z/p$. It is an element that generates the multiplicative cyclic group $\Z/p^\times\cong \Z/(p-1)$.
More »