# Application of Legendre, Jacobi and Kronecker Symbols

Legendre, Jacobi and Kronecker Symbols are powerful multiplicative functions in computational number theory. They are useful mathematical tools, essentially for primality testing and integer factorization; these in turn are important in cryptography.

Yet, it would be nice to have a discussion here on their use in classical number theory and math problems. In other words, what kind of problems can they be effectively applied to? Or simply, when/where to use them?

Definitions

For any integer $a$ and any positive odd integer $n$ the Jacobi symbol is defined as the product of the Legendre symbols corresponding to the prime factors of $n$:

$\left(\tfrac{a}{p}\right)$ represents the Legendre symbol, defined for all integers $a$ and all odd primes $p$ by $$\Bigg(\frac{a}{n}\Bigg) = \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}\mbox{ where } n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}.$$ $$\left(\frac{a}{p}\right) = \left\{ \begin{array}{rl} 0 & \text{if } a \equiv 0 \pmod{p},\\ 1 & \text{if } a \not\equiv 0\pmod{p} \text{ and for some integer } x:\;a\equiv x^2\pmod{p},\\ -1 & \text{if } a \not\equiv 0\pmod{p} \text{ and there is no such } x. \end{array} \right.$$ Following the normal convention for the empty product, $\left(\tfrac{a}{1}\right) = 1$. The Legendre and Jacobi symbols are indistinguishable exactly when the lower argument is an odd prime, in which case they have the same value.

The Kronecker symbol, written as $\left(\frac an\right)$ or $(a|n)$, is an extension of the Jacobi symbol to all integers.

Let $n$ be a non-zero integer, with prime factorization

$$n=u \cdot p_1^{e_1} \cdots p_k^{e_k},$$

where $u$ is a unit (i.e., $u=\pm1$), and the $p_i$ are primes. Let $a$ be an integer. The Kronecker symbol $(a|n)$ is defined by

$$\left(\frac{a}{n}\right) = \left(\frac{a}{u}\right) \prod_{i=1}^k \left(\frac{a}{p_i}\right)^{e_i}.$$

For odd number $p_i$, the number $(a|p_i)$ is simply the usual Legendre symbol. This leaves the case when $p_i=2$. We define $(a|2)$ by

$$\left(\frac{a}{2}\right) = \begin{cases} 0 & \mbox{if }a\mbox{ is even,} \\ 1 & \mbox{if } a \equiv \pm1 \pmod{8}, \\ -1 & \mbox{if } a \equiv \pm3 \pmod{8}. \end{cases}$$

Since it extends the Jacobi symbol, the quantity $(a|u)$ is simply $1$ when $u=1$. When $u=-1$, we define it by

$$\left(\frac{a}{-1}\right) = \begin{cases} -1 & \mbox{if }a < 0, \\ 1 & \mbox{if } a \ge 0. \end{cases}$$

Finally, we put

$$\left(\frac a0\right)=\begin{cases}1&\text{if }a=\pm1,\\0&\text{otherwise.}\end{cases}$$

These extensions suffice to define the Kronecker symbol for all integer values $a,n$.