Kvadraattinen vastavuoroisuuden laki

Kvadraattinen vastavuoroisuuden laki on joukko lauseita, jotka koskevat toisen asteen kongruenssimoduulin ratkaistavuutta . Tämän lain mukaan, jos ovat parittomia alkulukuja ja ainakin yksi niistä on muotoa, niin kaksi vertailua $p,q$ $4k+1,$

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

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

joko molemmilla on ratkaisuja tai molemmilla ei ole. Siksi lain otsikossa käytetään sanaa "vastavuoroisuus". Jos molemmilla on muoto , ratkaisussa on yksi ja vain yksi ilmoitetuista vertailuista [1] . $x,$ $p,q$ $4k+3,$

Aiheeseen liittyvät määritelmät

Jos annetuille kokonaisluvuille vertailulla on ratkaisuja, niin sitä kutsutaan neliöjäännökseksi [2] modulo, ja jos ratkaisuja ei ole, niin neliöllinen ei-jäännösmodulo Tätä terminologiaa käyttäen voimme muotoilla neliöllisen vastavuoroisuuden lain seuraavasti: $p,q$ $x^{2}\equiv p{\pmod {q))$ $s$ $q,$ $q.$

Jos ovat parittomia alkulukuja ja ainakin toisella niistä on muoto, niin joko molemmat ovat toisensa moduloivia neliöjäämiä tai molemmat ovat ei-jäännöksiä. Jos molemmilla on muoto, neliöjäännös on yksi ja vain yksi näistä luvuista - joko modulo tai modulo $p,q$ $4k+1,$ $p,q$ $p,q$ $4k+3,$ $s$ $q,$ $q$ $s.$

Antaa olla kokonaisluku, olla pariton alkuluku. Legendre-symboli määritellään seuraavasti: $s$ $q$ $\left({\frac {p}{q}}\right)$

$\left({\frac {p}{q}}\right)=0$ , jos jaollinen . $s$ $q$
$\left({\frac {p}{q}}\right)=1$ , jos on neliöllinen jäännös modulo . $s$ $q$
$\left({\frac {p}{q}}\right)=-1$ , jos on neliöllinen ei-jäännös modulo . $s$ $q$

Esimerkkejä vastavuoroisuudesta alkuluvuille 3 - 97

Alla olevasta taulukosta käy selvästi ilmi, mitkä parittomat alkuluvut 100 asti ovat jäämiä ja mitkä ei-jäämiä. Esimerkiksi ensimmäinen rivi viittaa modulo 3:een ja tarkoittaa, että numero 5 on neliöllinen ei-jäännös (H), 7 on jäännös (B), 11 on ei-jäännös jne. Taulukosta näkyy selvästi, että numeroille muodon (vihreät ja siniset solut) kaikki koodit, jotka ovat symmetrisiä niille matriisin päädiagonaalin suhteen, ovat täsmälleen samat, mitä "vastavuoroisuus" tarkoittaa. Esimerkiksi solulla (5, 7) on sama koodi kuin solulla (7, 5). Jos solut vastaavat kahta lomakkeen numeroa (keltaiset ja punaiset solut), koodit ovat vastakkaisia - esimerkiksi (11, 19). $4k+1$ $4k+3$

Selitykset:

AT	q on jäännös modulo p	q ≡ 1 (moodi 4) tai p ≡ 1 (mod 4) (tai molemmat)
H	q on ei-jäännös modulo p	q ≡ 1 (moodi 4) tai p ≡ 1 (mod 4) (tai molemmat)
AT	q on jäännös modulo p	sekä q ≡ 3 (moodi 4) että p ≡ 3 (mod 4)
H	q on ei-jäännös modulo p	sekä q ≡ 3 (moodi 4) että p ≡ 3 (mod 4)

		3	5	7	yksitoista	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
		q
s	3		H	AT	H	AT	H	AT	H	H	AT	AT	H	AT	H	H	H	AT	AT	H	AT	AT	H	H	AT
	5	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
	yksitoista	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
	19	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

Sanamuoto Legendre-symboleilla

Gaussin neliöllinen vastavuoroisuuslaki Legendre-symboleille sanoo tämän

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

jossa p ja q ovat erillisiä parittomat alkuluvut.

Myös seuraavat lisäykset ovat voimassa :

\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).

Seuraukset

Seuraava seikka, jonka myös Fermat tuntee : vain luku 2 ja aritmeettiseen sarjaan kuuluvat alkuluvut voivat olla lukujen alkujakajia $x^{2}+1$ $4k+1.$

Lisäksi tämä merkki on myös kriteeri, toisin sanoen vertailu

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

modulo prime on päätettävissä, jos ja vain jos Legendre-symbolia käyttämällä viimeinen väite voidaan ilmaista seuraavasti:

p>2

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

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

Kysymys vertailun päätettävyydestä $ax^{2}+bx+c\equiv 0{\pmod {p}}$

ratkaistaan algoritmilla, joka käyttää Legendre-symbolin multiplicatiivisuutta ja vastavuoroisuuden toisen asteen lakia.

Käyttöesimerkkejä

Toisen lain avulla voit nopeasti laskea Legendre-symbolit. Esimerkiksi $\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)=\ vasen({\frac {2}{3}}\oikea)\cdot \left({\frac {3}{5}}\right)=\left({\frac {2}{3}}\oikea) ^{2}=1$

Siksi vertailu

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

on ratkaisu.

Jos käytämme vastavuoroisuuden lain analogia Jacobi-symbolille , niin laskenta on vielä yksinkertaisempaa, koska symbolin osoittajaa ei enää tarvitse hajottaa alkutekijöiksi.

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

Historia

Euler tiesi neliöllisen vastavuoroisuuden lain muotoilun jo vuonna 1783 [3] . Legendre muotoili lain Eulerista riippumatta ja osoitti sen joissakin erityistapauksissa vuonna 1785. Täydellisen todisteen julkaisi Gauss julkaisussa Arithmetical Investigations (1801); myöhemmin Gauss antoi useita muita todisteita, jotka perustuivat täysin erilaisiin ideoihin.

Yksi yksinkertaisimmista todisteista ehdotti Zolotarev vuonna 1872. [4] [5] [6]

Myöhemmin saatiin erilaisia yleistyksiä toisen asteen vastavuoroisuuden laista [7] .

Muunnelmia ja yleistyksiä

Neliöllinen vastavuoroisuuslaki yleistyy luonnollisesti Jacobi-symboleihin , jolloin voit nopeuttaa Legendre-symbolin löytämistä, koska se ei enää vaadi primaalisuuden tarkistamista.

Katso myös

Muistiinpanot

↑ Carl Friedrich Gauss. Proceedings on lukuteoria / Akateemikko I. M. Vinogradovin yleinen painos , vastaavan jäsenen kommentit. Neuvostoliiton tiedeakatemia B. N. Delaunay . - M. : Neuvostoliiton tiedeakatemian kustantamo, 1959. - S. 126. - 297 s. - (tieteen klassikot).
↑ Quadratic Residue // Mathematical Encyclopedia (5 osassa). - M .: Neuvostoliiton tietosanakirja , 1979. - T. 2. - S. 785-786.
↑ Euler, Opuscula analytica, Pietari, 1783.
↑ Zolotareff G. Nouvelle demonstraatio de la loi de de réciprocité de Legendre (ranska) // Nouvelles Annales de Mathématiques, 2e sarja: aikakauslehti. - 1872. - Voi. 11 . - s. 354-362 . (linkki ei saatavilla)
↑ Prasolov V.V. Todistus toisen asteen vastavuoroisuuden laista Zolotarevin mukaan // Matemaattinen koulutus . - 2000. - T. 4 . - S. 140-144 .
↑ Gorin E. A. Permutaatiot ja vastavuoroisuuden neliölaki Zolotarev-Frobenius-Rousseaun mukaan // Chebyshev-kokoelma. - 2013. - T. 14 , nro 4 . - S. 80-94 .
↑ Ireland K., Rosen M. Klassinen johdatus nykyaikaiseen lukuteoriaan.

Kirjallisuus

Ireland K, Rosen M. Klassinen johdatus nykyaikaiseen lukuteoriaan . - Moskova: Mir, 1987. - 428 s.
Bukhshtab A. A. Numeroteoria . - Moskova: Koulutus, 1966.
Vinogradov I.M. Lukuteorian perusteet . - Moskova: GITTL, 1952. - P. 180. - ISBN 5-93972-252-0 .
Davenport G. Korkeampi aritmetiikka. Johdatus lukuteoriaan . - Moskova: Fizmatlit, 1965. - S. 176. - ISBN 539701298X . — ISBN 9785397012980 . Arkistoitu 30. syyskuuta 2017 Wayback Machineen
Conway, J. Kvadraattiset muodot, jotka meille annetaan tunneissa . - M. : MTsNMO, 2008. - 144 s. - 1000 kappaletta. - ISBN 978-5-94057-268-8 .
Hasse G. Luennot lukuteoriasta . - Toim. ulkomainen kirjallisuus, 1953. - 527 s.

Linkit

Lvovsky S. M. Neliöllinen vastavuoroisuuslaki Arkistoitu 27. huhtikuuta 2016 Wayback Machine Summer Schoolissa "Modern Mathematics", 2012, Dubna

Sanakirjat ja tietosanakirjat	Britannica (verkossa)