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$.
