Kvadratisk rest

Kvadratisk rest er et tall som opptrer ved løsning av andregradsligninger i modulær aritmetikk. Hvis den kalles r og modulus er heltallet n, kan den bestemmes ved å finne et tall x som oppfyller kongruensen

Forsiden til førsteutgaven av Disquisitiones Arithmeticae hvor kvadratiske rester ble systematisk studert av Gauss.

$x^{2}\equiv r{\pmod {n}}$

Denne har enten to kongruente løsninger eller ingen løsning. I det siste tilfellet kalles r  for en «ikke-rest».

For eksempel når n = 6, må man betrakte tallene {0,1,2,3,4,5}. Da har man modulo 6 at 0² ≡ 0, 1² ≡ 1, 2² ≡ 4, 3² ≡ 3, 4² ≡ 4, 5² ≡ 1. Det betyr at 1, 3 og 4 er kvadratiske rester, mens 2 og 5 er ikke-rester da det er vanlig å se bort fra 0 i denne sammenhengen. Tallet 1 er alltid en kvadratisk rest. Av størst betydning er vanligvis kvadratiske rester modulo et primtall p.

Generelt kan man si at kvadratiske rester er tall som har kvadratrøtter i modulær aritmetikk. Modulo 6 er både 1 og 5 kvadratrøtter av 1, mens 2 og 4 er begge kvadratrot av 4. De er viktige i forskjellige deler av tallteori og har praktiske anvendelser i moderne kryptografi. Deres store betydning ble etablert av Carl Friedrich Gauss og publisert på begynnelsen av 1800-tallet i hans store verk Disquisitiones Arithmeticae. Han mente at sammenhengene han oppdaget ved kvadratiske rester, var hans viktigste og dypeste resultat innen tallteorien.

Bakgrunn

En lineær ligning ax + b = 0 tilsvarer i modulær aritmetikk den lineære kongruensen ax + b ≡ 0 (mod n). Tilsvarende vil en andregradsligning gå over tili den kvadratiske kongruensen

$ax^{2}+bx+c\equiv 0{\pmod {n}}$

hvor koeffisientene kan ta verdiene {0,1,2,... , n - 1}. Den kan løses ved å sette y = 2ax + b. Da går den over til

$y^{2}\equiv D{\pmod {n}}$

hvor D = b² - 4ac er diskriminanten til den opprinnelige ligningen. Når denne er en kvadratisk rest, vil kongruensen ha to løsninger. I motsatt fall er det ingen slike.

Som et eksempel kan man betrakte kongruensen x² + 7x + 10 ≡ 0 (mod 11). Da er diskriminanten D = 7² - 4⋅10 = 9 slik at den kvadratiske kongruensen for y  blir y² ≡ 9 (mod 11). Den har den opplagte løsningen y = 3 som betyr at 2x = 3 - 7 = - 4 ≡ 7 (mod 11) slik at x = 9. Den andre løsningen følger fra y = - 3 ≡ 8 (mod 11) som gir x = 6 på samme måte.

Eulers kriterium

Når modulus n er et primtall p, kan antall kvadratiske rester bestemmes fra Fermats lille teorem. Det sier at

$a^{p-1}\equiv 1{\pmod {p}}$

der tallet a ikke kan deles med p. Da alle primtall p > 2 er oddetall, kan man skrive generelt at p = 2m + 1 slik at teoremet kan omskrives til

${\big (}a^{m}-1{\big )}{\big (}a^{m}+1{\big )}\equiv 0{\pmod {p}}$

Minst en av de to faktorene må derfor være delbar med p. Når a er en kvadratisk rest, vil den første faktoren oppfylle dette kravet. Da finnes det nemlig et tall x slik at x² er kongruent med a modulo p. Det betyr at

$a^{(p-1)/2}\equiv 1{\pmod {p}}$

da x^{p - 1} må være 1 modulo p ifølge det samme teoremet. Dette kalles Eulers kriterium for at a skal være en kvadratisk rest. På tilsvarende måte vil enhver kvadratisk ikke-rest b måtte oppfylle

$b^{(p-1)/2}\equiv -1{\pmod {p}}$

hvor -1 er kongruent med det positive tallet p - 1 modulo p.

Dette kan illustreres ved å velge eksempelet p = 7. Ved direkte utregning finner man da at 1, 2 og 4 er kvadratiske rester, mens 3, 5 og 6 er ikke-rester. Da er (p - 1)/2 = 3 som gir at 4³ = 64 ≡ 1 (mod 7), mens 5³ = 125 ≡ 6 ≡ -1 (mod 7).

Antall kvadratiske rester er alltid (p - 1)/2 og lik med antall ikke-rester. Det skyldes at kvadratiske rester kommer i par da x² er kongruent med (p - x)² modulo p. Følgelig er halvparten av tallene 1, 2, 3, .. p - 1 kvadratiske rester, mens den andre halvparten er ikke-rester.

Legendre-symbolet

For å kunne uttrykke på en kompakt måte om et tall er en kvadratisk rest eller ikke-rest, er det vanlig å benytte en notasjon som ble innført av Legendre. For et tall a og en modulus p er dette «Legendre-symbolet» definert ved at

$\left({\frac {a}{p}}\right)={\begin{cases}+1&{\text{hvis }}a{\text{ er en kvadratisk rest}}{\pmod {p}},\\-1&{\text{hvis }}a{\text{ er en kvadratisk ikke-rest}}{\pmod {p}}\\\end{cases}}$

hvor det igjen er antatt at tallet a ikke inneholder p som en faktor. Parentesen i symbolet omslutter ingen brøk a /p, men derimot tallet a plassert over modulus p som derfor ikke er noen nevner i en brøk.

For det tidligere eksempelet med p = 7 har man da

$\left({\frac {1}{7}}\right)=\left({\frac {2}{7}}\right)=\left({\frac {4}{7}}\right)=+1,\;\;\left({\frac {3}{7}}\right)=\left({\frac {5}{7}}\right)=\left({\frac {6}{7}}\right)=-1$.

Ved bruk av Eulers kriterium kan Legendre-symbolet generelt finnes fra

$\left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}$

Ofte kan man benytte regneregler som følger fra definisjonen av symbolet. Den viktigste av disse er

$\left({\frac {a}{p}}\right)\cdot \left({\frac {b}{p}}\right)=\left({\frac {a\cdot b}{p}}\right)$

som igjen er en direkte konsekvens av Eulers kriterium. Da hvert tall a kan skrives som et produkt av primtall, er det derfor naturlig at beregning av Legendre-symbolet kan konsentreres om slike tall.

I tillegg til den trivielle verdien $({\tfrac {1}{p}})=1$, har man også fra Eulers kriterium at

$\left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}+1&{\text{ når }}p\equiv 1{\pmod {4}}\\-1&{\text{ når }}p\equiv 3{\pmod {4}}\end{cases}}$

Det betyr at bare når primtallet p = 4n + 1 for et eller annet heltall n, er -1 ≡ p - 1 (mod p) en kvadratisk rest slik at man kan beregne √-1. For primtall på formen 4n + 3 er ikke dette mulig.

Primtallet p = 2 skiller seg ut fra alle andre primtall da det er et partall. For dette spesielle tilfellet har Legendre-symbolet verdiene

$\left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}+1&{\text{ når }}p\equiv 1\;{\text{eller }}7{\pmod {8}}\\-1&{\text{ når }}p\equiv 3\;{\text{eller }}5{\pmod {8}}\end{cases}}$

De kan finnes ved å betrakte nærmere denne kvadratiske resten i Eulers kriterium for disse fire klassene av forskjellige moduli.

Kvadratisk resiprositet

Bestemmelsen av kvadratiske rester kan i praksis reduseres til kun å betrakte rester som er primtall q, det vil si beregning av Legendre-symbolet $({\tfrac {q}{p}})$. Når modulus p er et stort tall, vil da bruk av Eulers kriterium involvere utregning av en potens med en stor eksponent. Dette kan være vanskelig og tidkrevende. Men oppdagelsen av en direkte sammenheng mellom symbolene $({\tfrac {q}{p}})$ og $({\tfrac {p}{q}})$ kan ofte i stor grad forenkle denne oppgaven. Denne ble påvist allerede av Euler og studert nærmere av Legendre. Men det var Gauss da han var 19 år gammel, som kunne bevise denne dype sammenhengen. Den kan skrives som

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

og kalles for setningen om «kvadratisk resiprositet». Beviset var komplisert, men han kunne vise til flere og noe enklere bevis senere i livet. Selv mente han at dette var ett av hans viktigste bidrag til tallteorien og omtalte setningen som sitt theorema auroreum - «det gyldne teorem».

Eksempel

Hvis den kvadratiske kongruensen $x^{2}\equiv 10\;({\text{mod}}\;13)$ skal ha en løsning, må Legendre-symbolet $({\tfrac {10}{13}})$ være positivt. Nå er

$\left({\frac {10}{13}}\right)=\left({\frac {2}{13}}\right)\cdot \left({\frac {5}{13}}\right)$

Den første faktoren er $({\tfrac {2}{13}})=-1$ fra den generelle formelen for $({\tfrac {2}{p}})$. Ved bruk av resiprositetssetningen kan den andre faktoren også utregnes og gir

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

siden 1 er en kvadratisk rest modulo 3, mens 2 er en ikke-rest. Dermed blir $({\tfrac {10}{13}})=(-1)\cdot (-1)=+1$. Kongruensen har derfor to løsninger som er ± 6 (mod 13).

På lignende måte kan man regne ut $({\tfrac {-3}{p}})$. For det første kan man skrive

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

Resiprositetssetningen sier nå at

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

Derfor blir

$\left({\frac {-3}{p}}\right)=\left({\frac {p}{3}}\right)={\begin{cases}+1&{\text{ når }}p\equiv 1{\pmod {3}}\\-1&{\text{ når }}p\equiv 2{\pmod {3}}\end{cases}}$

når man igjen benytter at modulo 3 er 1 en kvadratisk rest, mens 2 er en ikke-rest.

Eksterne lenker

• E.W. Weisstein, Quadratic Residue, Wolfram MathWorld