Quadratic law of reciprocity

The quadratic reciprocity law , together with the two supplementary theorems mentioned below, gives a method to calculate the Legendre symbol and thus to decide whether a number is a quadratic remainder or a non-remainder of (another) number. The discovery of the quadratic reciprocity law by Euler and the proof by Gauss ( Disquisitiones Arithmeticae 1801, but he had a proof as early as 1796) were the starting points for the development of modern number theory . Although there are elementary proofs of the reciprocity law, its essence lies relatively deep, namely in the prime factorization in the circles dividing fields with a primitive unit root . Gauss himself presented several methodologically different proofs. ${\displaystyle \mathbb {Q} (\zeta )}$ ${\displaystyle \zeta }$

The quadratic reciprocity law makes statements about the solvability of quadratic equations in modular arithmetic , the question of the solvability of equations of a higher degree leads to the higher reciprocity laws, which has been one of the driving forces of algebraic number theory since Gauss. Gotthold Eisenstein dealt with the third-degree case ( cubic reciprocity law ), and the fourth-degree case (biquadratic reciprocity law) with Gauss.

statement

In the following, the Legendre symbol is denoted by an integer and a prime number . ${\displaystyle \left({\frac {a}{p}}\right)}$ ${\displaystyle a}$ ${\displaystyle p}$

The quadratic reciprocity law says that for two different odd prime numbers and the following applies: ${\displaystyle p}$ ${\displaystyle q}$

${\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}=\left\{{\begin{matrix}-1&\mathrm {f{\ddot {u}}r} &p\equiv q\equiv 3{\pmod {4}}\\1&{\mbox{sonst}}&{\mbox{(also }}\mathrm {f{\ddot {u}}r} \ p\equiv 1{\pmod {4}}\quad {\mbox{oder}}\quad q\equiv 1{\pmod {4}}{\mbox{)}}&\end{matrix}}\right.}$

1. Supplementary theorem: For every odd prime number, the following applies: ${\displaystyle p}$

${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}=\left\{{\begin{matrix}1&\mathrm {f{\ddot {u}}r} &p\equiv 1{\pmod {4}}\\-1&{\mbox{sonst}}&{\mbox{(also }}\mathrm {f{\ddot {u}}r} \ p\equiv -1{\pmod {4}}{\mbox{)}}&\end{matrix}}\right.}$

2nd supplementary theorem: for every odd prime number : ${\displaystyle p}$

${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}=\left\{{\begin{matrix}1&\mathrm {f{\ddot {u}}r} &p\equiv \pm 1{\pmod {8}}\\-1&{\mbox{sonst}}&{\mbox{(also }}\mathrm {f{\ddot {u}}r} \ p\equiv \pm 3{\pmod {8}}{\mbox{)}}&\end{matrix}}\right.}$

Calculation rule

If and are two different odd prime numbers, then: ${\displaystyle p}$ ${\displaystyle q}$

${\displaystyle \left({\frac {p}{q}}\right)={\begin{cases}-\left({\frac {q}{p}}\right)&\mathrm {f{\ddot {u}}r} \ p\equiv q\equiv 3{\pmod {4}}\\[0.5em]\left({\frac {q}{p}}\right)&{\text{sonst}}\end{cases}}}$

From it follows namely . ${\displaystyle \left({\frac {p}{q}}\right)\in \{\pm 1\}}$ ${\displaystyle \left({\frac {p}{q}}\right)^{-1}=\left({\frac {p}{q}}\right)}$

Examples

• It is to be checked whether the congruence

${\displaystyle x^{2}\equiv 10{\pmod {13}}}$

is solvable. For this one calculates

${\displaystyle \left({\frac {10}{13}}\right)=\left({\frac {2}{13}}\right)\left({\frac {5}{13}}\right)}$(the Legendre symbol is multiplicative in the upper argument).

The first factor can be determined with the help of the second supplementary sentence . To calculate the second factor, we apply the reciprocity law: ${\displaystyle -1}$

${\displaystyle \left({\frac {5}{13}}\right)=\left({\frac {13}{5}}\right)=\left({\frac {3}{5}}\right)=\left({\frac {5}{3}}\right)=\left({\frac {2}{3}}\right)=-1}$

Here the second equal sign was used, analogously to the penultimate one. ${\displaystyle 13\equiv 3{\pmod {5}}}$ ${\displaystyle 5\equiv 2{\pmod {3}}}$

If you now put both factors together, the result is

${\displaystyle \left({\frac {10}{13}}\right)=(-1)(-1)=1}$

and with this one knows that the above congruence has a solution. The solution is . ${\displaystyle x\equiv \pm 6{\pmod {13}}}$

• It is to be checked whether the congruence

${\displaystyle x^{2}\equiv 57{\pmod {127}}}$

is solvable. For this one calculates again

${\displaystyle \left({\frac {57}{127}}\right)=\left({\frac {3}{127}}\right)\left({\frac {19}{127}}\right)}$

and, as above, can further simplify the two factors with the reciprocity law:

${\displaystyle \left({\frac {3}{127}}\right)=(-1)\left({\frac {127}{3}}\right)=(-1)\left({\frac {1}{3}}\right)=-1}$(in the last step was to be used) ${\displaystyle \left({\frac {a^{2}}{p}}\right)=\left({\frac {a}{p}}\right)^{2}=1}$ ${\displaystyle a=1}$

and

${\displaystyle \left({\frac {19}{127}}\right)=(-1)\left({\frac {127}{19}}\right)=(-1)\left({\frac {13}{19}}\right)=(-1)\left({\frac {19}{13}}\right)=(-1)\left({\frac {6}{13}}\right)}$

${\displaystyle =(-1)\left({\frac {2}{13}}\right)\left({\frac {3}{13}}\right)=(-1)(-1)\left({\frac {13}{3}}\right)=(-1)(-1)\left({\frac {1}{3}}\right)=1}$

If you put everything together, it results

${\displaystyle \left({\frac {57}{127}}\right)=(-1)\cdot 1=-1}$

and with it the realization that the above congruence has no solution.

Efficient calculation of the Legendre symbol

The method of calculation shown here has the disadvantage of having to determine the prime factorization of the numerator of the Legendre symbol. There is a more efficient method that works similarly to the Euclidean algorithm and does not require this factorization. The Jacobi symbol , a generalization of the Legendre symbol, is used for which the quadratic reciprocity law is still valid.

See also

• Lemma von Zolotareff , a proof variant for the quadratic reciprocity law with the help of permutations

literature

• K. Chandrasekharan : Introduction to Analytic Number Theory. Springer Verlag, Basic Teachings of Mathematical Sciences 148, ISBN 3540041419 , chap. V: The law of quadratic reciprocity.
• Eugen Netto (Ed.): Six proofs of the fundamental theorem about quadratic residues by Carl Friedrich Gauß . Wilhelm Engelmann Verlag, Leipzig 1901, digitized version.
• Reciprocity Laws. From Euler to Eisenstein.

Web links

Wikiversity: A Proof of the Quadratic Law of Reciprocity  - Course Materials