4.1 Kvadratiske rester, Legendre-symbolet og Eulers kriterium

$$x^2\equiv a\pmod p$$

har en løsning — altså dersom $a$ er «et kvadrattall sett med modulo-$p$-øyne».

I klarspråk: $a$ er en kvadratisk rest når du kan finne et tall som, opphøyd i annen, gir rest $a$ ved divisjon med $p$. Med $p=13$ er $10$ en kvadratisk rest, fordi $6^2=36=2\cdot 13+10$.

Er det ingen slik $x$, kalles $a$ en kvadratisk ikke-rest.

To presiseringer som er verdt å ha med fra starten:

- Vi ser bare på odde primtall $p$ som modulus. Primtallet $2$ er et unntak (alt er kvadrat modulo $2$), og sammensatte moduler behandles ved å splitte modulusen i primtallspotenser.
- Vi antar $p\nmid a$. Er $p\mid a$, er $a\equiv 0$, og $x=0$ er en løsning — men det tilfellet er trivielt og holdes utenfor tellingen.

Definisjonen må sitte utenat, og den er også språket sensor forventer: skriv «$a$ er en kvadratisk rest modulo $p$», ikke «$a$ er et kvadrattall mod $p$».

Oppskriften: regn ut $1^2,2^2,3^2,\dots$ modulo $p$, og stopp ved $\displaystyle x=\frac{p-1}{2}$. Restene du har fått, er nøyaktig de kvadratiske restene.

Hvorfor du kan stoppe halvveis: $x$ og $p-x$ gir samme kvadrat, siden
$$(p-x)^2=p^2-2px+x^2\equiv x^2\pmod p.$$
Andre halvdel av tabellen gjentar altså første halvdel baklengs, og det er derfor det er nøyaktig $(p-1)/2$ kvadratiske rester.

Når du skal bruke den: for $p$ opp til rundt $20$ er tabellmetoden raskest, og den gir deg i tillegg løsningene og ikke bare et ja/nei. Er $p$ større, blir tabellen for lang for eksamenstid, og du går over til regnereglene og Eulers kriterium.

Utledes på stedet — dette er ikke et kort du pugger, men en tabell du lager i margen på tjue sekunder.

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

I klarspråk: symbolet er en ja/nei-maskin for spørsmålet «har $x^2\equiv a\pmod p$ løsning?», med $+1$ for ja og $-1$ for nei. Den tredje verdien $0$ er randtilfellet der $a$ er delelig med $p$.

Definisjonen må sitte utenat. Den er ikke en formel du regner med, men avtalen alt annet hviler på.

Notasjonen er ikke en brøk. $\displaystyle \left(\frac{a}{p}\right)$ ser ut som $a$ delt på $p$, men det er den ikke — det er et symbol med to innganger, og verdien er alltid $1$, $-1$ eller $0$. Boka skriver det som brøk inne i alle utregninger, fordi det er formen løsningsforslagene bruker, og den korte formen $(a/p)$ i løpende prosa der plassen er trang.

Ett triks for å lese det riktig: tallet oppe er det du spør om, tallet nede er modulusen. Bytter du dem, spør du om noe helt annet — og hele resiprositetsloven i kap. 4.2 handler om nettopp hva som skjer når du bytter.

Utledes på stedet, tre linjer: avbildningen $x\mapsto x^2$ på de $p-1$ ikke-null restene treffer hver kvadratisk rest nøyaktig to ganger, siden $x^2\equiv y^2$ gir $p\mid(x-y)(x+y)$, altså $y\equiv\pm x$ etter Euklids lemma. Da må antall bilder være $\displaystyle \frac{p-1}{2}$.

Konsekvensen for Legendre-symbolet er en identitet du kan bli spurt om direkte:

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

fordi summen har like mange $+1$-er som $-1$-er.

Praktisk verdi: dette er kontrollen din når du lager en tabell. Har du funnet syv kvadratiske rester modulo $13$, har du regnet feil — det skal være seks.

Når $p\mid a$, er $\displaystyle \left(\frac{a}{p}\right)=0$.

Grunnen er at $a\equiv 0\pmod p$, og da har $x^2\equiv 0$ nøyaktig én løsning, nemlig $x\equiv 0$ — ikke to, som ellers. Tilfellet er altså kvalitativt annerledes, og derfor får det sin egen verdi.

Hvor det faktisk dukker opp på eksamen: midt i en reduksjonskjede. Reduserer du $\displaystyle \left(\frac{158}{79}\right)$ og finner at $158=2\cdot 79$, er svaret $0$ og du er ferdig — ingen resiprositet, ingen supplementsregel.

Fellen å kjenne: multiplikativiteten holder også når en faktor gir $0$, men da er hele produktet $0$. Skriv aldri $\displaystyle \left(\frac{a}{p}\right)=\pm 1$ uten å ha sjekket at $p\nmid a$ først. Sjekken tar to sekunder, og for de primtallene som brukes på eksamen ser du det med øyet.

Prosedyren for å regne ut $\displaystyle \left(\frac{a}{p}\right)$ med kriteriet:

1. Reduser $a$ modulo $p$ (periodisiteten i løkke 4). Regn aldri med et tall større enn $p$.
2. Regn eksponenten $\displaystyle m=\frac{p-1}{2}$.
3. Regn $a^m\bmod p$ med kvadrer-og-multipliser — binærutvikling av $m$, suksessive kvadrater, gang sammen. Potensen skal føres — den regnes ikke bort med et tastetrykk.
4. Les av: $1$ gir symbolet $+1$, og $p-1$ gir symbolet $-1$. Får du noe annet, har du regnet feil — det finnes ingen tredje mulighet.
5. Konkludér i ord: «altså har kongruensen to løsninger» eller «altså har kongruensen ingen løsning».

Når kriteriet er raskest: når $a$ eller $p$ er lite, når $a^{(p-1)/2}$ faller pent sammen (som når $a^2\equiv -1$), og alltid som uavhengig kontroll av en resiprositetskjede.

Når det ikke er raskest: for store $p$. Med $p=101$ er eksponenten $50$, og det er 5–6 kvadreringer med tresifrede tall. Da er resiprositetsloven i kap. 4.2 mye kortere. Steg 3 må sitte utenat som prosedyre, siden kalkulatoren under kode D ikke kan regne modulære potenser.

$$a\equiv b\pmod p\quad\Longrightarrow\quad \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).$$

Grunnen er at kongruensen $x^2\equiv a$ og kongruensen $x^2\equiv b$ er samme kongruens når $a\equiv b$ — de har nøyaktig de samme løsningene.

Regelen må sitte utenat, og den brukes som første og siste handling i hver utregning: reduser $a$ modulo $p$ før du gjør noe annet, og reduser igjen etter hvert resiprositetssteg i kap. 4.2.

Eksempel på hvor mye den sparer: $\displaystyle \left(\frac{94}{13}\right)$. Her er $94=7\cdot 13+3$, så
$$\left(\frac{94}{13}\right)=\left(\frac{3}{13}\right),$$
og $\displaystyle \left(\frac{3}{13}\right)$ er $1$ fordi $4^2=16\equiv 3$. Uten reduksjonen ville du regnet $94^6\bmod 13$.

Å ikke redusere først er en dokumentert felle. Den koster ikke bare tid: regner du videre med et stort $a$, får du store tall i faktoriseringen og en unødvendig lang kjede.

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

Utledes på stedet fra Eulers kriterium, én linje:
$$\left(\frac{ab}{p}\right)\equiv (ab)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\pmod p,$$
og siden begge sider er $\pm 1$ og $p>2$, er de like som tall og ikke bare kongruente.

Regelen må sitte utenat. Den er grunnen til at hele sjangeren er regnbar: faktoriser $a$, og regn ett lite symbol per primfaktor.

Fellen — symbolet er IKKE additivt. $\displaystyle \left(\frac{a+b}{p}\right)$ har ingenting å gjøre med $\displaystyle \left(\frac ap\right)+\left(\frac bp\right)$. Med $p=13$: $\displaystyle \left(\frac{3}{13}\right)=1$ og $\displaystyle \left(\frac{10}{13}\right)=1$, men $3+10=13\equiv 0$, så $\displaystyle \left(\frac{13}{13}\right)=0$ og ikke $2$. Det er en av de mest belagte feilene i sjangeren.

Konsekvenser du bør kunne lese av med én gang:

- Kvadrater faller bort: $\displaystyle \left(\frac{a^2b}{p}\right)=\left(\frac bp\right)$, siden $\displaystyle \left(\frac{a}{p}\right)^2=1$.
- Rest $\cdot$ rest $=$ rest, ikke-rest $\cdot$ ikke-rest $=$ rest, rest $\cdot$ ikke-rest $=$ ikke-rest — nøyaktig fortegnsregningen for $\pm 1$.

$$\left(\frac{a^2}{p}\right)=1,\qquad\text{og derfor}\qquad \left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right).$$

Utledes på stedet, én linje: multiplikativiteten gir $\displaystyle \left(\frac{a^2}{p}\right)=\left(\frac ap\right)^2$, og $(\pm 1)^2=1$.

Praktisk verdi: dette er tidsbesparelsen i faktoriseringssteget. Faktoriser $a$, og se bare på primfaktorene med odde eksponent — de med partall eksponent bidrar med $1$ og kan strykes med en gang.

Eksempel: $\displaystyle \left(\frac{45}{59}\right)$. Her er $45=3^2\cdot 5$, så
$$\left(\frac{45}{59}\right)=\left(\frac{3}{59}\right)^2\left(\frac{5}{59}\right)=\left(\frac{5}{59}\right).$$
Ett symbol i stedet for to, og det gjenstående er det minste.

Merk hvorfor $\displaystyle \left(\frac{a^2}{p}\right)=1$ ikke er en overraskelse: $a^2$ er et kvadrat, så kongruensen $x^2\equiv a^2$ har den åpenbare løsningen $x\equiv a$.

Kongruensen $x^2\equiv a\pmod p$ med $p\nmid a$ har nøyaktig to løsninger når $\displaystyle \left(\frac ap\right)=1$, og ingen når $\displaystyle \left(\frac ap\right)=-1$. Det finnes ingen mellomting.

Utledes på stedet, to linjer: er $x_0$ en løsning, er $-x_0\equiv p-x_0$ også en løsning, siden $(-x_0)^2=x_0^2$. Og de er ulike modulo $p$, for $x_0\equiv -x_0$ ville gitt $p\mid 2x_0$, umulig når $p$ er odde og $p\nmid x_0$. Er $y$ en tredje løsning, gir $x_0^2\equiv y^2$ at $p\mid(x_0-y)(x_0+y)$, og ved Euklids lemma er $y\equiv\pm x_0$.

Løsningene er alltid et $\pm$-par: $x\equiv x_0$ og $x\equiv p-x_0$.

Konklusjonsregelen må sitte utenat, og den må skrives ut. Fasitpraksisen i arkivet er at svaret på en F-oppgave er en setning, ikke et symbol: «Siden $\displaystyle \left(\frac{a}{p}\right)=1$, har kongruensen to løsninger modulo $p$.» Å svare «$1$» og stoppe er et sluttall uten konklusjon.

Den dokumenterte fellen: å skrive «én løsning». Det er feil, og det er en feil som er lett å gjøre når man har funnet den ene løsningen ved å prøve seg frem og glemmer speilingen.

Utledes på stedet — dette er selve eksempelet på en utledning du gjør i margen, og den tar under et halvt minutt:

Sett $a=-1$ i Eulers kriterium:
$$\left(\frac{-1}{p}\right)\equiv(-1)^{\frac{p-1}{2}}\pmod p.$$
Nå er $\displaystyle \frac{p-1}{2}$ partall nøyaktig når $p-1$ er delelig med $4$, altså når $p\equiv 1\pmod 4$ — og da er høyresiden $1$. Ellers er $\displaystyle \frac{p-1}{2}$ odde og høyresiden $-1$. Ferdig, tre linjer.

Så: må du kunne resultatet utenat? Du bør kunne det, fordi det sparer tid — men du trenger det ikke, og det er poenget. Kan du Eulers kriterium, har du regelen tilgjengelig når som helst. Det er slik hele Del 4 er bygget: få kort utenat, resten utledet på stedet.

Bruk: $p=29$ gir $29=7\cdot 4+1$, altså $p\equiv 1\pmod 4$ og $\displaystyle \left(\frac{-1}{29}\right)=1$ — kongruensen $x^2\equiv -1\pmod{29}$ har to løsninger. (De er $x\equiv 12$ og $x\equiv 17$, siden $12^2=144=5\cdot 29-1\equiv -1$.) Med $p=23$ er $23=5\cdot 4+3$, så $\displaystyle \left(\frac{-1}{23}\right)=-1$ og $x^2\equiv -1\pmod{23}$ er uløselig.

Praktisk grep: $\displaystyle \left(\frac{p-1}{p}\right)$ er det samme som $\displaystyle \left(\frac{-1}{p}\right)$, siden $p-1\equiv -1$. Ser du $p-1$ i telleren, bruk regelen — ikke faktoriser $p-1$.

$$\left(\frac{-a}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{a}{p}\right).$$

Oppskriften i praksis: trekk ut $-1$ som egen faktor, bruk supplementsregelen på den, og regn videre med det positive tallet.

Alternativet er ofte enklere: legg til $p$ til telleren blir positiv, siden symbolet bare avhenger av $a\bmod p$. For eksempel er
$$\left(\frac{-5}{17}\right)=\left(\frac{12}{17}\right)=\left(\frac{4}{17}\right)\left(\frac{3}{17}\right)=\left(\frac{3}{17}\right),$$
der $4=2^2$ falt bort som kvadrat.

Hvor det dukker opp: i oppgaver formulert som «har $x^2+5\equiv 0\pmod{17}$ løsning?». Det er $x^2\equiv -5$, og da er du her.

Kontrollregel: for $p\equiv 1\pmod 4$ er $a$ og $-a$ alltid av samme type (begge rester eller begge ikke-rester), fordi $\displaystyle \left(\frac{-1}{p}\right)=1$. For $p\equiv 3\pmod 4$ er de alltid av motsatt type. Det er en fin sjekk på at fortegnsarbeidet ble riktig.

Et tall $a$ med $p\nmid a$ som ikke er kongruent med noe kvadrat modulo $p$ — altså der $x^2\equiv a\pmod p$ er uløselig, og $\displaystyle \left(\frac ap\right)=-1$.

Det er nøyaktig $\displaystyle \frac{p-1}{2}$ av dem, like mange som det er kvadratiske rester.

Hvorfor begrepet trenger et eget navn: ikke-restene har egne regneegenskaper. To ikke-rester ganget sammen gir en rest (fortegnsregningen $(-1)(-1)=1$), mens en rest ganget med en ikke-rest gir en ikke-rest. Ikke-restene er altså ikke «restene som ble borte» — de er en like strukturert halvdel.

Språkbruk i besvarelsen: skriv «$a$ er en kvadratisk ikke-rest modulo $p$», ikke «$a$ er ikke en kvadratisk rest». Den første formen er den fasitene bruker, og den gjør konklusjonen tydeligere.

Koblingen fremover: i kap. 5.2 viser det seg at en primitiv rot modulo $p$ alltid er en kvadratisk ikke-rest — de to begrepene henger sammen gjennom Eulers kriterium.

$$\left(\frac{a}{p}\right)\qquad\text{og}\qquad (a/p).$$

Boka bruker brøkformen inne i alle utregninger og reduksjonskjeder, fordi det er formen løsningsforslagene bruker og fordi den gjør det lettere å se hvilket tall som er teller og hvilket som er modulus. Den korte formen brukes i løpende prosa der plassen er trang.

Regelen for din egen føring: hold én form gjennom en hel kjede. Bytter du frem og tilbake midt i en reduksjon, blir det vanskelig for leseren — og for deg selv — å følge hvilket symbol som ble snudd hvor.

Hva symbolet IKKE er: en brøk. Verdien er alltid $1$, $-1$ eller $0$, aldri noe imellom, og du kan ikke forkorte teller mot nevner. Ser du $\displaystyle \left(\frac{6}{3}\right)$ i en utregning, er det en skrivefeil — nevneren i et Legendre-symbol er alltid et odde primtall, og telleren blir aldri forkortet mot den.

Slektningen du ikke trenger: Jacobi-symbolet utvider notasjonen til sammensatte nevnere. Det er ikke pensum her, og du skal ikke bruke det — men det forklarer hvorfor du kan se $\displaystyle \left(\frac{a}{n}\right)$ med sammensatt $n$ i andre bøker.

Rekkefølgen du behandler et Legendre-symbol i. Den er den samme hver gang, og den må sitte utenat:

1. Reduser telleren modulo $p$ (periodisiteten). Er telleren negativ, legg til $p$ — eller trekk ut $-1$ som egen faktor.
2. Faktoriser telleren i primtall.
3. Splitt symbolet over faktorene (multiplikativiteten), og stryk alle faktorer med partall eksponent — de bidrar med $1$.
4. Regn hvert gjenstående lille symbol, med Eulers kriterium her i kap. 4.1, og med supplementsreglene og resiprositetsloven i kap. 4.2.

Deretter: konkludér i ord. Antall løsninger, ikke bare symbolverdien.

Hvorfor rekkefølgen er viktig og ikke bare ryddig: hvert steg gjør tallene mindre. Bytter du om på 1 og 2, faktoriserer du et større tall enn nødvendig. Hopper du over 3, regner du potenser av store tall. Under kode D er dette forskjellen mellom fem minutter og tjue.

Prosedyren for å regne $a^{(p-1)/2}\bmod p$ for hånd. Den er den samme malen som i kap. 2.1, brukt på en spesiell eksponent.

1. Skriv $\displaystyle m=\frac{p-1}{2}$ i binærform — for eksempel $11=1011_2=8+2+1$.
2. Lag tabellen over suksessive kvadrater $a^1,a^2,a^4,a^8,\dots$ modulo $p$, hver som kvadratet av den forrige.
3. Reduser etter HVER kvadrering. Aldri regn $a^8$ som et helt tall først; hold alt under $p$.
4. Gang sammen de potensene som svarer til ett-erne i binærutviklingen, og reduser mellom hver multiplikasjon.
5. Les av $1$ eller $p-1$.

Prosedyren må sitte utenat, for kalkulatoren du får bruke kan ikke regne modulære potenser.

To snarveier verdt å se etter, som ofte halverer arbeidet:

- Lander en potens på $-1$ (altså $p-1$), er alle høyere potenser gratis: $a^{2k}\equiv 1$, $a^{4k}\equiv 1$ og så videre.
- Er $\displaystyle \frac{p-1}{2}$ en toerpotens (som for $p=17$: $m=8$), består hele regningen av kvadreringer — ingen multiplikasjoner å holde styr på.

Begge metodene i dette kapitlet gir riktig svar. Valget er praktisk:

For små $p$ (opp til rundt $30$): prøv oppover. Kvadrer $x=1,2,3,\dots$ til du treffer $a$. Du trenger aldri gå lenger enn $\displaystyle \frac{p-1}{2}$, siden andre halvdel speiler seg. Og oppgi begge: $x\equiv x_0$ og $x\equiv p-x_0$.