# Quadratic reciprocity

In mathematics, in number theory, the law of quadratic reciprocity connects the solvability of two related quadratic equations in modular arithmetic. As a consequence, it allows us to determine the solvability of any quadratic equation in modular arithmetic.

It was conjectured by Euler and Legendre and first satisfactorily proved by Gauss.

Suppose p and q are two different odd primes, which means that p and q are congruent either to 1 or to 3 (mod 4). If at least one of them is congruent to 1 mod 4, then the congruence

[itex]x^2\equiv p\ ({\rm mod}\ q)[itex]

has a solution x if and only if the congruence

[itex]y^2\equiv q\ ({\rm mod}\ p)[itex]

has a solution y. (The two solutions will in general be different.) On the other hand, if both primes are congruent to 3 modulo 4, then the congruence

[itex]x^2\equiv p\ ({\rm mod}\ q)[itex]

has a solution x if and only if the congruence

[itex]y^2\equiv q\ ({\rm mod}\ p)[itex]

does not have a solution y.

## Using the Legendre symbol

Using the Legendre symbol:

[itex]\left(\frac{p}{q}\right)=\left\{\begin{matrix}1 & \mathrm{if}\ p\ \mathrm{is\ a\ square\ modulo\ }q, \\

-1 & \mathrm{otherwise,}\end{matrix}\right.[itex]

these statements may be summarized as

[itex] \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}.[itex]

Since [itex](p-1)(q-1)/4[itex] is even if either p or q is congruent to 1 mod 4, and odd only if both p and q are odd, [itex] \left(\frac{p}{q}\right) \left(\frac{q}{p}\right)[itex] is equal to 1 if either p or q is congruent to 1 mod 4, and is equal to –1 if both p and q are congruent to 3 mod 4.

For example taking p to be 11 and q to be 19, we can relate [itex]\left(\frac{11}{19}\right)[itex] to [itex]\left(\frac{19}{11}\right)[itex], which is [itex]\left(\frac{8}{11}\right)[itex] or [itex]\left(\frac{-3}{11}\right)[itex]. To proceed further we may need to know supplementary laws for computing [itex]\left(\frac{2}{q}\right)[itex] and [itex]\left(\frac{-1}{q}\right)[itex] explicitly. For example,

[itex]\left(\frac{-1}{q}\right) = (-1)^{(q-1)/2}.[itex]

Using this we relate [itex]\left(\frac{-3}{11}\right)[itex] to [itex]\left(\frac{3}{11}\right)[itex] to [itex]\left(\frac{11}{3}\right)[itex] to [itex]\left(\frac{2}{3}\right)[itex] to [itex]\left(\frac{-1}{3}\right)[itex], and can complete the initial calculation.

Franz Lemmermeyer's book Reciprocity Laws: From Euler to Eisenstein, published in 2000, collects literature citations for 196 different published proofs for the quadratic reciprocity law.

There are cubic, quartic (biquadratic) and other higher reciprocity laws; but since two of the cube roots of 1 (root of unity) are not real, cubic reciprocity is outside the arithmetic of the rational numbers (and the same applies to higher laws).

The Gauss lemma reasons about the properties of quadratic residues and is involved in two of Gauss's proofs of quadratic reciprocity.

## External links

##### Navigation

Academic Kids Menu

• Art and Cultures
• Art (http://www.academickids.com/encyclopedia/index.php/Art)
• Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
• Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
• Music (http://www.academickids.com/encyclopedia/index.php/Music)
• Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
• Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
• Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
• Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
• Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
• Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
• History (http://www.academickids.com/encyclopedia/index.php/History)
• Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
• Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
• Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
• Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
• Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
• Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
• United States (http://www.academickids.com/encyclopedia/index.php/United_States)
• Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
• World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
• Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
• Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
• Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
• Science (http://www.academickids.com/encyclopedia/index.php/Science)
• Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
• Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
• Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
• Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
• Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
• Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
• Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
• Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
• Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
• Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
• Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
• Government (http://www.academickids.com/encyclopedia/index.php/Government)
• Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
• Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
• Space and Astronomy
• Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
• Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
• Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
• Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
• Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
• US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

• Home Page (http://academickids.com/encyclopedia/index.php)
• Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

• Clip Art (http://classroomclipart.com)