Quadratic residues

From AoPSWiki

Let $a$ and $m$ be integers, with $m\neq 0$ . We say that $a$ is a quadratic residue modulo $m$ if there is some integer $n$ so that $n^2-a$ is divisible by $m$ .

Legendre Symbol

Determining whether $a$ is a quadratic residue modulo $m$ is easiest if $m=p$ is a prime. In this case we write $\left(\frac{a}{p}\right)=\begin{cases} 0 & \mathrm{if }\ p\mid a, \\ 1 & \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \...$

The symbol $\left(\frac{a}{p}\right)$ is called the Legendre symbol.

Quadratic Reciprocity

Let $p$ and $q$ be distinct odd primes. Then $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$ . This is known as the Quadratic Reciprocity Theorem. Whereas the above are properties of the Legendre symbol, they still hold for any odd coprime integers $p$ and $q$ when using the Jacobi symbol defined below.

Additional properties

Also, we have for any odd prime $p$ the following rules:

Multiplicaticity: $\left(\frac{a}{p}\right) \left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)$

Euler's criterion: $\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p$

First supplementary rule: $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$ , so $\left(\frac{-1}{p}\right)=1 \iff p \equiv 1 \mod 4$

Second supplementary rule: $\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$ , so $\left(\frac{2}{p}\right)=1 \iff p \equiv \pm 1 \mod 8$

It's also useful not to forget that the symbols are only properties $\mod p$ , so $a \equiv b \mod p \implies \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$

Jacobi Symbol

Now suppose that $m$ is odd, and let $m=p_1^{e_1}\cdots p_n^{e_n}$ . Then we write $\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)^{e_1}\cdots\left(\frac{a}{p_n}\right)^{e_n}$ . This symbol is called the Jacobi symbol. All properties mentioned above except Euler's criterion are also true for Jacobi symbols with odd (positive) integers $p$ and $q$ instead.

Note that $\left(\frac{a}{m}\right)=1$ does not mean that $a$ is a quadratic residue $\mod m$ (but is necassary for it to be).

Calculation and examples

With the rules and properties already mentioned, it's eays to calculate Jacobi symbols. Since they are for primes $p$ identical to the Legendre symbol, this gives a fast way to decide if an integer is a quadratic residue $\mod p$ or not.

Example:

$\left(\frac{12345}{13337}\right) =$

$=\left(\frac{13337}{12345}\right) = \left(\frac{992}{12345}\right) = \left(\frac{2^5}{12345}\right)\left(\frac{31}{12345}\rig...$

$= 1^5 \left(\frac{7}{31}\right) = -\left(\frac{31}{7}\right) = -\left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\...$

$=1$

Thus we know that $12345$ is a quadratic residue modulo the prime $13337$ . Indeed: $2425^2 \equiv 12345 \mod 13337$

In a more general manner, one, for example, also gets:

$\left(\frac{-2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{2}{p}\right) = (-1)^{\frac{(p-2)^2-1}{8}}$ , so $\left(\frac{-2}{p}\right)=1 \iff p \equiv 1,3 \mod 8$ .

$\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} \left(\frac{p}{3}\right)$ , so $\left(\frac{3}{p}\right)=1 \iff p \equiv \pm 1 \mod 12$ .

$\left(\frac{-3}{p}\right) = \left(\frac{p}{3}\right)$ , so $\left(\frac{-3}{p}\right)=1 \iff p \equiv 1 \mod 3$ .

The general case

In general, to determine whether $a$ is a quadratic residue modulo $n$ , one has to check whether $a$ is a quadratic residue modulo every odd prime $p$ dividing $n$ . This is enough if $n$ is odd or $n=2m$ and $m$ is odd. If $n=4m$ and $m$ is odd, one also has to check that $a\equiv 0\mathrm{\ or\ }1\mod 4$ . Finally, if $n$ is divisible by $8$ , one also has to check that $a\equiv 0,1,\mathrm{\ or\ }4\mod 8$ .

Personal tools

Navigation

Search

Toolbox