Jacobi symbol

From Wikipedia, the free encyclopedia

The Jacobi symbol generalises the Legendre symbol. It is used by mathematicians in the area of number theory and is named after the German mathematician Carl Gustav Jakob Jacobi.

1 Definition
2 Properties of the Jacobi symbol
3 Residue
4 External links

[edit] Definition

The Jacobi symbol $\left(\frac{a}{n}\right)$ uses the prime factorization of the bottom number. It is defined as follows:

Let n > 0 be odd and let $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ be the prime factorization of n.

For any integer a, the Jacobi symbol $\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{\alpha_1}\left(\frac{a}{p_2}\right)^{\alpha_2}\cdots \left(\frac{a}{p_k}\right)^{\alpha_k}$ where the symbols on the right are all Legendre symbols (given that the bottom numbers $p i$ are all prime).

[edit] Properties of the Jacobi symbol

There are a number of useful properties of the Jacobi symbol which can be used to speed up calculations. They include:

If n is prime, the Jacobi symbol is the Legendre symbol.
$\left(\frac{a}{n}\right)\in \{0,1,-1\}$
$\left(\frac{a}{n}\right) = 0$ if $\gcd (a,n) \neq 1$
$\left(\frac{ab}{n}\right) = \Bigg(\frac{a}{n}\Bigg)\left(\frac{b}{n}\right)$
$\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$ Note that this means that $\left(\frac{a}{n^2}\right)$ is 0 or 1 for any a and any n.
If a ≡ b (mod n), then $\Bigg(\frac{a}{n}\Bigg) = \left(\frac{b}{n}\right)$
$\left(\frac{1}{n}\right) = 1$
$\left(\frac{-1}{n}\right) = (-1)^{(n-1)/2} = \left\{\begin{array}{cl} 1 & \textrm{if}\;n \equiv 1 \mod 4\\ -1 &\textrm{if}\;n \equiv 3 \mod 4\end{array}\right.$
${\left(\frac{2}{n}\right) = (-1)^{(n^2-1)/8} = \left\{\begin{array}{cl} 1 & \textrm{if}\;n \equiv 1\;\textrm{ or }\;7 \mod 8\\ -1 &\textrm{if}\;n \equiv 3\;\textrm{ or }\;5\mod 8\end{array}\right.}$
$\left(\frac{m}{n}\right) = \left(\frac{n}{m}\right)(-1)^{(m-1)(n-1)/4}$ if m and n are odd integers.

The last property is known as reciprocity, similar to the law of quadratic reciprocity for Legendre symbols.

[edit] Residue

There are two statements about quadratic residues with respect to the Legendre symbol which cannot be made with the Jacobi symbol.

First, if $\left(\frac{a}{n}\right) = -1$ then a is not a quadratic residue of n because a was not a quadratic residue of some p_k that divides n. However, in the case where $\left(\frac{a}{n}\right) = 1$ we are unable to say that a is a quadratic residue of n. Since the Jacobi symbol is a product of Legendre symbols, there are cases where two Legendre symbols evaluate to −1 and the Jacobi symbol evaluates to 1.

There is a second noticeable missing property from the list above, namely an analogue of Euler's congruence $\left(\frac{a}{n}\right) \equiv a^{(n-1)/2}$ mod n. In fact, that congruence is false at least half the time for Jacobi symbols with a composite denominator, and this is the basis for the Solovay-Strassen probabilistic primality test.