6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.