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 »

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

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 »

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

If $m$ and $n$ are relatively prime integers, the Jacobi symbol $(m/n)$ is defined as the sign of the permutation $x\mapsto mx$ on the set $\Z/n$. Let's give a simple example: $(7/5)$. The permutation on $\{1,2,3,4\}$ is given by $(1 2 4 3) = (1 2)(2 4)(4 3)$ which has an odd number of transpositions. Therefore, $(7/5) = -1$.

Note that as in this example, it is sufficient to compute the sign of the permutation on $\Z/n – \{0\}$, since multiplication always leaves zero fixed.

But what if we wanted to compute something like $(3/412871)$? These numbers aren't so big, so a computer could do it directly. However, there is a better way to do the computation of the Jacobi symbol $(m/n)$ if one of $m$ or $n$ is much larger than the other one. This method is good for computers too when one of the numbers is so large, that a direct computation even by a fast computer would be hopeless.
More »