Gauss lemma (talteori)

Den här artikeln handlar om Gauss lemma i talteorin. För annan användning, se Gauss lemma .

Gauss lemma i talteori ger ett villkor för att ett heltal ska vara en kvadratisk rest . Även om det inte är användbart beräkningsmässigt, har det teoretisk betydelse, eftersom det är involverat i vissa bevis på kvadratisk ömsesidighet .

Det gjorde sitt första framträdande i Carl Friedrich Gauss tredje bevis (1808) på kvadratisk ömsesidighet och han bevisade det igen i sitt femte bevis (1818).

Uttalande av lemma

För varje udda primtal p låt a vara ett heltal som är coprime till p .

Tänk på heltal

$a,2a,3a,\dots ,{\frac {p-1}{2}}a$

och deras minst positiva rester modulo p . Dessa rester är alla distinkta, så det finns ( p − 1)/2 av dem.

Låt n vara antalet av dessa rester som är större än p /2 . Sedan

$\left({\frac {a}{p}}\right)=(-1)^{n},$

där $\left({\frac {a}{p}}\right)$ är Legendre-symbolen .

Exempel

Med p = 11 och a = 7 är den relevanta sekvensen av heltal

7, 14, 21, 28, 35.

Efter reduktion modulo 11 blir denna sekvens

7, 3, 10, 6, 2.

Tre av dessa heltal är större än 11/2 (nämligen 6, 7 och 10), så n = 3. På motsvarande sätt förutsäger Gauss lemma att

$\left({\frac {7}{11}}\right)=(-1)^{3}=-1.$

Detta är verkligen korrekt, eftersom 7 inte är en kvadratisk restmodulo 11.

Ovanstående sekvens av rester

7, 3, 10, 6, 2

kan också skrivas

−4, 3, −1, −5, 2.

I denna form visas heltal större än 11/2 som negativa tal. Det är också uppenbart att de absoluta värdena för resterna är en permutation av resterna

1, 2, 3, 4, 5.

Bevis

Ett ganska enkelt bevis, som påminner om ett av de enklaste bevisen i Fermats lilla sats , kan erhållas genom att utvärdera produkten

$Z=a\cdot 2a\cdot 3a\cdot \cdots \cdot {\frac {p-1}{2}}a$

modulo p på två olika sätt. Å ena sidan är det lika med

$Z=a^{(p-1)/2}\left(1\cdot 2\cdot 3 \cdot \cdots \cdot {\frac {p-1}{2}}\right)$

Den andra utvärderingen kräver mer arbete. Om x är en rest som inte är noll modulo p , låt oss definiera det "absoluta värdet" för x som

$|x|={\begin{cases}x&{\mbox{if }}1 \leq x\leq {\frac {p-1}{2}},\\px&{\mbox{if }}{\frac {p+1}{2}}\leq x\leq p-1.\ slut{cases}}$

Eftersom n räknar de multipler ka som är i det senare intervallet, och eftersom för dessa multipler, − ka är i det första intervallet, har vi

$Z=(-1)^{n}\left(|a|\cdot |2a|\cdot |3a|\cdot \cdots \cdots \left|{\frac {p-1}{2}} a\right|\right).$

Observera nu att värdena | ra | är distinkta för r = 1, 2, …, ( p − 1)/2 . Det har vi faktiskt

${\begin{aligned}|ra|&\equiv |sa|&{\pmod {p}}\\ ra&\equiv \pm sa&{\pmod {p}}\\r&\equiv \pm s&{\pmod {p}}\end{aligned}}$

eftersom a är coprime till p .

Detta ger r = s , eftersom r och s är positiva minsta rester. Men det finns exakt ( p − 1)/2 av dem, så deras värden är en omarrangemang av heltalen 1, 2, …, ( p − 1)/2 . Därför,

$Z=(-1)^{n}\left(1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}\right).$

Jämfört med vår första utvärdering kan vi ta bort icke-nollfaktorn

$1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}$

och vi är kvar med

$a^{(p-1)/2}=(-1)^{n}.$

Detta är det önskade resultatet, eftersom den vänstra sidan enligt Eulers kriterium bara är ett alternativt uttryck för Legendre-symbolen $\left({\frac {a}{p}}\right)$ .

Ansökningar

Gauss lemma används i många, men inte alls alla, av de kända bevisen på kvadratisk ömsesidighet.

Till exempel använde Gotthold Eisenstein Gauss lemma för att bevisa att om p är ett udda primtal då

$\left({\frac {a}{p }}\right)=\prod _{n=1}^{(p-1)/2}{\frac {\sin {(2\pi an/p)}}{\sin {(2\pi n /p)}}},$

och använde denna formel för att bevisa kvadratisk ömsesidighet. Genom att använda elliptiska snarare än cirkulära funktioner, bevisade han de kubiska och kvartiska ömsesidighetslagarna .

Leopold Kronecker använde lemma för att visa det

$\left({\frac {p}{q}}\right)=\operatörsnamn {sgn} \prod _{i=1}^{\frac {q-1}{2}}\prod _{ k=1}^{\frac {p-1}{2}}\left({\frac {k}{p}}-{\frac {i}{q}}\right).$

Att byta p och q ger omedelbart kvadratisk reciprocitet.

Det används också i vad som förmodligen är de enklaste bevisen för den "andra tilläggslagen"

$\left({\frac {2}{p}}\right)=(-1)^{(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}}$

Högre makter

Generaliseringar av Gauss lemma kan användas för att beräkna restsymboler med högre effekt. I sin andra monografi om biquadratic reciprocity använde Gauss ett fjärdepotens lemma för att härleda formeln för den biquadratiska karaktären 1 + i i Z [ i ] , ringen av Gaussiska heltal . Därefter använde Eisenstein tredje- och fjärdekraftsversioner för att bevisa kubisk och kvarts ömsesidighet .

n :e effektrestsymbol

Huvudartikel: Symbol för kraftrester

Låt k vara ett algebraiskt talfält med ring av heltal ${\mathcal {O}}_{k},$ och låt ${\mathfrak {p}}\subset {\ mathcal {O}}_{k}$ vara ett främsta ideal . Den ideala normen $\mathrm {N} {\mathfrak {p}}$ för ${\mathfrak {p}}$ definieras som kardinaliteten för restklassringen. Eftersom ${\mathfrak {p}}$ är primtal är detta ett ändligt fält ${\displaystyle {\mathcal {O}}_{k}/{\mathfrak {p}}} ,$ så idealnorm är $\mathrm {N} {\mathfrak {p}}=|{\mathcal {O}}_{k}/{\mathfrak {p}}|$ .

Antag att en primitiv n: te rot av enhet $\zeta _{n}\in {\mathcal {O}}_{k},$ att n och ${\mathfrak {p}}$ är coprime (dvs ${\displaystyle n\inte \in {\mathfrak {p}}} )$ . Då kan inga två distinkta n: te rötter av enhet vara kongruenta modulo ${\mathfrak {p}}$ .

Detta kan bevisas genom motsägelse, börja med att anta att $\zeta _{n}^{r}\equiv \zeta _{n}^{s}$ mod ${ \mathfrak {p}}$ , 0 < r < s ≤ n . Låt t = s − r så att $\zeta _{n}^{t}\equiv 1$ mod ${\mathfrak {p}}$ och 0 < t < n . Från definitionen av enhetens rötter,

$x^{n}-1=(x-1) (x-\zeta _{n})(x-\zeta _{n}^{2})\dots (x-\zeta _{n}^{n-1}),$

och dividera med x − 1 ger

$x^{n-1}+x^{n-2}+\dots +x+1=(x-\zeta _{n})(x-\zeta _{n}^{2}) \dots (x-\zeta _{n}^{n-1}).$

Låter x = 1 och tar rester mod ${\mathfrak {p}}$ ,

$n\equiv (1-\zeta _{n})(1-\zeta _{n}^{2})\dots (1-\zeta _{n}^{n-1}){\ pmod {\mathfrak {p}}}.$

Eftersom n och ${\mathfrak {p}}$ är coprime, $n\not \equiv 0$ mod ${\mathfrak {p}},$ men under antagandet, en av faktorerna till höger måste vara noll. Därför är antagandet att två distinkta rötter är kongruenta falskt.

Således är restklasserna för ${\mathcal {O}}_{k}/{\mathfrak {p}}$ som innehåller potenserna ζ _n en undergrupp av ordningen n av dess (multiplikativa) grupp av enheter, ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }={\mathcal {O}}_{k}/{\mathfrak {p}}- \{0\}.} Därför$ är ordningen på $({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }$ en multipel av n och

${\begin{aligned}\mathrm {N} {\mathfrak {p}}&=|{\mathcal {O}}_{k}/{\mathfrak {p}}|\\&=\left |({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }\right|+1\\&\equiv 1{\pmod {n}}.\end{aligned }}$

Det finns en analog till Fermats teorem i ${\mathcal {O}}_{k}$ . Om $\alpha \in {\mathcal {O}}_{k}$ för ${\displaystyle \alpha \not \in {\mathfrak {p}}},$ då

$\alpha ^{\mathrm {N} {\mathfrak {p}}-1}\equiv 1{\pmod {\mathfrak {p}}},$

och eftersom $\mathrm {N} {\mathfrak {p}}\equiv 1$ mod n ,

$\alpha ^{\frac {\mathrm {N} {\mathfrak {p}}-1}{n}}\equiv \zeta _{n }^{s}{\pmod {\mathfrak {p}}}$

är väldefinierad och kongruent med en unik n: te rot av enhet ζ _n ^s .

Denna rot av enhet kallas restsymbolen för n :te potensen för ${\mathcal {O}}_{k},$ och betecknas med

${\begin{aligned}\left({\frac {\alpha }{\mathfrak {p}}}\right)_{n}&=\zeta _{n}^{s}\\&\ ekvivalent \alpha ^{\frac {\mathrm {N} {\mathfrak {p}}-1}{n}}{\pmod {\mathfrak {p}}}.\end{aligned}}$

Det kan bevisas

$\left({\frac {\alpha }{\mathfrak {p}}}\right)_{n}=1$

om och bara om det finns en $\eta \in {\mathcal {O}}_{k}$ så att α ≡ η ⁿ mod ${\mathfrak {p}}$ .

1/ n system

Låt $\mu _{n}=\{1,\zeta _{n},\zeta _{n}^ {2},\dots ,\zeta _{n}^{n-1}\}$ vara den multiplikativa gruppen av de n :te rötterna av enhet, och låt $A=\{a_{1},a_{2},\dots ,a_{m}\}$ vara representanter för bisatserna för $}}_{k}/{\mathfrak {p}})^{\times }/\mu _{n}.} Då kallas A$ O för en 1 / n systemmod ${\mathfrak {p}}.$

Det finns med andra ord $mn=\mathrm {N} {\mathfrak {p}}-1$ tal i mängden $A\mu =\{a_{i}\zeta _{n}^{j}\;:\;1\leq i\leq m,\;\ ;\;0\leq j\leq n-1\},$ och denna uppsättning utgör en representativ uppsättning för $({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }.$

Siffrorna 1, 2, … ( p − 1)/2 , som används i den ursprungliga versionen av lemma, är ett 1/2-system (mod p ).

Att konstruera ett 1/ n- system är enkelt: låt M vara en representativ uppsättning för ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }.} Välj en 1 ∈$ M ${1}\in M}$ och ta bort talen kongruenta med $a_{1},a_{1}\zeta _{n},a_{1} \zeta _{n}^{2},\dots ,a_{1}\zeta _{n}^{n-1}$ från M . Välj en ₂ från M och ta bort talen som är kongruenta med ${\displaystyle a_{2},a_{2}\zeta _{ n},a_{2}\zeta _{n}^{2},\dots ,a_{2}\zeta _{n}^{n-1}} Upprepa$ tills M är slut. Då { a ₁ , a ₂ , … a _m } en 1/ n systemmod ${\mathfrak {p}}.$

Lemmat för n :e makter

Gauss' lemma kan utökas till den n :te potensrestsymbolen enligt följande. Låt $\zeta _{n}\in {\mathcal {O}}_{k}$ vara en primitiv n :te rot av enhet, ${\mathfrak {p }}\subset {\mathcal {O}}_{k}$ ett primideal, $\gamma \in {\mathcal {O}}_{k},\ ;\;n\gamma \not \in {\mathfrak {p}},$ (dvs ${\mathfrak {p}}$ är coprime till både γ och n ) och låt A = { a ₁ , a ₂ , …, a _m } vara en 1/ n systemmod ${\mathfrak {p}}.$

Sedan för varje i , 1 ≤ i ≤ m , finns det heltal π ( i ) , unika (mod m ) och b ( i ) , unika (mod n ), så att

$\gamma a_{i}\equiv \zeta _{n}^{b(i)}a_{\pi (i )}{\pmod {\mathfrak {p}}},$

och restsymbolen för n :te potens ges av formeln

$\left({\frac {\gamma }{\mathfrak {p}}}\right)_{n}=\zeta _{n}^{b(1)+b(2)+\dots + b(m)}.$

Det klassiska lemmat för den kvadratiska Legendre-symbolen är specialfallet n = 2 , ζ ₂ = −1 , A = {1, 2, …, ( p − 1)/2} , b ( k ) = 1 om ak > p /2 , b ( k ) = 0 om ak < p /2 .

Bevis

Beviset för n :te potenslemma använder samma idéer som användes i beviset för andragradslemma.

Förekomsten av heltalen π ( i ) och b ( i ) , och deras unika (mod m ) respektive (mod n ), kommer från det faktum att Aμ är en representativ mängd.

Antag att π ( i ) = π ( j ) = p , dvs

$\gamma a_{i}\equiv \zeta _{n}^{r}a_{p}{\pmod {\mathfrak {p}}}$

och

$\gamma a_{j}\equiv \zeta _{n}^{s}a_{p}{\pmod {\mathfrak {p}}}.$

Sedan

$\zeta _{n}^{sr}\gamma a_{i}\equiv \zeta _{n}^ {s}a_{p}\equiv \gamma a_{j}{\pmod {\mathfrak {p}}}$

Eftersom γ och ${\mathfrak {p}}$ är coprime kan båda sidorna delas med γ , vilket ger

$\zeta _{n}^{sr}a_{i}\equiv a_{j}{\pmod {\mathfrak {p}}},$

vilket, eftersom A är ett 1/ n- system, innebär s = r och i = j , vilket visar att π är en permutation av mängden {1, 2, …, m } .

Sedan å ena sidan, genom definitionen av kraftrestsymbolen,

${\ displaystyle {\begin{aligned}(\gamma a_{1})(\gamma a_{2})\dots (\gamma a_{m})&=\gamma ^{\frac {\mathrm {N} {\mathfrak {p}}-1}{n}}a_{1}a_{2}\dots a_{m}\\&\equiv \left({\frac {\gamma }{\mathfrak {p}}}\right )_{n}a_{1}a_{2}\dots a_{m}{\pmod {\mathfrak {p}}},\end{aligned}}}$

och å andra sidan, eftersom π är en permutation,

${\begin{aligned}(\gamma a_{1})(\gamma a_{2}) \dots (\gamma a_{m})&\equiv {\zeta _{n}^{b(1)}a_{\pi (1)}}{\zeta _{n}^{b(2)} a_{\pi (2)}}\dots {\zeta _{n}^{b(m)}a_{\pi (m)}}&{\pmod {\mathfrak {p}}}\\&\ ekvivalent \zeta _{n}^{b(1)+b(2)+\dots +b(m)}a_{\pi (1)}a_{\pi (2)}\dots a_{\pi ( m)}&{\pmod {\mathfrak {p}}}\\&\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}a_{1} a_{2}\dots a_{m}&{\pmod {\mathfrak {p}}},\end{aligned}}$

så

$\left({ \frac {\gamma }{\mathfrak {p}}}\right)_{n}a_{1}a_{2}\dots a_{m}\equiv \zeta _{n}^{b(1)+ b(2)+\dots +b(m)}a_{1}a_{2}\dots a_{m}{\pmod {\mathfrak {p}}},$

och eftersom för alla 1 ≤ i ≤ m , a _i och ${\mathfrak {p}}$ är coprime, kan a ₁ a ₂ ... a _m avbrytas från båda sidor av kongruensen,

$\left({\frac {\gamma }{\mathfrak {p}}} \right)_{n}\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}{\pmod {\mathfrak {p}}},$

och satsen följer av det faktum att inga två distinkta n: te rötter till enhet kan vara kongruenta (mod ${\displaystyle {\mathfrak {p}}} )$ .

Relation till överföringen i gruppteori

Låt G vara den multiplikativa gruppen av restklasser som inte är noll i Z / p Z , och låt H vara undergruppen {+1, −1}. Betrakta följande coset-representanter för H i G ,

$1,2,3,\dots ,{\frac {p-1}{2}}.$

Genom att tillämpa mekanismen för överföringen på denna samling av coset-representanter får vi överföringshomomorfismen

$\phi :G\to H,$

som visar sig vara den karta som skickar a till (−1) ⁿ , där a och n är som i lemmasatsen. Gauss lemma kan då ses som en beräkning som uttryckligen identifierar denna homomorfism som den kvadratiska restkaraktären.

Se även

• Zolotarevs lemma