Difference between revisions of "Quadratic residues"

Revision as of 06:33, 27 June 2006

Let $a$ and $m$ be integers, with $m\neq 0$ . We say that $a$ is a quadratic residue modulo $m$ if there is some number $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\ \mathrm{\ is\ a\ quadratic\ residue\ modulo\ }\ p, \\ -1 & \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ nonresidue\ modulo\ }\ p. \end{cases}$

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 integers $p$ and $q$ when using the Jacobi symbol defined below.

Additional properties

We have for any odd prime $p$ also 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 usefull 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}\right)=\left(\frac{2}{12345}\right)^5 \left(\frac{12345}{31}\right) = 1^5 \left(\frac{7}{31}\right) = -\left(\frac{31}{7}\right) = -\left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\frac{1}{3}\right)=1$ Thus we know that $12345$ is a quadratic residue modulo the prime $13337$ . Indeed: $2425^2 \equiv 12345 \mod 13337$

@@ Line 10: / Line 10: @@
 Let <math>p</math> and <math>q</math> be distinct odd primes. Then <math>\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}</math>. This is known as the [[Quadratic Reciprocity Theorem]].
+Whereas the above are properties of the Legendre symbol, they still hold for any odd integers <math>p</math> and <math>q</math> when using the Jacobi symbol defined below.
+== Additional properties ==
+We have for any odd prime <math>p</math> also the following rules:
+Multiplicaticity: <math>\left(\frac{a}{p}\right) \left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)</math>
+Euler's criterion: <math>\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p</math>
+First supplementary rule: <math>\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}</math>, so <math>\left(\frac{-1}{p}\right)=1 \iff p \equiv 1 \mod 4</math>
+Second supplementary rule: <math>\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}</math>, so <math>\left(\frac{2}{p}\right)=1 \iff p \equiv \pm 1 \mod 8</math>
+It's also usefull not to forget that the symbols are only properties <math>\mod p</math>, so <math>a \equiv b \mod p \implies \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right) </math>
 == Jacobi Symbol ==
-Now suppose that <math>m</math>, as above, is not [[composite]], and let <math>m=p_1^{e_1}\cdots p_n^{e_n}</math>. Then we write <math>\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)^{e_1}\cdots\left(\frac{a}{p_n}\right)^{e_n}</math>. This symbol is called the [[Jacobi symbol]].
+Now suppose that <math>m</math> is odd, and let <math>m=p_1^{e_1}\cdots p_n^{e_n}</math>. Then we write <math>\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)^{e_1}\cdots\left(\frac{a}{p_n}\right)^{e_n}</math>. 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 <math>p</math> and <math>q</math> instead.
+Note that <math>\left(\frac{a}{m}\right)=1</math> does not mean that <math>a</math> is a quadratic residue <math>\mod m</math> (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 <math>p</math> identical to the Legendre symbol, this gives a fast way to decide if an integer is a quadratic residue <math>\mod p</math> or not.
+Example:
+<math>\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}\right)=\left(\frac{2}{12345}\right)^5 \left(\frac{12345}{31}\right) = 1^5 \left(\frac{7}{31}\right) = -\left(\frac{31}{7}\right) = -\left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\frac{1}{3}\right)=1</math>
+Thus we know that <math>12345</math> is a quadratic residue modulo the prime <math>13337</math>. Indeed: <math>2425^2 \equiv 12345 \mod 13337</math>

Page

Toolbox

Search