Quadratic reciprocity

related topics
{math, number, function}
{style, bgcolor, rowspan}
{law, state, case}
{work, book, publish}

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic which gives conditions for the solvability of quadratic equations modulo prime numbers. There are a number of equivalent statements of the theorem, which consists of two "supplements" and the reciprocity law:

Let p, q > 2 be two distinct (positive odd) prime numbers. Then

(Supplement 1)

(Supplement 2)

(Quadratic reciprocity)
Let q * = ±q   where the sign is plus if q ≡ 1 (mod 4) and minus if q ≡ −1 (mod 4). (I.e. |q *| = q and q * ≡ 1 (mod 4).) Then

Although the law can be used to tell whether any quadratic equation modulo a prime number has a solution, it does not provide any help at all for actually finding the solution. (The article on quadratic residues discusses algorithms for this.)

The theorem was conjectured by Euler and Legendre and first proven by Gauss.[1] He refers to it as the "fundamental theorem" in the Disquisitiones Arithmeticae and his papers; privately he referred to it as the "golden theorem."[2] He published six proofs, and two more were found in his posthumous papers. There are now over 200 published proofs.[3]

The first section of this article does not use the Legendre symbol and gives the formulations of quadratic reciprocity found by Legendre and Gauss. The Legendre-Jacobi symbol is introduced in the second section.

Contents

Full article ▸

related documents
System of linear equations
Prolog
Relational model
Combinatory logic
Spinor
Laplace transform
Linear programming
Big O notation
Fibonacci number
Trigonometric functions
Red-black tree
Field (mathematics)
Banach–Tarski paradox
Wikipedia:Free On-line Dictionary of Computing/R - S
Formal power series
Linked list
Lebesgue integration
Bernoulli number
Binary search algorithm
Computer numbering formats
Lambda calculus
P-adic number
Determinant
Distribution (mathematics)
Mandelbrot set
Turing machine
Travelling salesman problem
Binomial coefficient
Discrete cosine transform
Grothendieck topology