---
tag: 085MJS6907
kind: statement
role: theorem
name: Law of quadratic reciprocity
aliases: [quadratic-reciprocity]
msc: [11A15]
uses: [01J8AMV9RS, 0PHBS78HKT, 0ZXW95S44M]
sources:
  - url: https://en.wikipedia.org/wiki/Quadratic_reciprocity
    locator: Statement of the theorem
  - url: https://en.wikipedia.org/wiki/Quadratic_reciprocity
    locator: History and alternative statements
same_as:
  wikidata: Q472883
  wikipedia: Quadratic reciprocity
---

## Statement

Let $p$ and $q$ be distinct odd primes.
Then
$$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}},$$
where the symbols are [[Legendre symbols|01J8AMV9RS]].

## Remarks

So $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$ unless $p \equiv q \equiv 3 \pmod 4$. In that case $\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)$.
For example, $\left(\frac{7}{3}\right) = \left(\frac{1}{3}\right) = 1$, and $3 \equiv 7 \equiv 3 \pmod 4$. So $\left(\frac{3}{7}\right) = -1$.
With the [[first supplement|0PHBS78HKT]], the [[second supplement|0ZXW95S44M]] and [[multiplicativity|0NW1JP7TBR]], the law computes every Legendre symbol.

## History

Euler and Legendre conjectured the law.
Gauss first proved it in 1796, and he published proofs in his Disquisitiones Arithmeticae of 1801.
Gauss called it the fundamental theorem.

## Explanations

### L1 human

The law connects two questions: is $p$ a square modulo $q$, and is $q$ a square modulo $p$?
The answers are the same, except when both primes leave remainder $3$ on division by $4$. Then the answers are opposite.
This lets you swap and reduce the numbers, as in the [[Euclidean algorithm|0TRNT4X7J0]].