Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Quadratic residues"
Line 24: Line 24:
 
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>
 
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>
+
It's also useful 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 ==
 
== Jacobi Symbol ==
Line 38: Line 38:
  
 
Example:
 
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>
+
<math>\left(\frac{12345}{13337}\right) =</math>
 +
 
 +
<math>=\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)=</math>
 +
 
 +
<math>= 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)=</math>
 +
 
 +
<math>=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>
 +
 
 +
In a more general manner, one for for example also gets:
 +
 
 +
<math>\left(\frac{-2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{2}{p}\right) = (-1)^{\frac{(p-2)^2-1}{8}}</math>, so <math>\left(\frac{-2}{p}\right)=1 \iff p \equiv 1,3 \mod 8</math>.
 +
 
 +
<math>\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} \left(\frac{p}{3}\right)</math>, so <math>\left(\frac{3}{p}\right)=1 \iff p \equiv \pm 1 \mod 12</math>.
 +
 
 +
<math>\left(\frac{-3}{p}\right) = \left(\frac{p}{3}\right)</math>, so <math>\left(\frac{-3}{p}\right)=1 \iff p \equiv 1 \mod 3</math>.

Revision as of 06:49, 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 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}\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$

In a more general manner, one for 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$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Quadratic_residues&oldid=4912"