Vastavuoroisuuden neliöllinen laki

Neliönjäännöslause laki , ja kaksi ylimääräistä lauseet mainittu alla, antaa menetelmä laskea Legendren symboli ja siten päättää, onko numero on neliöllinen jäljellä tai ei-jäljellä (toinen) numero. Eulerin löytämä toissijaisuuslaki ja Gaussin todistus ( Disquisitiones Arithmeticae 1801, mutta hänellä oli todiste jo vuonna 1796) olivat lähtökohdat nykyaikaisen lukuteorian kehittämiselle . Vaikka alkeis todisteita tästä vastavuoroisuutta lain, sen ydin piilee melko syvällä, nimittäin Alkutekijähajotelma vuonna piireissä jakamalla kentät jossa primitiivinen yksikköjuuripro- . Gauss itse esitti useita metodologisesti erilaisia ​​todisteita. ${\ displaystyle \ mathbb {Q} (\ zeta)}$ ${\ displaystyle \ zeta}$

Neliöllinen vastavuoroisuuslainsäädäntö antaa lausuntoja neliöyhtälöiden ratkaistavuudesta modulaarisessa aritmeettisuudessa , kysymys ylemmän tason yhtälöiden ratkaisukyvystä johtaa korkeampiin vastavuoroisuuslaeihin, mikä on ollut yksi algebrallisen lukuteorian liikkeellepanevista voimista Gaussin jälkeen. Gotthold Eisenstein käsitteli kolmannen asteen tapausta ( kuutioinen vastavuoroisuuslaki ) ja neljännen asteen tapausta (kaksisuuntainen vastavuoroisuuslainsäädäntö) Gaussin kanssa.

lausunto

Seuraavassa tarkoittaa Legendren symbolin kanssa kokonaisluku ja alkuluku . ${\ displaystyle \ left ({\ frac {a} {p}} \ oikea)}$${\ displaystyle a}$ ${\ displaystyle p}$

Neliönjäännöslause laki sanoo, että kahden eri pariton alkulukuja ja pätee seuraava: ${\ displaystyle p}$${\ displaystyle q}$

${\ displaystyle \ left ({\ frac {p} {q}} \ right) \ left ({\ frac {q} {p}} \ right) = (- 1) ^ {{\ frac {p-1} {2}} {\ frac {q-1} {2}}} = \ vasen \ {{\ begin {matrix} -1 & \ mathrm {f {\ ddot {u}} r} & p \ equiv q \ equiv 3 {\ pmod {4}} \\ 1 & {\ mbox {muuten}} & {\ mbox {(myös}} \ mathrm {f {\ ddot {u}} r} \ p \ equiv 1 {\ pmod {4}} \ quad {\ mbox {tai}} \ quad q \ equiv 1 {\ pmod {4}} {\ mbox {)}} & \ end {matrix}} \ right.}$

1. Lisälause: Jokaiselle parittomalle alkuluvulle sovelletaan seuraavaa: ${\ 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 {muuten}} & {\ mbox {(myös}} \ mathrm { f {\ ddot {u}} r} \ p \ equiv -1 {\ pmod {4}} {\ mbox {)}} ja \ end {matriisi}} \ oikea.}$

2. Lisälause: Jokaiselle parittomalle alkuluvulle sovelletaan seuraavaa: ${\ displaystyle p}$

${\ displaystyle \ left ({\ frac {2} {p}} \ right) = (- 1) ^ {\ frac {p ^ {2} -1} {8}} = \ vasen \ {{\ begin { matriisi} 1 & \ mathrm {f {\ ddot {u}} r} & p \ equiv \ pm 1 {\ pmod {8}} \\ - 1 & {\ mbox {muuten}} ja {\ mbox {(myös }} \ mathrm {f {\ ddot {u}} r} \ p \ equiv \ pm 3 {\ pmod {8}} {\ mbox {)}} & \ end {matrix}} \ right.}$

Laskusääntö

Jos ja ovat kaksi erilaista parittomia alkulukuja, niin: ${\ 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] \ vasen ({\ frac {q} {p}} \ oikea) ja {\ text {muuten }} \ loppu {tapaukset}}}$

Siitä seuraa nimittäin . ${\ displaystyle \ left ({\ frac {p} {q}} \ right) \ in \ {\ pm 1 \}}$${\ displaystyle \ left ({\ frac {p} {q}} \ right) ^ {- 1} = \ left ({\ frac {p} {q}} \ right)}$

Esimerkkejä

• On tarkistettava, onko yhteneväisyys

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

on ratkaistavissa. Tätä varten lasketaan

${\ displaystyle \ left ({\ frac {10} {13}} \ right) = \ left ({\ frac {2} {13}} \ right) \ left ({\ frac {5} {13}} \ oikea)}$(Legendre-symboli on kerrottava ylemmässä argumentissa).

Ensimmäinen tekijä voidaan määrittää toisen täydentävän lauseen avulla . Toisen tekijän laskemiseksi sovelletaan vastavuoroisuuslakia: ${\ displaystyle -1}$

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

Tässä käytettiin toista yhtäläisyysmerkkiä , analogisesti edeltävän viimeisen kanssa. ${\ displaystyle 13 \ equiv 3 {\ pmod {5}}}$${\ displaystyle 5 \ equiv 2 {\ pmod {3}}}$

Jos laitat nyt molemmat tekijät yhteen, tulos on

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

ja sen kanssa tiedetään, että yllä olevalla kongruenssilla on ratkaisu. Ratkaisu on . ${\ displaystyle x \ equiv \ pm 6 {\ pmod {13}}}$

• On tarkistettava, onko yhteneväisyys

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

on ratkaistavissa. Tätä varten lasketaan uudelleen

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

ja voi, kuten edellä, yksinkertaistaa edelleen kahta tekijää vastavuoroisuuslailla:

${\ displaystyle \ left ({\ frac {3} {127}} \ right) = (- 1) \ left ({\ frac {127} {3}} \ right) = (- 1) \ left ({\ frac {1} {3}} \ oikea) = - 1}$(viimeisessä vaiheessa oli tarkoitus käyttää)${\ displaystyle \ left ({\ frac {a ^ {2}} {p}} \ right) = \ left ({\ frac {a} {p}} \ right) ^ {2} = 1}$${\ displaystyle a = 1}$

ja

${\ 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}} \ oikea)}$

${\ displaystyle = (- 1) \ vasen ({\ frac {2} {13}} \ oikea) \ vasen ({\ frac {3} {13}} \ oikea) = (- 1) (- 1) \ vasen ({\ frac {13} {3}} \ oikea) = (- 1) (- 1) \ vasen ({\ frac {1} {3}} \ oikea) = 1}$

Jos laitat kaiken yhteen, se johtaa

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

ja sen kanssa oivallus siitä, että yllä olevalla kongruenssilla ei ole ratkaisua.

Legendre-symbolin tehokas laskeminen

Tässä esitetyllä laskentamenetelmällä on se haitta, että joudutaan määrittämään Legendre-symbolin osoittajan alkulukko. On tehokkaampi menetelmä, joka toimii samalla tavalla kuin euklidinen algoritmi ja joka toimii ilman tätä kerrointa. Käytetään Jacobi-symbolia , joka on Legendre-symbolin yleistys, ja toissijaisuuslaki on edelleen voimassa.

Katso myös

• Lemma von Zolotareff , todistusvoimainen toissijaisuuslainsäätö muunnosten avulla

kirjallisuus

• K.Chandrasekharan : Johdatus analyyttiseen lukuteoriaan. Springer Verlag, Matematiikan perusopetukset 148, ISBN 3540041419 , luku . V: Toissijaisen vastavuoroisuuden laki.
• Eugen Netto (Toim.): Carl Friedrich Gaußin kuusi todistusta neliöjäännöksiä koskevasta peruslauseesta . Verlag Wilhelm Engelmann, Leipzig 1901, digitoitu versio.
• Vastavuoroisuuslait. Euleristä Eisensteiniin.

nettilinkit