Jacobi Symbol
The Jacobi symbol is a generalization of the Legendre symbol, which can be used to simplify computations involving quadratic residues. It shares many of the properties of the Legendre symbol, and can be used to state and prove an extended version of the law of quadratic reciprocity.
Contents
Definition
Recall that the Legendre symbol is defined for an integer and an odd prime The Jacobi symbol is defined for any odd positive integer as follows:
If where the are primes, then
Properties
The Legendre symbol measures whether is a square mod Unfortunately, the Jacobi symbol does not retain this property:
If and is a square mod where is an odd positive integer, then but the converse is not true.
To see this, note that if is a square mod then it is a square mod for all primes dividing so the Legendre symbols are all equal to so the Jacobi symbol equals by definition. But if is not a square mod for some the Jacobi symbol might still be
- but is not a square mod it is not even a square mod
- but is not a square mod it is not a square mod or
On the other hand, many of the other properties of the Legendre symbol do extend to the Jacobi symbol.
Let be positive odd integers and let be integers.
- If , then .
- ; that is, the function is a completely multiplicative function.
- , so it is if and only if mod .
- so it is if and only if mod .
- (Extension of the law of quadratic reciprocity:) If and are coprime positive odd integers,
(1), (2), and (3) are immediate from the definition (and the corresponding properties of the Legendre symbol). The other three follow from the corresponding properties for the Legendre symbol, and then an induction on To illustrate, here is a proof of (4) the proofs of (5) and (6) are similar:
Induct on When (base case), the result holds trivially. Now suppose the result holds for all positive odd integers less than If is prime, the result is true by the corresponding theorem for the Legendre symbol. If is composite, write where and are positive odd integers less than Then by the inductive hypothesis and property (2),
and now the result follows from the following lemma:
If and are odd,
The proof of the lemma reduces to four cases based on whether and are or mod and the statement can be verified easily in all four cases.
The lemma implies that
so the result holds for as well. Hence it holds for all by strong induction.
Computations using the Jacobi Symbol
The properties of the Jacobi symbol not only simplify computations of Jacobi symbols but those of Legendre symbols as well.
Is 1235 a quadratic residue mod the prime number 10007?
Use extended quadratic reciprocity repeatedly:
so the answer is no. Note that without using properties of the Jacobi symbol, the beginning part of the problem would have taken longer; if the top of the symbol was composite (as 1235 was), we would have had to factor it as a product of primes and then flipped each individual Legendre symbol using quadratic reciprocity. The properties of the Jacobi symbol allow us to avoid any factoring (except for factoring out powers of 2, which is always necessary).
Applications to Primality Testing
The Legendre symbol satisfies Euler's criterion:
for coprime to This is no longer true in general for the Jacobi symbol.
We have but
So this gives a criterion for primality: if there is an integer coprime to such that , then cannot be prime.
It is not hard to show that if is composite, then at least half the positive less than that are coprime to satisfy this condition. Choosing random values of times leads to a probability of that none of the random values are witnesses to the compositeness of in this way. This probabilistic primality test is called the Solovay-Strassen primality test, and is quite efficient in practice. One interesting feature of the test is that it can be used to prove that numbers are composite without explicitly determining a nontrivial factor.
Show that is composite using the Solovay-Strassen primality test.
Suppose we randomly choose It turns out that and This random choice leaves the outcome of the test inconclusive. Next suppose we randomly choose In this case, but so this immediately shows that is composite.