A reciprocitás másodfokú törvénye

A reciprocitás másodfokú törvénye a másodfokú kongruencia modulo megoldhatóságára vonatkozó állítások sorozata . E törvény szerint, ha páratlan prímszámok és legalább az egyik alakja van, akkor két összehasonlítás $p,q$ $4k+1,$

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

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

vagy mindkettőre van megoldás, vagy mindkettőre nincs. Ezért a törvény címében a „viszonosság” szó szerepel. Ha mindkettőnek megvan a formája, akkor a megoldásban csak egy van a jelzett összehasonlítások közül [1] . $x,$ $p,q$ $4k+3,$

Kapcsolódó definíciók

Ha adott egész számokra az összehasonlításnak vannak megoldásai, akkor másodfokú maradéknak [2] modulonak nevezzük , ha pedig nincs megoldás, akkor másodfokú nem maradék modulo Ezzel a terminológiával a következőképpen fogalmazhatjuk meg a másodfokú reciprocitás törvényét: $p,q$ $x^{2}\equiv p{\pmod {q))$ $p$ $q,$ $q.$

Ha páratlan prímszámok, és legalább az egyiknek van alakja, akkor vagy mindkettő másodfokú maradék modulo egymásnak, vagy mindkettő nem maradék. Ha mindkettőnek van alakja, akkor a másodfokú maradék egy és csak egy ezek közül a számok közül - vagy modulo vagy modulo $p,q$ $4k+1,$ $p,q$ $p,q$ $4k+3,$ $p$ $q,$ $q$ $p.$

Legyen egész szám, legyen páratlan prímszám. A Legendre szimbólum meghatározása a következő: $p$ $q$ $\left({\frac {p}{q}}\right)$

$\left({\frac {p}{q}}\right)=0$ , ha osztható -vel . $p$ $q$
$\left({\frac {p}{q}}\right)=1$ , ha egy kvadratikus maradék modulo . $p$ $q$
$\left({\frac {p}{q}}\right)=-1$ , ha egy kvadratikus nem maradék modulo . $p$ $q$

Példák a 3 és 97 közötti prímszámok kölcsönösségére

Az alábbi táblázat jól mutatja, hogy mely páratlan prímek 100-ig maradékok és melyek nem maradékok. Például az első sor a 3-as modulra utal, és azt jelenti, hogy az 5-ös szám egy másodfokú nem-maradék (H), a 7 egy maradék (B), a 11 egy nem-maradék stb. A táblázat egyértelműen mutatja, hogy a számok esetében A formának (zöld és kék cellák) minden olyan kód, amely a mátrix főátlójához képest szimmetrikus, pontosan megegyezik, ez az, amit a "reciprocitás" jelent. Például az (5, 7) cellának ugyanaz a kódja, mint a (7, 5) cellának. Ha a cellák az űrlap két számának felelnek meg (sárga és vörös cellák), akkor a kódok ellentétesek - például (11, 19). $4k+1$ $4k+3$

Magyarázatok:

NÁL NÉL	q egy modulo p maradék	q ≡ 1 (4. mód) vagy p ≡ 1 (4. mód) (vagy mindkettő)
H	q egy nem maradék modulo p	q ≡ 1 (4. mód) vagy p ≡ 1 (4. mód) (vagy mindkettő)
NÁL NÉL	q egy modulo p maradék	q ≡ 3 (4. mód.) és p ≡ 3 (4. mód.)
H	q egy nem maradék modulo p	q ≡ 3 (4. mód.) és p ≡ 3 (4. mód.)

		3	5	7	tizenegy	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
		q
p	3		H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL
	5	H		H	NÁL NÉL	H	H	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H
	7	H	H		NÁL NÉL	H	H	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	H
	tizenegy	NÁL NÉL	NÁL NÉL	H		H	H	H	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	H	H	NÁL NÉL	NÁL NÉL
	13	NÁL NÉL	H	H	H		NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	H	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	H	H	NÁL NÉL	H	H	H
	17	H	H	H	H	NÁL NÉL		NÁL NÉL	H	H	H	H	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	H	NÁL NÉL	NÁL NÉL	H
	19	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	NÁL NÉL		NÁL NÉL	H	H	H	H	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	H	H	NÁL NÉL	H	NÁL NÉL	H	H
	23	NÁL NÉL	H	H	H	NÁL NÉL	H	H		NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	H	H	H	H
	29	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	NÁL NÉL		H	H	H	H	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	H	H
	31	H	NÁL NÉL	NÁL NÉL	H	H	H	NÁL NÉL	H	H		H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	H	H	H	NÁL NÉL
	37	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	H	H	H	H	H		NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H
	41	H	NÁL NÉL	H	H	H	H	H	NÁL NÉL	H	NÁL NÉL	NÁL NÉL		NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	H	NÁL NÉL	H	H
	43	H	H	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL		NÁL NÉL	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL
	47	NÁL NÉL	H	NÁL NÉL	H	H	NÁL NÉL	H	H	H	H	NÁL NÉL	H	H		NÁL NÉL	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	NÁL NÉL
	53	H	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	NÁL NÉL		NÁL NÉL	H	H	H	H	H	H	NÁL NÉL	NÁL NÉL
	59	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	NÁL NÉL	H	H	NÁL NÉL		H	H	NÁL NÉL	H	NÁL NÉL	H	H	H
	61	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	H	NÁL NÉL	H	H	H	H	NÁL NÉL	H	NÁL NÉL	H	H		H	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL
	67	H	H	H	H	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	NÁL NÉL	H	NÁL NÉL	H		NÁL NÉL	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H
	71	NÁL NÉL	NÁL NÉL	H	H	H	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	H	H	H	H		NÁL NÉL	NÁL NÉL	NÁL NÉL	NÁL NÉL	H
	73	NÁL NÉL	H	H	H	H	H	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	H	H	H	H	NÁL NÉL	NÁL NÉL	NÁL NÉL		NÁL NÉL	H	NÁL NÉL	NÁL NÉL
	79	H	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	H	H	H	H	H	NÁL NÉL	H	NÁL NÉL		NÁL NÉL	NÁL NÉL	NÁL NÉL
	83	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	H	H	NÁL NÉL	NÁL NÉL	H	H	H	H		H	H
	89	H	NÁL NÉL	H	NÁL NÉL	H	NÁL NÉL	H	H	H	H	H	H	H	NÁL NÉL	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	NÁL NÉL	H		NÁL NÉL
	97	NÁL NÉL	H	H	NÁL NÉL	H	H	H	H	H	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	NÁL NÉL	H	NÁL NÉL	H	H	NÁL NÉL	NÁL NÉL	H	NÁL NÉL

Megszövegezés Legendre szimbólumokkal

Gauss másodfokú reciprocitási törvénye a Legendre szimbólumokra kimondja

\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{u}}&q\equiv 3{\pmod {4}},\end {esetek}}

ahol p és q különálló páratlan prímek.

A következő kiegészítések is érvényesek :

\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} }

és

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

Következmények

A következő, Fermat által is ismert tény : csak a 2-es szám és a számtani sorozathoz tartozó prímszámok lehetnek számok prímosztói $x^{2}+1$ $4k+1.$

Sőt, ez a jel egyben ismérv, vagyis összehasonlítás

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

A modulo prím akkor és csak akkor határozható meg, ha A Legendre szimbólum használatával az utolsó állítás a következőképpen fejezhető ki:

p>2

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

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

Az összehasonlítás eldönthetőségének kérdése $ax^{2}+bx+c\equiv 0{\pmod {p}}$

A Legendre szimbólum multiplicativitását és a reciprocitás másodfokú törvényét alkalmazó algoritmussal oldjuk meg.

Használati példák

A másodfokú törvény lehetővé teszi a Legendre szimbólumok gyors kiszámítását. Például $\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)=\ bal ({\frac {2}{3}}\jobb)\cdot \left({\frac {3}{5}}\right)=\left({\frac {2}{3}}\jobb) ^{2}=1$

Ezért az összehasonlítás

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

van megoldása.

Ha a reciprocitás törvényének analógját használjuk a Jacobi-szimbólumhoz , akkor a számítás még egyszerűbb, mivel többé nem kell a szimbólum számlálóját prímtényezőkre bontani.

\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}}\jobbra)^{3} =1

Történelem

A másodfokú reciprocitás törvényének megfogalmazását Euler már 1783-ban ismerte [3] . Legendre Eulertől függetlenül fogalmazta meg a törvényt, és 1785-ben bizonyos esetekben be is bizonyította. A teljes bizonyítékot Gauss publikálta Aritmetical Investigations (1801) c. ezt követően Gauss számos további bizonyítást adott, amelyek teljesen más elképzeléseken alapultak.

Az egyik legegyszerűbb bizonyítékot Zolotarev javasolta 1872-ben. [4] [5] [6]

Ezt követően a másodfokú reciprocitás törvényének különféle általánosításait kaptuk [7] .

Változatok és általánosítások

A másodfokú reciprocitás törvénye természetesen általánosít a Jacobi-szimbólumokra , így felgyorsíthatja a Legendre-szimbólum megtalálását, mivel többé nem szükséges az elsődlegesség ellenőrzése.

Lásd még

Jegyzetek

↑ Carl Friedrich Gauss. Proceedings on number theory / I. M. Vinogradov akadémikus általános kiadása , a levelező tag megjegyzései. A Szovjetunió Tudományos Akadémia B. N. Delaunay . - M. : A Szovjetunió Tudományos Akadémia Kiadója, 1959. - S. 126. - 297 p. - (A tudomány klasszikusai).
↑ Quadratic Residue // Mathematical Encyclopedia (5 kötetben). - M .: Szovjet Enciklopédia , 1979. - T. 2. - S. 785-786.
↑ Euler, Opuscula analytica, Pétervár, 1783.
↑ Zolotareff G. Nouvelle demonstration de la loi de de réciprocité de Legendre (francia) // Nouvelles Annales de Mathématiques, 2e série: magazin. - 1872. - Kt. 11 . - P. 354-362 . (nem elérhető link)
↑ Prasolov V.V. A reciprocitás másodfokú törvényének bizonyítása Zolotarev szerint // Matematikai oktatás . - 2000. - T. 4 . - S. 140-144 .
↑ Gorin E. A. Permutációk és a reciprocitás másodfokú törvénye Zolotarev-Frobenius-Rousseau szerint // Csebisev-gyűjtemény. - 2013. - T. 14 , sz. 4 . - S. 80-94 .
↑ Ireland K., Rosen M. Klasszikus bevezetés a modern számelméletbe.

Irodalom

Ireland K, Rosen M. Klasszikus bevezetés a modern számelméletbe . - Moszkva: Mir, 1987. - 428 p.
Bukhshtab A. A. Számelmélet . - Moszkva: Oktatás, 1966.
Vinogradov I.M. A számelmélet alapjai . - Moszkva: GITTL, 1952. - P. 180. - ISBN 5-93972-252-0 .
Davenport G. Felső aritmetika. Bevezetés a számelméletbe . - Moszkva: Fizmatlit, 1965. - S. 176. - ISBN 539701298X . — ISBN 9785397012980 . Archiválva : 2017. szeptember 30. a Wayback Machine -nál
Conway, J. Quadratic Forms Given to Us in Sensations . - M. : MTsNMO, 2008. - 144 p. - 1000 példányban. - ISBN 978-5-94057-268-8 .
Hasse G. Előadások a számelméletről . - Szerk. külföldi irodalom, 1953. - 527 p.

Linkek

Lvovsky S. M. Quadratic reciprocity law Archiválva : 2016. április 27., a Wayback Machine Summer School "Modern Mathematics", 2012, Dubna

Szótárak és enciklopédiák	Britannica (online)