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 (Moving comment on symbols to talk page)
m (→‎Additional properties)
 
(11 intermediate revisions by 8 users not shown)
Line 1: Line 1:
−
Let <math>a</math> and <math>m</math> be [[integer]]s, with <math>m\neq 0</math>. We say that <math>a</math> is a '''quadratic residue''' [[modulo]] <math>m</math> if there is some number <math>n</math> so that <math>n^2-a</math> is [[divisible]] by <math>m</math>.
+
Let <math>a</math> and <math>m</math> be [[integer]]s, with <math>m\neq 0</math>. We say that <math>a</math> is a '''quadratic residue''' [[modulo]] <math>m</math> if there is some integer <math>n</math> so that <math>n^2-a</math> is [[divisibility | divisible]] by <math>m</math>.
  
 
== Legendre Symbol ==
 
== Legendre Symbol ==
Line 9: Line 9:
 
== Quadratic Reciprocity ==
 
== Quadratic Reciprocity ==
  
−
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 integer | 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 coprime integers <math>p</math> and <math>q</math> when using the Jacobi symbol defined below.
 +
 
 +
== Additional properties ==
 +
 
 +
Also, we have for any odd prime <math>p</math> the following rules:
 +
 
 +
Multiplicativity: <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 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 ==
  
−
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 necessary 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) =</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 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>.
 +
 
 +
== The general case ==
 +
 
 +
In general, to determine whether <math>a</math> is a quadratic residue modulo <math>n</math>, one has to check whether <math>a</math> is a quadratic residue modulo every odd prime <math>p</math> dividing <math>n</math>. This is enough if <math>n</math> is odd or <math>n=2m</math> and <math>m</math> is odd. If <math>n=4m</math> and <math>m</math> is odd, one also has to check that <math>a\equiv 0\mathrm{\ or\ }1\mod 4</math>. Finally, if <math>n</math> is divisible by <math>8</math>, one also has to check that <math>a\equiv 0,1,\mathrm{\ or\ }4\mod 8</math>.
 +
 
 +
[[Category:Number theory]]

Latest revision as of 12:10, 29 November 2017

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

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

Multiplicativity: $\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 necessary 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 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$.

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