Kvadratický zákon reciprocity

Kvadratický zákon reciprocity je série prohlášení týkajících se řešitelnosti kvadratické kongruence modulo . Pokud jsou podle tohoto zákona lichá prvočísla a alespoň jedno z nich má tvar, pak dvě přirovnání $p,q$ $4k+1,$

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

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

buď oba mají řešení, nebo oba ne. Proto je v názvu zákona použito slovo „reciprocita“. Pokud mají oba tvar, pak řešení má pouze jedno z uvedených srovnání [1] . $X,$ $p,q$ $4k+3,$

Související definice

Pokud pro daná celá čísla má porovnání řešení, pak se nazývá kvadratický zbytek [2] modulo, a pokud řešení neexistují, pak kvadratické nezbytkové modulo Pomocí této terminologie můžeme formulovat kvadratický zákon reciprocity takto: $p,q$ $x^{2}\equiv p{\pmod {q))$ $p$ $q,$ $q.$

Pokud jsou lichá prvočísla a alespoň jedno z nich má tvar, pak jsou buď oba kvadratické zbytky modulo navzájem, nebo oba jsou nezbytky. Pokud mají obě tvar, pak je kvadratický zbytek jedno a pouze jedno z těchto čísel - buď modulo nebo modulo $p,q$ $4k+1,$ $p,q$ $p,q$ $4k+3,$ $p$ $q,$ $q$ $p.$

Nechť je celé číslo, je liché prvočíslo. Symbol Legendre je definován takto: $p$ $q$ $\left({\frac {p}{q}}\right)$

$\left({\frac {p}{q}}\right)=0$ , je-li dělitelný . $p$ $q$
$\left({\frac {p}{q}}\right)=1$ , if je kvadratický zbytek modulo . $p$ $q$
$\left({\frac {p}{q}}\right)=-1$ , if je kvadratický nezbytkový modulo . $p$ $q$

Příklady reciprocity pro prvočísla od 3 do 97

Níže uvedená tabulka jasně ukazuje, která lichá prvočísla do 100 jsou zbytky a která jsou nezbytková. Například první řádek odkazuje na modulo 3 a znamená, že číslo 5 je kvadratický nezbytek (H), 7 je zbytek (B), 11 je nezbytkový atd. Tabulka jasně ukazuje, že pro čísla formuláře (zelené a modré buňky) jsou všechny kódy, které jsou k nim symetrické vzhledem k hlavní diagonále matice, úplně stejné, což znamená "reciprocita". Například buňka (5, 7) má stejný kód jako buňka (7, 5). Pokud buňky odpovídají dvěma číslům formuláře (žluté a červené buňky), pak jsou kódy opačné - například pro (11, 19). $4k+1$ $4k+3$

Vysvětlivky:

V	q je zbytek modulo p	q ≡ 1 (mod 4) nebo p ≡ 1 (mod 4) (nebo obojí)
H	q je nezbytkový modulo p	q ≡ 1 (mod 4) nebo p ≡ 1 (mod 4) (nebo obojí)
V	q je zbytek modulo p	oba q ≡ 3 (mod 4) i p ≡ 3 (mod 4)
H	q je nezbytkový modulo p	oba q ≡ 3 (mod 4) i p ≡ 3 (mod 4)

		3	5	7	jedenáct	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
		q
p	3		H	V	H	V	H	V	H	H	V	V	H	V	H	H	H	V	V	H	V	V	H	H	V
	5	H		H	V	H	H	V	H	V	V	H	V	H	H	H	V	V	H	V	H	V	H	V	H
	7	H	H		V	H	H	H	V	V	H	V	H	V	H	V	H	H	V	V	H	V	H	H	H
	jedenáct	V	V	H		H	H	H	V	H	V	V	H	H	V	V	V	H	V	V	H	H	H	V	V
	13	V	H	H	H		V	H	V	V	H	H	H	V	H	V	H	V	H	H	H	V	H	H	H
	17	H	H	H	H	V		V	H	H	H	H	H	V	V	V	V	H	V	H	H	H	V	V	H
	19	H	V	V	V	H	V		V	H	H	H	H	V	V	H	H	V	H	H	V	H	V	H	H
	23	V	H	H	H	V	H	H		V	V	H	V	H	V	H	V	H	H	V	V	H	H	H	H
	29	H	V	V	H	V	H	H	V		H	H	H	H	H	V	V	H	V	V	H	H	V	H	H
	31	H	V	V	H	H	H	V	H	H		H	V	H	V	H	V	H	V	V	H	H	H	H	V
	37	V	H	V	V	H	H	H	H	H	H		V	H	V	V	H	H	V	V	V	H	V	H	H
	41	H	V	H	H	H	H	H	V	H	V	V		V	H	H	V	V	H	H	V	H	V	H	H
	43	H	H	H	V	V	V	H	V	H	V	H	V		V	V	V	H	V	H	H	V	V	H	V
	47	V	H	V	H	H	V	H	H	H	H	V	H	H		V	V	V	H	V	H	V	V	V	V
	53	H	H	V	V	V	V	H	H	V	H	V	H	V	V		V	H	H	H	H	H	H	V	V
	59	V	V	V	H	H	V	V	H	V	H	H	V	H	H	V		H	H	V	H	V	H	H	H
	61	V	V	H	H	V	H	V	H	H	H	H	V	H	V	H	H		H	H	V	H	V	H	V
	67	H	H	H	H	H	V	V	V	V	H	V	H	H	V	H	V	H		V	V	H	V	V	H
	71	V	V	H	H	H	H	V	H	V	H	V	H	V	H	H	H	H	H		V	V	V	V	H
	73	V	H	H	H	H	H	V	V	H	H	V	V	H	H	H	H	V	V	V		V	H	V	V
	79	H	V	H	V	V	H	V	V	H	V	H	H	H	H	H	H	H	V	H	V		V	V	V
	83	V	H	V	V	H	V	H	V	V	V	V	V	H	H	H	V	V	H	H	H	H		H	H
	89	H	V	H	V	H	V	H	H	H	H	H	H	H	V	V	H	H	V	V	V	V	H		V
	97	V	H	H	V	H	H	H	H	H	V	H	H	V	V	V	H	V	H	H	V	V	H	V

Formulace se symboly Legendre

Gaussův kvadratický zákon reciprocity pro Legendreovy symboly to říká

\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1) (q-1)}{4}}={\begin{cases}1&{\text{if}}&p\ekviv 1{\pmod {4}}&{\text{or}}&q\ekviv 1{\ pmod {4)),\\-1&{\text{if}}&p\equiv 3{\pmod {4}}&{\text{u}}&q\equiv 3{\pmod {4}},\end {případy}}

kde p a q jsou zřetelná lichá prvočísla.

Platí také následující dodatky :

\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{if}}&p\equiv \pm 1{\pmod {8)),\\-1&{\text{if}}&p\equiv \pm 3{\pmod {8)),\end{cases} }

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

Důsledky

Následující fakt, známý také Fermatovi : pouze číslo 2 a prvočísla patřící do aritmetické posloupnosti mohou být prvotřídními děliteli čísel. $x^{2}+1$ $4k+1.$

Navíc je toto označení také kritériem, tedy srovnáním

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

modulo prime je rozhoditelné právě tehdy, když pomocí Legendreho symbolu lze poslední tvrzení vyjádřit následovně:

p>2

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

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

Otázka rozhodnosti srovnání $ax^{2}+bx+c\equiv 0{\pmod {p}}$

je řešena algoritmem využívajícím multiplikativitu Legendreho symbolu a kvadratického zákona reciprocity.

Příklady použití

Kvadratický zákon umožňuje rychle vypočítat Legendreovy symboly. Například $\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$

Proto to srovnání

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

má řešení.

Použijeme-li analog zákona reciprocity pro Jacobiho symbol , pak je výpočet ještě jednodušší, protože již není potřeba rozkládat čitatele symbolu na prvočinitele.

\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

Historie

Formulaci kvadratického zákona reciprocity znal Euler již v roce 1783 [3] . Legendre formuloval zákon nezávisle na Eulerovi a dokázal jej v některých konkrétních případech v roce 1785. Úplný důkaz publikoval Gauss v Arithmetical Investigations (1801); následně Gauss podal několik dalších svých důkazů, založených na zcela odlišných myšlenkách.

Jeden z nejjednodušších důkazů navrhl Zolotarev v roce 1872. [4] [5] [6]

Následně byla získána různá zobecnění kvadratického zákona reciprocity [7] .

Variace a zobecnění

Zákon kvadratické reciprocity se přirozeně zobecňuje na Jacobiho symboly , což vám umožňuje urychlit hledání Legendreho symbolu, protože již nevyžaduje kontrolu primality.

Viz také

Poznámky

↑ Carl Friedrich Gauss. Sborník z teorie čísel / Obecné vydání akademika I. M. Vinogradova , komentáře člena korespondenta. Akademie věd SSSR B. N. Delaunay . - M. : Nakladatelství Akademie věd SSSR, 1959. - S. 126. - 297 s. - (Klasika vědy).
↑ Quadratic Residue // Mathematical Encyclopedia (v 5 svazcích). - M .: Sovětská encyklopedie , 1979. - T. 2. - S. 785-786.
↑ Euler, Opuscula analytica, Petersburg, 1783.
↑ Zolotareff G. Nouvelle demonstrace de la loi de de de réciprocité de Legendre (francouzsky) // Nouvelles Annales de Mathématiques, 2e série: magazín. - 1872. - Sv. 11 . - str. 354-362 . (nedostupný odkaz)
↑ Prasolov V.V. Důkaz kvadratického zákona reciprocity podle Zolotareva // Matematické vzdělávání . - 2000. - T. 4 . - S. 140-144 .
↑ Gorin E. A. Permutace a kvadratický zákon reciprocity podle Zolotarev-Frobenius-Rousseau // Čebyševova sbírka. - 2013. - T. 14 , no. 4 . - S. 80-94 .
↑ Ireland K., Rosen M. Klasický úvod do moderní teorie čísel.

Literatura

Ireland K, Rosen M. Klasický úvod do moderní teorie čísel . - Moskva: Mir, 1987. - 428 s.
Bukhshtab A. A. Teorie čísel . - Moskva: Vzdělávání, 1966.
Vinogradov I.M. Základy teorie čísel . - Moskva: GITTL, 1952. - S. 180. - ISBN 5-93972-252-0 .
Davenport G. Vyšší aritmetika. Úvod do teorie čísel . - Moskva: Fizmatlit, 1965. - S. 176. - ISBN 539701298X . — ISBN 9785397012980 . Archivováno 30. září 2017 na Wayback Machine
Conway, J. Kvadratické formy dané nám v pocitech . - M. : MTsNMO, 2008. - 144 s. - 1000 výtisků. - ISBN 978-5-94057-268-8 .
Hasse G. Přednášky o teorii čísel . - Ed. zahraniční literatura, 1953. - 527 s.

Odkazy

Lvovsky S. M. Kvadratické právo reciprocity Archivováno 27. dubna 2016 na Wayback Machine Summer School "Modern Mathematics", 2012, Dubna

Slovníky a encyklopedie	Britannica (online)