Legendre, Jacobi, Kronecker Symbols

For an odd prime ${p}$ , the Legendre symbol is defined as the quadratic residue symbol,

$\displaystyle \left(\frac{a}{p}\right)= \begin{cases}1 & \text { if } a \text { is a quadratic residue modulo } p \text { and } a \not \equiv 0 (\bmod p), \\ -1 & \text { if } a \text { is a non-quadratic residue modulo } p \\ 0 & \text { if } a \equiv 0 \mod p\end{cases}$

$\displaystyle \left(\frac{\cdot}{p}\right):(\mathbb{Z} / p \mathbb{Z})^{\times} \rightarrow\{\pm 1\}$

This is a character modulo ${p}$ and is helpful as a “harmonic” in contrast to the Gauss’s notation ${aRp}$ and ${aNp}$ which serve as indicators for being a quadratic residue and non-residue. We also distinguish ${0 \bmod p}$ and rest of the quadratic residues.

Some properties of Legendre symbol:

Euler’s criterion:

$\displaystyle \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \quad(\bmod p)$

Periodicity:

$\displaystyle \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right) , \text{ if } a \equiv b \mod p$

Mutliplicativity:

$\displaystyle \left(\frac{a b}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) .$

Quadratic reciprocity:

For ${p, q}$ distinct odd primes, we have

$\displaystyle \begin{aligned} \left(\frac{q}{p}\right)\left(\frac{p}{q}\right)&=(-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}\\ \left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}&= \begin{cases}1 & \text { if } p \equiv 1~(\bmod 4) \\ -1 & \text { if } p \equiv 3~(\bmod 4)\end{cases} \\ \left(\frac{2}{p}\right)=(-1)^{\frac{p^{2}-1}{8}}&= \begin{cases}1 & \text { if } p \equiv 1 \text { or } 7~(\bmod 8) \\ -1 & \text { if } p \equiv 3 \text { or } 5~(\bmod 8)\end{cases}\\ \end{aligned}$

Expressions in terms of analytic functions:

$\displaystyle \left(\frac{q}{p}\right)=\prod_{n=1}^{\frac{p-1}{2}} \frac{\sin \left(\frac{2 \pi q n}{p}\right)}{\sin \left(\frac{2 \pi n}{p}\right)}=\text{sgn}\left(\prod_{i=1}^{\frac{p-1}{2}} \prod_{k=1}^{\frac{q-1}{2}}\left(\frac{k}{q}-\frac{i}{p}\right)\right)$

Zolotarev’s Lemma:

${\left(\frac{a}{p}\right)}$ is the determinant of the permutation map induced by the multiplication by ${a}$ map on ${\mathbb Z/p\mathbb Z.}$

Gauss Lemma:

${\left(\frac{a}{p}\right)}$ equals the number of residues in ${a, 2a, 3a, \cdots \frac{p-1}{2}a}$ that get mapped to ${\{1, 2, \cdots \frac{p-1}{2} \}}$ .

Legendre symbols are quadratic (real) characters: that is they only take values ${\pm 1}$ on integers coprime to ${p}$ . Also note that the symbol is just defined by odd ${p}$ . For ${p=2}$ , we get a trivial symbol if we define it in terms of squares/quadratic residues because every odd number is a square mod ${2}$ .

Quadratic residues:

What about quadratic residues modulo ${n}$ for ${n}$ not a prime? Let’s say ${n=p^k}$ , how do we decide if a number is square mod ${p^k}$ .

The equation ${X^2-a=0}$ has a solution modulo ${p^k}$ iff only if it has solution mod ${p}$ . To see that we can lift mod ${p}$ to ${p^k}$ , write ${X= b +tp}$ where ${b^2=a \mod p}$ . We get

$\displaystyle X^2-a= b^2+2tbp+p^2 -a = a+ kp +2btp+p^2 -a$

This is zero mod ${p^2}$ iff ${k+2bt=0 \mod p}$ . So if ${p\neq 2}$ , we can always choose such which satisfies this equation and get a solution to ${X^2=a \mod p^2}$ . We can continue doing this and lift the uniquely to ${\mod p^k.}$

What about modulo ${2^k}$ ?

Mod ${2}$ , everything is ${0, 1}$ and hence a square.
Mod ${4}$ , ${0, 1}$ are the only squares. So just one square in ${(\mathbb Z/4)^{\times}}$
Mod ${2^k}$ with ${k\ge 3}$ , there are exactly ${2^{k-3}}$ odd squares that is in ${(\mathbb Z/2^k)^{\times}}$ , so that subgroup of squares is of index ${4}$ and hence cannot be defined by by a quadratic character. This is due to the fact that ${ \left(\mathbb{Z} / 2^{k} \mathbb{Z}\right)^{\times} \cong \mathrm{C}_{2} \times \mathrm{C}_{2^{k-2}}}$ , the group is not cyclic and has two factors.

The even squares should be divisible by ${4}$ and should be of the form ${4k}$ where ${k}$ is a square modulo ${2^{k-2}.}$

Putting all these together and the fact that ${x}$ is square mod ${mn}$ iff if it’s a square mod ${m}$ and ${n}$ for coprime integers ${m}$ and ${n}$ , we get that the subgroup of squares in ${\left(\mathbb Z/N\right)^{\times}}$ is defined by not just one character (it’s kernel) but a list of characters one for each prime.

For odd primes powers ${p^k}$ the character is the Legendre symbol ${\left(\frac{q}{p}\right)}$ ,

for ${n=2}$ , the character is trivial,

for ${n=4}$ , the character is a quadratic character detecting ${1 \mod 4}$ ,

for ${n=2^k, k \ge 3}$ , there are 4 quartics character defining a subgroup of index ${4}$ . For instance we have to detect ${1 \mod 8}$ for ${n=3}$ .

To repeat the character defining the squares in ${\left(\mathbb Z/N\right)^{\times}}$ cannot be defined in terms of a single character or a symbol- like we had in the case of odd primes. We have to use all the characters mentioned above to detect the subgroup. That is

$\displaystyle 1_{\square}(a) = \sum_{ \chi(\square)=1} \chi(a)$

We now extend the lower argument to all odd numbers.

Jacobi Symbol: For an odd positive number ${n}$ , we define the Jacobi symbol ${\left(\frac{a}{n}\right)}$ mutliplicatively in ${n}$ as the product of Legendre symbols

$\displaystyle \left(\frac{a}{n}\right)=\left(\frac{a}{p_{1}}\right)^{k_{1}}\left(\frac{a}{p_{2}}\right)^{k_{2}} \cdots\left(\frac{a}{p_{r}}\right)^{k_{r}}$ where

$\displaystyle n=p_1^{k_1}p_2^{k_2} \cdot p_{r}^{k_r}$

This is an extension of Legendre symbol and in fact equals the sign of the permutation of multiplication by ${a}$ on ${\mathbb Z/n\mathbb Z.}$

So this also non-zero values ${\pm1}$ precisely on ${ \left(\mathbb Z/n\right)^{\times}}$ , that is

${\left(\frac{a}{n}\right)= \begin{cases}0 & \text { if } (a, n) \neq 1 \\ \pm 1 & \text { if }(a, n)=1\end{cases}}$

and defines a character mod ${n}$ .

$\displaystyle \left(\frac{\cdot}{n}\right):(\mathbb{Z} / n \mathbb{Z})^{\times} \rightarrow\{\pm 1\}$

Periodicity in ${a}$ with period ${n}$ .

$\displaystyle \text { If } a=b~(\bmod n) \text {, then }\left(\frac{a}{n}\right)=\left(\frac{b}{n}\right)$

Multiplicativity in both arguments:

$\displaystyle \left(\frac{a b}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$

$\displaystyle \left(\frac{a}{m n}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$

Mutiplicativity in ${a}$ follows from the multiplicativity of Legendre symbol and the mutiplicativity on ${n}$ , odd is by defintion.

Quadratic reciprocity:

For ${m, n}$ distinct positive odd integers,

$\displaystyle \left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{\frac{m-1}{2} \cdot \frac{n-1}{2}}= \begin{cases}1 & \text { if } n \equiv 1~(\bmod 4) \text { or } m \equiv 1(\bmod 4) \\ -1 & \text { if } n \equiv m \equiv 3~(\bmod 4)\end{cases}$

$\displaystyle \left(\frac{-1}{n}\right)=(-1)^{\frac{n-1}{2}}= \begin{cases}1 & \text { if } n \equiv 1~(\bmod 4) \\ -1 & \text { if } n \equiv 3~(\bmod 4)\end{cases}$

$\displaystyle \left(\frac{2}{n}\right)=(-1)^{\frac{n^{2}-1}{8}}= \begin{cases}1 & \text { if } n \equiv 1,7~(\bmod 8) \\ -1 & \text { if } n \equiv 3,5~(\bmod 8)\end{cases}$

Squares and quadratic residues:

$\displaystyle \left(\frac{x^2}{n}\right)=1$

follows from the fact that Legendre symbol detects squares.

$\displaystyle \left(\frac{a}{m^2}\right)=1 \text { if } (a, m)=1.$ This is because of the construction/definition we get

$\displaystyle \left(\frac{a}{m^2}\right)=\left(\frac{a}{m}\right)^2=1.$

If ${a}$ is a square mod ${n}$ , then we have ${\left(\frac{a}{n}\right)=1}$ .

If ${\left(\frac{a}{n}\right)=-1}$ , then ${a}$ has to be a non-residue. But it could happen that ${\left(\frac{a}{n}\right)=1}$ and still ${a}$ is a non-residue. For instance it can happen because ${n=p^2}$ , and then the symbol even on non residues is

$\displaystyle \left(\frac{a}{n}\right)=\left(\frac{a}{p}\right)^2=(-1)^2=1$

Or because n is a product of primes say ${pq}$ and ${a}$ is a non-residue modulo both ${p}$ and ${q}$ , so .

$\displaystyle \left(\frac{a}{pq}\right)=\left(\frac{a}{p}\right) \left(\frac{a}{q}\right)=(-1)(-1)=1.$

The upper argument ${a}$ can be any integer, but we have restricted the lower argument ${n}$ to be an odd positive number. What should we do for ${n}$ negative or even?

We extend further.

Kronecker Symbol:

${\left(\frac{a}{2}\right)}$ is defined as the quadratic character mod ${8}$ given by

$\displaystyle \left(\frac{a}{2}\right)= \begin{cases}0 & \text { if } a \text { is even, } \\ 1 & \text { if } a \equiv \pm 1~(\bmod 8) \\ -1 & \text { if } a \equiv \pm 3~(\bmod 8)\end{cases}.$

${\left(\frac{a}{-1}\right)}$ is the sign symbol, a character on ${\mathbb R^{*}/\mathbb R_{+}^{*}}$ .

$\displaystyle \left(\frac{a}{-1}\right)= \begin{cases}-1 & \text { if } a<0 \\ 1 & \text { if } a \geq 0\end{cases}$

$\displaystyle \left(\frac{a}{1}\right)=1$

Now extend the Jacobi symbol multiplicatively with these extra definitions.

Why did we do this? Let’s say we want the Jacobi symbol ${\left(\frac{a}{\cdot}\right)}$ to be a character, that is in the lower argument. We already have multiplicativity over odd positive integers. Let assume that ${a = 1 \mod 4}$ be a positive integer so that

we have by quadratic reciprocity for a odd positive integer

$\displaystyle \left(\frac{a}{n}\right)= \left(\frac{n}{a}\right)$

${\left(\frac{n}{a}\right)}$ is a character modulo ${a}$ . Extend the definition of ${\left(\frac{a}{\cdot}\right)}$ to all the integers so that it equals ${\left(\frac{n}{a}\right)}$ .

$\displaystyle \left(\frac{a}{2}\right) =\left(\frac{2}{a}\right) =(-1)^{\frac{n^{2}-1}{8}} = \begin{cases}0 & \text { if } a \text { is even, } \\ 1 & \text { if } a \equiv \pm 1~(\bmod 8) \\ -1 & \text { if } a \equiv \pm 3~(\bmod 8)\end{cases}.$

$\displaystyle \left(\frac{a}{1}\right) =\left(\frac{1}{a}\right)=1$

$\displaystyle \left(\frac{a}{-1}\right) =\left(\frac{-1}{a}\right)=1$

This shows the motivation for the defintion of the Kronecker symbols. Note that we only considered the case ${a = 1 \mod 4}$ used it to define the symbol for the general case, because for ${a = 3 \mod 4}$ , we ${\left(\frac{a}{n}\right)= (-1)^{n-1/2}\left(\frac{n}{a}\right)}$ and ${\left(\frac{a}{n}\right)}$ is not even have a periodic function in ${n}$ . (Also extension to ${2}$ from this formula doesn’t make sense!)

We again see that the values again are non-zero only for ${ \left(\mathbb Z/n\right)^{\times}}$ .

Now the multiplicativity in ${a}$ is lost! For instance consider the case ${n=-1, a=0, b=-1}$ . But except for these choices we have

$\displaystyle \left(\frac{a b}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$

Multiplicativity in ${n}$ .

It is multiplicative in ${n}$ if we avoid the value ${0}$ in the lower argument.

$\displaystyle \left(\frac{a}{m n}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$

Periodicity in ${a}$ : Assume ${n>0}$ . Because at ${2}$ the character ${\left(\frac{a}{2}\right)}$ is defined ${\bmod ~8}$ , the period of ${\left(\frac{a}{2}\right)}$ is ${4n}$ instead of ${n}$ sometimes-for instance when ${n}$ is divisible by ${2}$ exactly once. Note that if ${2}$ divides even number of times, then the symbol has to be trivial- we multiply ${\left(\frac{a}{2}\right)}$ even number of times.

So if ${n>0}$ , ${ \left(\frac{a}{n}\right)}$ is a real character of modulus

$\displaystyle q=\begin{cases}4 n, & n \equiv 2(\bmod 4) \\ n, & \text { otherwise. }\end{cases}$

If ${n<0}$ , ${\left(\frac{\cdot}{n}\right)}$ needed not be periodic, for instance take ${n=-1}$ .

But ${q}$ might not be the conductor and there could be a much smaller period. For instance Take ${n=16}$ , ${\left(\frac{a}{16}\right)=1}$ for every odd ${a}$ . Hence it’s a trivial character with conductor ${1}$ .

These list of characters ${ \left(\frac{\cdot}{n}\right)}$ do not exhaust all the real characters. ${\left(\frac{-4}{\cdot }\right)}$ as we will see later is a character of modulus ${4}$ , but cannot be represented as ${ \left(\frac{\cdot}{n}\right)}$ for any ${n}$ .

Periodicity in ${n}$ :

We have the following periodicity

$\displaystyle \left(\frac{a}{m}\right)=\left(\frac{a}{n}\right) \text { whenever } m \equiv n \bmod \begin{cases}4|a|, & a \equiv 2(\bmod 4), \\ |a| & \text { otherwise. }\end{cases}$

except for the cases ${a=0}$ and ${a= 3 ~\bmod 4.}$

Thus if ${a \not \equiv 3 ~(\bmod ~4)}$ and ${a \neq 0}$ , ${\left(\frac{a}{n}\right)}$ is a real character of modulus

$\displaystyle q=\begin{cases}4|a|, & a \equiv 2(\bmod 4), \\ |a|, & \text { otherwise. }\end{cases}$

But if ${a=3 \mod 4}$ , ${\left(\frac{a}{n}\right)}$ need not be periodic! For example take ${\left(\frac{3}{n}\right)}$ .

Squares and residues: Just like Jacobi symbol, Kronecker doesn’t give information about whether ${a}$ is a square mod ${n.}$ .

Like before ${\left(\frac{a}{n}\right)=1}$ doesn’t imply that ${a}$ is a residue. But if we include ${2}$ , that is when ${n}$ is even, the values of ${\left(\frac{a}{n}\right)}$ are completely independent of whether ${a}$ is residue or non-residue. Like take ${a=3}$ which is a square mod ${2}$ , but ${\left(\frac{3}{2}\right)=-1}$ . So we don’t have ${\left(\frac{x^2}{n}\right)=1}$ anymore. Also ${\left(\frac{a}{n}\right)=-1}$ doesn’t imply that ${a}$ has to be a non-residue. (which is a true implication for odd ${n}$ )

Quadratic reciprocity:

$\displaystyle \left(\frac{2}{n}\right)= \begin{cases} (-1)^{\frac{n^{2}-1}{8}} & \text { if } 2\nmid n \\ 0 & \text { if } 2\mid n\end{cases}$

If ${n=2^{e}n'}$ with ${n'}$ odd

$\displaystyle \left(\frac{-1}{n}\right)=(-1)^{\frac{n'-1}{2}}$

Similarly if ${m=2^{f}m'}$ with ${m'}$ odd

$\displaystyle \left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=\pm(-1)^{\frac{m^{\prime}-1}{2}}(-1)^\frac{n^{\prime}-1}{2}$

where we take the ${-}$ sign iff both ${m}$ and ${n}$ are negative

Primtive quadratic characters: If ${D}$ is a fundamental discriminant, that is ${D}$ is given by

$\displaystyle D= \begin{cases}d & \text { if } d \equiv 1~(\bmod ~4) \\ 4 d & \text { if } d \equiv 2 \text { or } 3~(\bmod ~4)\end{cases}$

where ${d}$ is a squarefree integer, that is ${D}$ is the discriminant of the field ${\mathbb Q(\sqrt d)}$ , then

$\displaystyle \chi_{D} = \left(\frac{D}{n}\right)$

is a character of conductor ${|D|}$ , and is primitive. That is it’s period is exactly ${|D|}$ and we can cannot induce ${\chi}$ from a character of smaller modulus.

In fact ${\chi_D}$ decides the splitting behaviour in the field.

$\displaystyle \chi(p)= \begin{cases}0, & (p) \text { is ramified, } \\ 1, & (p) \text { splits } \\ -1, & (p) \text { is inert. }\end{cases}$

Every primitive quadratic character is of this form!

We need ${D}$ to be a fundamental discriminant. If it’s not the ${\left(\frac{D}{n}\right)}$ needn’t even be a character. So sometimes it could be a character and not primitive, sometimes it’s not even a character and only when ${D}$ is a fundamental discriminant we have a primitive character. For $D=3$ , it’s not periodic and hence not a character, for $D=-4$ it’s a primitive character and or $D=4$ we get the trivial character (so not primitive mod $|D|$ ).