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"

m
(→‎Quadratic Reciprocity)
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]].
 
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.
+
Whereas the above are properties of the Legendre symbol, they still hold for any odd coprime integers <math>p</math> and <math>q</math> when using the Jacobi symbol defined below.
  
 
== Additional properties ==
 
== Additional properties ==

Revision as of 19:05, 28 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 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\ \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 coprime 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 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 has also to check that $a\equiv 0\mathrm{\ or\ }1\mod 4$. Finally, if $n$ is divisible by $8$, one has also to check that $a\equiv 0,1,\mathrm{\ or\ }4\mod 8$.

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