Editing Quadratic reciprocity (section)

{{short description|Gives conditions for the solvability of quadratic equations modulo prime numbers}}
[[File:Disqvisitiones-800.jpg|thumb|[[Carl Friedrich Gauss|Gauss]] published the first and second proofs of the law of quadratic reciprocity on arts 125&ndash;146 and 262 of ''[[Disquisitiones Arithmeticae]]'' in 1801.]]
In [[number theory]], the '''law of quadratic reciprocity''' is a theorem about [[modular arithmetic]] that gives conditions for the solvability of [[quadratic equation]]s modulo [[prime number]]s. Due to its subtlety, it has many formulations, but the most standard statement is: 
{{math_theorem|name=Law of quadratic reciprocity|Let {{math|''p''}} and {{math|''q''}} be distinct odd prime numbers, and define the [[Legendre symbol]] as
:<math>\left(\frac{q}{p}\right)
=\begin{cases}
1 & \text{if } n^2 \equiv q \bmod p \text{ for some integer } n\\
-1 & \text{otherwise}.
\end{cases}</math>
Then
:<math> \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}.</math>
}}

This law, together with its [[#q_=_±1_and_the_first_supplement|supplements]], allows the easy calculation of any Legendre symbol, making it possible to determine whether there is an integer solution for any quadratic equation of the form <math>x^2\equiv a \bmod p</math> for an odd prime <math>p</math>; that is, to determine the "perfect squares" modulo <math>p</math>. However, this is a [[constructivism (mathematics)|non-constructive]] result: it gives no help at all for finding a ''specific'' solution; for this, other methods are required. For example, in the case <math>p\equiv 3 \bmod 4</math> using [[Euler's criterion]] one can give an explicit formula for the "square roots" modulo <math>p</math> of a quadratic residue <math>a</math>, namely,

:<math>\pm a^{\frac{p+1}{4}}</math>

indeed,

:<math>\left (\pm a^{\frac{p+1}{4}} \right )^2=a^{\frac{p+1}{2}}=a\cdot a^{\frac{p-1}{2}}\equiv a\left(\frac{a}{p}\right)=a \bmod p.</math>

This formula only works if it is known in advance that <math>a</math> is a [[quadratic residue]], which can be checked using the law of quadratic reciprocity.

The quadratic reciprocity theorem was conjectured by [[Leonhard Euler]] and [[Adrien-Marie Legendre]] and first proved by [[Carl Friedrich Gauss]],<ref>Gauss, DA&nbsp;§&nbsp;4, arts 107&ndash;150</ref> who referred to it as the "fundamental theorem" in his ''[[Disquisitiones Arithmeticae]]'' and his papers, writing

:''The fundamental theorem must certainly be regarded as one of the most elegant of its type.'' (Art. 151)

Privately, Gauss referred to it as the "golden theorem".<ref>E.g. in his mathematical diary entry for April 8, 1796 (the date he first proved quadratic reciprocity). See [https://books.google.com/books?id=NM36hgqmOLkC&dq=+%22theorema+aureum%22++diary+gauss&pg=PA30 facsimile page from Felix Klein's ''Development of Mathematics in the 19th century'']</ref> He published six [[mathematical proof|proofs]] for it, and two more were found in his posthumous papers. There are now over 240 published proofs.<ref>See F. Lemmermeyer's chronology and bibliography of proofs in the [[#External links|external references]]</ref> The shortest known proof is included [[#Proof|below]], together with short proofs of the law's supplements (the Legendre symbols of −1 and 2).

Generalizing the [[reciprocity law]] to higher powers has been a leading problem in mathematics, and has been crucial to the development of much of the machinery of [[abstract algebra|modern algebra]], number theory, and [[algebraic geometry]], culminating in [[Artin reciprocity]], [[class field theory]], and the [[Langlands program]].