Kvadratisk gensidighedslov

Den kvadratiske gensidighed lov , sammen med de to supplerende teoremer nævnt nedenfor, giver en metode til at beregne den Legendre symbolet og dermed at afgøre, om et tal er et kvadratisk resten eller en ikke-resten af (anden) nummer. Opdagelsen af ​​den kvadratiske gensidighedslov af Euler og beviset af Gauss ( Disquisitiones Arithmeticae 1801, men han havde et bevis allerede i 1796) var udgangspunktet for udviklingen af ​​moderne talteori . Selvom der er elementære beviser for gensidighedsloven, ligger dens essens relativt dybt, nemlig i den primære faktorisering i cirklerne, der deler felter med en primitiv enhedsrod . Gauss selv fremlagde adskillige metodologisk forskellige beviser. ${\ displaystyle \ mathbb {Q} (\ zeta)}$ ${\ displaystyle \ zeta}$

Den kvadratiske gensidighedslov afgiver udsagn om opløseligheden af ​​kvadratiske ligninger i modulær aritmetik , spørgsmålet om ligningen i højere grad fører til de højere gensidighedslove, som har været en af ​​drivkræfterne i algebraisk talteori siden Gauss. Gotthold Eisenstein behandlede den tredje graders sag ( cubic reciprocity law ) og den fjerde graders case (biquadratic reciprocity law) med Gauss.

udmelding

I det følgende betegner den Legendre symbolet med et heltal og et primtal . ${\ displaystyle \ left ({\ frac {a} {p}} \ right)}$${\ displaystyle a}$ ${\ displaystyle p}$

Den kvadratiske gensidighedslov siger, at for to forskellige ulige primtal og følgende gælder: ${\ displaystyle p}$${\ displaystyle q}$

${\ displaystyle \ left ({\ frac {p} {q}} \ right) \ left ({\ frac {q} {p}} \ right) = (- 1) ^ {{\ frac {p-1} {2}} {\ frac {q-1} {2}}} = \ venstre \ {{\ begynder {matrix} -1 & \ mathrm {f {\ ddot {u}} r} & p \ equiv q \ equiv 3 {\ pmod {4}} \\ 1 & {\ mbox {ellers}} & {\ mbox {(også}} \ mathrm {f {\ ddot {u}} r} \ p \ equiv 1 {\ pmod {4}} \ quad {\ mbox {eller}} \ quad q \ equiv 1 {\ pmod {4}} {\ mbox {)}} & \ end {matrix}} \ højre.}$

1. Supplerende sætning: For hvert ulige primtal gælder følgende: ${\ 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 {ellers}} & {\ mbox {(også}} \ mathrm { f {\ ddot {u}} r} \ p \ equiv -1 {\ pmod {4}} {\ mbox {)}} & \ end {matrix}} \ højre.}$

2. Supplerende sætning: For hvert ulige primtal gælder følgende: ${\ displaystyle p}$

${\ displaystyle \ left ({\ frac {2} {p}} \ right) = (- 1) ^ {\ frac {p ^ {2} -1} {8}} = \ left \ {{\ begin { matrix} 1 & \ mathrm {f {\ ddot {u}} r} & p \ equiv \ pm 1 {\ pmod {8}} \\ - 1 & {\ mbox {ellers}} & {\ mbox {(også }} \ mathrm {f {\ ddot {u}} r} \ p \ equiv \ pm 3 {\ pmod {8}} {\ mbox {)}} & \ end {matrix}} \ højre.}$

Beregningsregel

Hvis og er to forskellige ulige primtal, så: ${\ 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] \ left ({\ frac {q} {p}} \ right) & {\ text {ellers }} \ end {cases}}}$

Af det følger nemlig . ${\ displaystyle \ left ({\ frac {p} {q}} \ right) \ in \ {\ pm 1 \}}$${\ displaystyle \ left ({\ frac {p} {q}} \ right) ^ {- 1} = \ left ({\ frac {p} {q}} \ right)}$

Eksempler

• Det skal kontrolleres, om kongruensen

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

er løselig. For at gøre dette beregner man

${\ displaystyle \ left ({\ frac {10} {13}} \ right) = \ left ({\ frac {2} {13}} \ right) \ left ({\ frac {5} {13}} \ ret)}$(Legendre-symbolet er multiplikativt i det øverste argument).

Den første faktor kan bestemmes ved hjælp af den anden supplerende sætning . For at beregne den anden faktor anvender man gensidighedsloven: ${\ displaystyle -1}$

${\ displaystyle \ left ({\ frac {5} {13}} \ right) = \ left ({\ frac {13} {5}} \ right) = \ left ({\ frac {3} {5}} \ højre) = \ venstre ({\ frac {5} {3}} \ højre) = \ venstre ({\ frac {2} {3}} \ højre) = - 1}$

Her blev det andet ligetegn brugt, analogt med det næstsidste. ${\ displaystyle 13 \ equiv 3 {\ pmod {5}}}$${\ displaystyle 5 \ equiv 2 {\ pmod {3}}}$

Hvis du nu sætter begge faktorer sammen, er resultatet

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

og med det ved man, at ovenstående kongruens har en løsning. Løsningen er . ${\ displaystyle x \ equiv \ pm 6 {\ pmod {13}}}$

• Det skal kontrolleres, om kongruensen

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

er løselig. For at gøre dette beregner man igen

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

og kan som ovenfor yderligere forenkle de to faktorer med gensidighedsloven:

${\ displaystyle \ left ({\ frac {3} {127}} \ right) = (- 1) \ left ({\ frac {127} {3}} \ right) = (- 1) \ left ({\ frac {1} {3}} \ right) = - 1}$(i det sidste trin var at blive brugt)${\ displaystyle \ left ({\ frac {a ^ {2}} {p}} \ right) = \ left ({\ frac {a} {p}} \ right) ^ {2} = 1}$${\ displaystyle a = 1}$

og

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

${\ displaystyle = (- 1) \ left ({\ frac {2} {13}} \ right) \ left ({\ frac {3} {13}} \ right) = (- 1) (- 1) \ venstre ({\ frac {13} {3}} \ højre) = (- 1) (- 1) \ venstre ({\ frac {1} {3}} \ højre) = 1}$

Hvis du sætter alt sammen, resulterer det

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

og med det erkendelsen af, at ovenstående kongruens ikke har nogen løsning.

Effektiv beregning af Legendre-symbolet

Den her viste beregningsmetode har ulempen ved at skulle bestemme primfaktoriseringen af tælleren for Legendre-symbolet. Der er en mere effektiv metode, der fungerer på samme måde som den euklidiske algoritme og fungerer uden denne factoring. Den Jacobi-symbolet , en generalisering af Legendre symbolet, der bruges, for hvilken den kvadratiske gensidighed loven stadig er gyldig.

Se også

• Lemma von Zolotareff , en bevisvariant for den kvadratiske gensidighedslov ved hjælp af permutationer

litteratur

• K. Chandrasekharan : Introduktion til analytisk talteori. Springer Verlag, Basic Teachings of Mathematical Sciences 148, ISBN 3540041419 , kap. V: Loven om kvadratisk gensidighed.
• Eugen Netto (red.): Seks bevis for den grundlæggende sætning om kvadratiske rester af Carl Friedrich Gauß . Verlag Wilhelm Engelmann, Leipzig 1901, digitaliseret version.
• Gensidighed love. Fra Euler til Eisenstein.

Weblinks