Quadratic law of reciprocity

The quadratic law of reciprocity is a series of statements concerning the solvability of a quadratic comparison modulo . According to this law, if $p, q$ ${\ displaystyle p, q}$ $p, q$ - odd prime numbers and at least one of them has the form $4k+1,$ ${\ displaystyle 4k + 1,}$ ${\ displaystyle 4k + 1,}$ then two comparisons:

x^{2}\equiv q{\pmod {p}}

{\ displaystyle x ^ {2} \ equiv q {\ pmod {p}}}

{\ displaystyle x ^ {2} \ equiv q {\ pmod {p}}}

x^{2}\equiv p{\pmod {q}}

{\ displaystyle x ^ {2} \ equiv p {\ pmod {q}}}

{\ displaystyle x ^ {2} \ equiv p {\ pmod {q}}}

either both have solutions for $x,$ ${\ displaystyle x,}$ $x,$ or both do not have. Therefore, the word “reciprocity” is used in the title of the law. If $p, q$ ${\ displaystyle p, q}$ $p, q$ both look like $4k+3,$ ${\ displaystyle 4k + 3,}$ ${\ displaystyle 4k + 3,}$ This solution has one and only one of the indicated comparisons ^[1] .

Content

Related definitions

If for given integers $p, q$ ${\ displaystyle p, q}$ comparison $x^{2}\equiv p{\pmod {q}}$ ${\ displaystyle x ^ {2} \ equiv p {\ pmod {q}}}$ has solutions then $p$ ${\ displaystyle p}$ called quadratic residue ^[2] modulo $q,$ ${\ displaystyle q,}$ and if there are no solutions, then - by a quadratic non-number modulo $q$ ${\ displaystyle q}$ . Using this terminology, we can formulate the quadratic law of reciprocity as follows:

If a $p, q$ ${\ displaystyle p, q}$ - odd prime numbers and at least one of them has the form $4k+1,$ ${\ displaystyle 4k + 1,}$ either or both $p, q$ ${\ displaystyle p, q}$ are quadratic residues modulo each other, or both are non-residues. If $p, q$ ${\ displaystyle p, q}$ both look like $4k+3,$ ${\ displaystyle 4k + 3,}$ then a quadratic residue is one and only one of these numbers — either $p$ ${\ displaystyle p}$ modulo $q,$ ${\ displaystyle q,}$ or $q$ ${\ displaystyle q}$ modulo $p .$ ${\ displaystyle p.}$

Let be $p$ ${\ displaystyle p}$ - integer $q$ ${\ displaystyle q}$ - odd prime number. Legendre Symbol $\left({\frac {p}{q}}\right)$ ${\ displaystyle \ left ({\ frac {p} {q}} \ right)}$ is defined as follows.

$\left({\frac {p}{q}}\right)=0$ ${\ displaystyle \ left ({\ frac {p} {q}} \ right) = 0}$ , if a $\ p$ ${\ displaystyle \ p}$ divided entirely by $\ q$ ${\ displaystyle \ q}$ .
$\left({\frac {p}{q}}\right)=1$ ${\ displaystyle \ left ({\ frac {p} {q}} \ right) = 1}$ , if a $\ p$ ${\ displaystyle \ p}$ is a quadratic modulo $\ q$ ${\ displaystyle \ q}$ .
$\left({\frac {p}{q}}\right)=-1$ ${\ displaystyle \ left ({\ frac {p} {q}} \ right) = - 1}$ , if a $\ p$ ${\ displaystyle \ p}$ is a quadratic non-absolute modulus $\ q$ ${\ displaystyle \ q}$ .

Examples of reciprocity for prime numbers from 3 to 97

The table below clearly shows which odd primes, not exceeding 100, are deductions, and which ones are non-deductions. For example, the first line refers to module 3 and means that the number 5 is a quadratic non-calculation (H), 7 is a residue (B), 11 - a non-residue, etc. The table clearly shows that for numbers like $4k+1$ ${\ displaystyle 4k + 1}$ (green and blue cells) all codes that are symmetrical to them relative to the main diagonal of the matrix are exactly the same as reciprocity. For example, in the cell (5, 7) the same code as in the cell (7, 5). If the cells correspond to two numbers of the form $4k+3$ ${\ displaystyle 4k + 3}$ (yellow and red cells), the codes are opposite - for example, for (11, 19).

Explanations:
AT	q is a modulo p residue	q ≡ 1 (mod 4) or p ≡ 1 (mod 4) (or both)
H	q is non-reading modulo p	q ≡ 1 (mod 4) or p ≡ 1 (mod 4) (or both)
AT	q is a modulo p residue	both q ≡ 3 (mod 4) and p ≡ 3 (mod 4)
H	q is non-reading modulo p	both q ≡ 3 (mod 4) and p ≡ 3 (mod 4)

		3	five	7	eleven	13	17	nineteen	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
		q
p	3		H	AT	H	AT	H	AT	H	H	AT	AT	H	AT	H	H	H	AT	AT	H	AT	AT	H	H	AT
	five	H		H	AT	H	H	AT	H	AT	AT	H	AT	H	H	H	AT	AT	H	AT	H	AT	H	AT	H
	7	H	H		AT	H	H	H	AT	AT	H	AT	H	AT	H	AT	H	H	AT	AT	H	AT	H	H	H
	eleven	AT	AT	H		H	H	H	AT	H	AT	AT	H	H	AT	AT	AT	H	AT	AT	H	H	H	AT	AT
	13	AT	H	H	H		AT	H	AT	AT	H	H	H	AT	H	AT	H	AT	H	H	H	AT	H	H	H
	17	H	H	H	H	AT		AT	H	H	H	H	H	AT	AT	AT	AT	H	AT	H	H	H	AT	AT	H
	nineteen	H	AT	AT	AT	H	AT		AT	H	H	H	H	AT	AT	H	H	AT	H	H	AT	H	AT	H	H
	23	AT	H	H	H	AT	H	H		AT	AT	H	AT	H	AT	H	AT	H	H	AT	AT	H	H	H	H
	29	H	AT	AT	H	AT	H	H	AT		H	H	H	H	H	AT	AT	H	AT	AT	H	H	AT	H	H
	31	H	AT	AT	H	H	H	AT	H	H		H	AT	H	AT	H	AT	H	AT	AT	H	H	H	H	AT
	37	AT	H	AT	AT	H	H	H	H	H	H		AT	H	AT	AT	H	H	AT	AT	AT	H	AT	H	H
	41	H	AT	H	H	H	H	H	AT	H	AT	AT		AT	H	H	AT	AT	H	H	AT	H	AT	H	H
	43	H	H	H	AT	AT	AT	H	AT	H	AT	H	AT		AT	AT	AT	H	AT	H	H	AT	AT	H	AT
	47	AT	H	AT	H	H	AT	H	H	H	H	AT	H	H		AT	AT	AT	H	AT	H	AT	AT	AT	AT
	53	H	H	AT	AT	AT	AT	H	H	AT	H	AT	H	AT	AT		AT	H	H	H	H	H	H	AT	AT
	59	AT	AT	AT	H	H	AT	AT	H	AT	H	H	AT	H	H	AT		H	H	AT	H	AT	H	H	H
	61	AT	AT	H	H	AT	H	AT	H	H	H	H	AT	H	AT	H	H		H	H	AT	H	AT	H	AT
	67	H	H	H	H	H	AT	AT	AT	AT	H	AT	H	H	AT	H	AT	H		AT	AT	H	AT	AT	H
	71	AT	AT	H	H	H	H	AT	H	AT	H	AT	H	AT	H	H	H	H	H		AT	AT	AT	AT	H
	73	AT	H	H	H	H	H	AT	AT	H	H	AT	AT	H	H	H	H	AT	AT	AT		AT	H	AT	AT
	79	H	AT	H	AT	AT	H	AT	AT	H	AT	H	H	H	H	H	H	H	AT	H	AT		AT	AT	AT
	83	AT	H	AT	AT	H	AT	H	AT	AT	AT	AT	AT	H	H	H	AT	AT	H	H	H	H		H	H
	89	H	AT	H	AT	H	AT	H	H	H	H	H	H	H	AT	AT	H	H	AT	AT	AT	AT	H		AT
	97	AT	H	H	AT	H	H	H	H	H	AT	H	H	AT	AT	AT	H	AT	H	H	AT	AT	H	AT

Formulation using Legendre symbols

Gauss’s quadratic reciprocity law for Legendre symbols states that

\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}={\begin{cases}1&{\text{если}}&p\equiv 1{\pmod {4}}&{\text{или}}&q\equiv 1{\pmod {4}},\\-1&{\text{если}}&p\equiv 3{\pmod {4}}&{\text{и}}&q\equiv 3{\pmod {4}},\end{cases}}

{\ displaystyle \ left ({\ frac {p} {q}} \ right) \ left ({\ frac {q} {p}} \ right) = (- 1) ^ {\ frac {(p-1) (q-1)} {4}} = {\ begin {cases} 1 & {\ text {if} & p \ equiv 1 {\ pmod {4}} & {\ text {or}} & q \ equiv 1 {\ pmod {4}}, \\ - 1 & {\ text {if}} & p \ equiv 3 {\ pmod {4}} & {\ text {and}} & q \ equiv 3 {\ pmod {4}}, \ end {cases}}}

where p and q are different odd primes.

The following additions are also valid:

\left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\text{если}}&p\equiv 1{\pmod {4}},\\-1&{\text{если}}&p\equiv 3{\pmod {4}},\end{cases}}

{\ displaystyle \ left ({\ frac {-1} {p}} \ right) = (- 1) ^ {\ frac {p-1} {2}} = {\ begin {cases} 1 & {\ text { if}} & p \ equiv 1 {\ pmod {4}}, \\ - 1 & {\ text {if}} & p \ equiv 3 {\ pmod {4}}, \ end {cases}}}

\left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}1&{\text{если}}&p\equiv \pm 1{\pmod {8}},\\-1&{\text{если}}&p\equiv \pm 3{\pmod {8}},\end{cases}}

{\ displaystyle \ left ({\ frac {2} {p}} \ right) = (- 1) ^ {\ frac {p ^ {2} -1} {8}} = {\ begin {cases} 1 & { \ text {if}} & p \ equiv \ pm 1 {\ pmod {8}}, \\ - 1 & {\ text {if}} & p \ equiv \ pm 3 {\ pmod {8}}, \ end {cases} }}

and

\left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)\quad {\text{если}}\quad p\equiv q{\pmod {4a}}.

{\ displaystyle \ left ({\ frac {a} {p}} \ right) = \ left ({\ frac {a} {q}} \ right) \ quad {\ text {if}} \ quad p \ equiv q {\ pmod {4a}}.}

Consequences

The following fact, also known Fermat : simple divisors of numbers $x^{2}+1$ ${\ displaystyle x ^ {2} +1}$ there can be only number 2 and prime numbers belonging to an arithmetic progression
$4k+1$ ${\ displaystyle 4k + 1}$ .

In other words, the comparison

x^{2}+1\equiv 0{\pmod {p}}

{\ displaystyle x ^ {2} +1 \ equiv 0 {\ pmod {p}}}

modulo

p>2

{\ displaystyle p> 2}

solvable if and only if

p\equiv 1{\pmod {4}}.

{\ displaystyle p \ equiv 1 {\ pmod {4}}.}

With the help of the Legendre symbol , the last statement can be expressed as follows:

\left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}.

{\ displaystyle \ left ({\ frac {-1} {p}} \ right) = (- 1) ^ {\ frac {p-1} {2}}.}

The question of the solvability of comparison
$ax^{2}+bx+c\equiv 0{\pmod {p}}$ ${\ displaystyle ax ^ {2} + bx + c \ equiv 0 {\ pmod {p}}}$

is solved by an algorithm using the multiplicity of the Legendre symbol and the quadratic reciprocity law.

Usage Examples

The quadratic law allows you to quickly calculate Legendre symbols. for example
$\left({\frac {983}{1103}}\right)=-\left({\frac {1103}{983}}\right)=-\left({\frac {120}{983}}\right)=-\left({\frac {2}{983}}\right)^{3}\cdot \left({\frac {3}{983}}\right)\cdot \left({\frac {5}{983}}\right)=\left({\frac {983}{3}}\right)\cdot \left({\frac {983}{5}}\right)=\left({\frac {2}{3}}\right)\cdot \left({\frac {3}{5}}\right)=\left({\frac {2}{3}}\right)^{2}=1$ ${\ displaystyle \ left ({\ frac {983} {1103}} \ right) = - \ left ({\ frac {1103} {983}} \ right) = - \ left ({\ frac {120} {983 }} \ right) = - \ left ({\ frac {2} {983}} \ right) ^ {3} \ cdot \ left ({\ frac {3} {983}} \ right) \ cdot \ left ( {\ frac {5} {983}} \ right) = \ left ({\ frac {983} {3}} \ right) \ cdot \ left ({\ frac {983} {5}} \ right) = \ left ({\ frac {2} {3}} \ right) \ cdot \ left ({\ frac {3} {5}} \ right) = \ left ({\ frac {2} {3}} \ right) ^ {2} = 1}$

Therefore, the comparison

x^{2}\equiv 983{\pmod {1103}}

{\ displaystyle x ^ {2} \ equiv 983 {\ pmod {1103}}}

has a solution.

If we use an analogue of the law of reciprocity for the Jacobi symbol , then the calculation is even simpler, since there is no longer any need to decompose the numerator of a symbol into prime factors.

\left({\frac {983}{1103}}\right)=-\left({\frac {1103}{983}}\right)=-\left({\frac {120}{983}}\right)=-\left({\frac {2}{983}}\right)^{3}\cdot \left({\frac {15}{983}}\right)=\left({\frac {983}{15}}\right)=\left({\frac {8}{15}}\right)=\left({\frac {2}{15}}\right)^{3}=1

{\ displaystyle \ left ({\ frac {983} {1103}} \ right) = - \ left ({\ frac {1103} {983}} \ right) = - \ left ({\ frac {120} {983 }} \ right) = - \ left ({\ frac {2} {983}} \ right) ^ {3} \ cdot \ left ({\ frac {15} {983}} \ right) = \ left ({ \ frac {983} {15}} \ right) = \ left ({\ frac {8} {15}} \ right) = \ left ({\ frac {2} {15}} \ right) ^ {3} = 1}

History

The formulation of the quadratic law of reciprocity was known to Euler in 1783 ^[3] . Legendre formulated the law independently of Euler and proved it in some particular cases in 1785. The full proof was published by Gauss in Arithmetic Studies (1801); Later Gauss gave some more of his evidence based on completely different ideas.

One of the simplest evidence was proposed by Zolotarev in 1872. ^[4] ^[5] ^[6]

Later, various generalizations of the quadratic reciprocity law were obtained ^[7] .

Variations and generalizations

The quadratic law of reciprocity is naturally generalized to Jacobi symbols , this allows us to speed up the finding of the Legendre symbol, since it no longer requires testing for simplicity.

Notes

↑ Karl Friedrich Gauss. Proceedings on number theory / The general edition of Academician I. M. Vinogradov , the comments of the corresponding member. USSR Academy of Sciences B. N. Delone . - Moscow : Publishing House of the Academy of Sciences of the USSR, 1959. - p. 126. - 297 p. - (Classics of science).
↑ Quadratic Deduction // Mathematical Encyclopedia (in 5 volumes). - M .: Soviet Encyclopedia , 1979. - T. 2. - p. 785-786.
↑ Euler, Opuscula analytica, Petersburg, 1783.
↑ Zolotareff G. Nouvelle démonstration de la loi de réciprocité de Legendre (Fr.) // Nouvelles Annales de Mathématiques, 2e série: magazine. - 1872. - Vol. 11 - P. 354-362 . (inaccessible link)
↑ V. Prasolov. Proof of the Zolotarev quadratic reciprocity law // Mathematical Enlightenment . - 2000. - Vol . 4 . - S. 140-144 .
↑ Gorin, E. A. Permutations and the quadratic law of reciprocity according to Zolotarev-Frobenius-Russo // Chebyshevsky collection. - 2013. - Vol. 14 , no. 4 - p . 80-94 .
↑ Ayerland K., Rozen M. A classic introduction to modern number theory.

Literature

Ayerland K., Rosen M. A classic introduction to modern number theory . - Moscow: World, 1987. - 428 p.
Buchstab A. A. Number Theory . - Moscow: Enlightenment, 1966.
Vinogradov I.M. Fundamentals of Number Theory . - Moscow: Hittl, 1952. - p. 180. - ISBN 5-93972-252-0 .
Davenport G. Higher arithmetic. Introduction to the theory of numbers . - Moscow: Fizmatlit, 1965. - p. 176. - ISBN 539701298X . - ISBN 9785397012980 .
Conway J. Quadratic forms, given to us in sensations . - M .: MTSNMO, 2008. - 144 p. - 1000 copies - ISBN 978-5-94057-268-8 .
Hasse G. Lectures on number theory . - Ed. foreign literature, 1953. - 527 p.

Links

Lvovsky S.M. Quadratic Law of Reciprocity Summer School "Contemporary Mathematics", 2012, Dubna

[1] Karl Friedrich Gauss. Proceedings on number theory / The general edition of Academician I. M. Vinogradov , the comments of the corresponding member. USSR Academy of Sciences B. N. Delone . - Moscow : Publishing House of the Academy of Sciences of the USSR, 1959. - p. 126. - 297 p. - (Classics of science).

[2] Quadratic Deduction // Mathematical Encyclopedia (in 5 volumes). - M .: Soviet Encyclopedia , 1979. - T. 2. - p. 785-786.

[3] Euler, Opuscula analytica, Petersburg, 1783.

[4] Zolotareff G. Nouvelle démonstration de la loi de réciprocité de Legendre (Fr.) // Nouvelles Annales de Mathématiques, 2e série: magazine. - 1872. - Vol. 11 - P. 354-362 . (inaccessible link)

[5] V. Prasolov. Proof of the Zolotarev quadratic reciprocity law // Mathematical Enlightenment . - 2000. - Vol . 4 . - S. 140-144 .

[6] Gorin, E. A. Permutations and the quadratic law of reciprocity according to Zolotarev-Frobenius-Russo // Chebyshevsky collection. - 2013. - Vol. 14 , no. 4 - p . 80-94 .

[7] Ayerland K., Rozen M. A classic introduction to modern number theory.