4.2 Kvadratisk resiprositet og supplementsreglene

Den kvadratiske resiprositetsloven (p/q)(q/p)=(−1)^… og supplementsreglene for (−1/p) og (2/p) — regnereglene som må automatiseres for å avgjøre løsbarhet effektivt, med hele reduksjonsmaskineriet.

60 min

9 oppgaver

Kvadratisk resiprositetsupplementsreglene

Din fremgang i kapitlet

0 / 9 oppgaver

Kapitlets plass i kurset

Bygger på

4.1Kvadratiske rester, Legendre-symbolet og Eulers kriterium

Brukes videre i

4.3Drill: Legendre-symbol og resiprositet

Dette er kjernen i sjanger F, som forekommer i 10 av 15 sett — 67 %. Sjangerbokstaven F er bokas forkortelse for oppgaver om kvadratiske rester og Legendre-symbolet; katalogen står i kap. 0.1.

Der kap. 4.1 ga deg definisjonen og Eulers kriterium, gir dette kapitlet regnemaskineriet: resiprositetsloven og de to supplementsreglene. Forskjellen i praksis er stor. Med Eulers kriterium alene tar $\displaystyle \left(\frac{66}{103}\right)$ omtrent tjue kvadreringer med tresifrede tall; med resiprositet tar den fire linjer.

Hvorfor dette er den tydelige karakterskilleren i settets andre halvdel: oppgaven er kort, oppskriften er mekanisk, og den som har drillet den, tar delpunktet på under ti minutter. Den som ikke har det, står helt fast — det finnes ingen delvis vei gjennom en resiprositetsreduksjon.

Slik oppgaven ser ut i arkivet: «Avgjør om $x^2\equiv a\pmod p$ har løsning», med $a$ på to eller tre siffer og $p$ et primtall i to- eller tresifret klasse. Noen ganger med et tillegg: «hvor mange løsninger har den?» eller «regn ut $\displaystyle \left(\frac ap\right)$ ».

Prioritet: høyeste. Hele apparatet er tre formler og en rekkefølge. Det er den korteste veien til et sikret delpunkt som finnes i dette emnet.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en enkel kalkulator. Dette kapitlet er det stedet i boka der kode D biter hardest. Resiprositetsloven med fortegnsfaktoren og de to supplementsreglene er nøyaktig den typen ting man ellers ville slått opp, og de finnes ikke i rommet 24. november.

Må sitte utenat:

- Resiprositetsloven $\displaystyle \left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$ , med fortegnsfaktoren
- den praktiske formen: symbolene er like, unntatt når BEGGE primtallene er $\equiv 3\pmod 4$ — da får du et fortegnsbytte
- supplementsregelen for $-1$ : $\displaystyle \left(\frac{-1}{p}\right)=1$ når $p\equiv 1\pmod 4$
- supplementsregelen for $2$ : $\displaystyle \left(\frac 2p\right)=1$ når $p\equiv\pm 1\pmod 8$ — «8-regelen»
- reduksjonsalgoritmen i fem steg (reduser, faktoriser, splitt, snu, gjenta)

Utledes på stedet:

- $\displaystyle \left(\frac{-1}{p}\right)$ ut av Eulers kriterium: $\displaystyle \left(\frac{-1}{p}\right)\equiv(-1)^{(p-1)/2}$ , som er $1$ nøyaktig når $\displaystyle \frac{p-1}{2}$ er partall, altså når $p\equiv 1\pmod 4$ . Tre linjer, under et halvt minutt. Utledningen står i løkke 2.
- fortegnsfaktoren i praktisk form: $\displaystyle (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$ er $-1$ nøyaktig når begge brøkene er odde, altså når $p\equiv q\equiv 3\pmod 4$ . Én linje.
- at $\displaystyle \left(\frac{a^2b}{p}\right)=\left(\frac bp\right)$ — kvadrater faller bort (kap. 4.1).

Merk hva som IKKE utledes på stedet: $\displaystyle \left(\frac 2p\right)$ . Beviset for den regelen (via Gauss' lemma) er for langt for eksamenstid, og den må derfor sitte utenat. Minnekroken er « $\pm 1$ modulo $8$ gir $+1$ » — de to restene som ligger inntil hverandre om nullpunktet.

Selvtest, fire minutter: dekk til boka og skriv ned resiprositetsloven, når fortegnsfaktoren er $-1$ , og de to supplementsreglene med riktig modulus ( $4$ for $-1$ , $8$ for $2$ ). Bytter du om på $4$ og $8$ , er det den feilen å drille bort — den er blant de mest belagte i sjangeren.

Forkunnskaper

Fra boka: kap. 4.1 (Legendre-symbolet, multiplikativitet, periodisitet, Eulers kriterium) er hele grunnlaget. Du bør også ha kap. 1.1 (primtallsfaktorisering) friskt, siden hvert steg begynner med å faktorisere en teller.

Sist du var her. De fire resultatene fra kap. 4.1 som dette kapitlet står helt på, ferdig oppfrisket:

Definisjonen. $\displaystyle \left(\frac ap\right)=1$ hvis $x^2\equiv a\pmod p$ har løsning, $-1$ hvis ikke, og $0$ hvis $p\mid a$ .

Periodisiteten. Symbolet avhenger bare av $a$ modulo $p$ :
$a\equiv b\pmod p\ \Longrightarrow\ \left(\frac ap\right)=\left(\frac bp\right).$

Multiplikativiteten. $\displaystyle \left(\frac{ab}{p}\right)=\left(\frac ap\right)\left(\frac bp\right)$ , og som følge av den faller kvadrater bort: $\displaystyle \left(\frac{a^2b}{p}\right)=\left(\frac bp\right)$ .

Eulers kriterium. $\displaystyle \left(\frac ap\right)\equiv a^{\frac{p-1}{2}}\pmod p$ — som du fortsatt bruker, men nå mest som uavhengig kontroll av kjeden.

Fra videregående kreves ingenting.

Å bytte spørsmålet med et enklere

Du står med $\displaystyle \left(\frac{13}{97}\right)$ : er $13$ et kvadrat modulo $97$ ? Eulers kriterium ville krevd $13^{48}\bmod 97$ — seks kvadreringer med tresifrede tall, og ingen mulighet for å oppdage en regnefeil underveis.

Resiprositetsloven sier at du kan bytte om på tallene. Spørsmålet «er $13$ et kvadrat modulo $97$ ?» har samme svar som spørsmålet «er $97$ et kvadrat modulo $13$ ?» — og det andre spørsmålet er mye enklere, for $97\equiv 6\pmod{13}$ , og da er du nede i ensifrede tall.

Det er et usedvanlig resultat. De to spørsmålene handler om helt ulike ting: det ene om restene modulo $97$ , det andre om restene modulo $13$ . At de har samme svar, er ikke opplagt, og Gauss selv kalte det «teorema aureum» — gullsetningen. Han ga åtte forskjellige bevis.

For deg er poenget praktisk: loven gjør symbolet rekursivt regnbart. Snu, reduser, faktoriser, snu igjen — og tallene krymper for hvert steg, helt til du sitter med noe du kan lese av direkte. En reduksjon som starter med tresifrede tall, er ferdig i fire–fem linjer.

Til dette trenger du tre ting: loven (løkke 1), de to supplementsreglene for $-1$ og $2$ , som er tilfellene loven ikke dekker (løkke 2), og en fast rekkefølge å gjøre stegene i (løkke 3). Deretter er resten drill.

Tidsanslag for kapitlet: ~60 minutter lesetid, fordelt på fem løkker à 9–14 minutter. Regner du med penn underveis — og her bør du — legg til omtrent halvparten.

Løkke 1: Resiprositetsloven

~13 minutter.

Loven forteller hva som skjer når du bytter om teller og nevner i et Legendre-symbol. Svaret er «ingenting» i tre av fire tilfeller — og et fortegnsbytte i det fjerde.

📜Den kvadratiske resiprositetsloven

For to ulike odde primtall

p

q

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

Siden hvert symbol er $\pm 1$ , kan loven leses som en regel for å snu:

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

Loven må sitte utenat, og den må navngis — løsningsforslagene skriver «etter den kvadratiske resiprositetsloven». Beviset er langt (Gauss' lemma og et gitterpunkt-telleargument) og er ikke pensum å gjengi; det du skal kunne, er å bruke loven feilfritt.

Fortegnsfaktoren i praktisk form — dette er den utgaven du regner med:

$\left(\frac{p}{q}\right)=\begin{cases}-\left(\frac{q}{p}\right) & \text{hvis } p\equiv q\equiv 3\pmod 4,\\[2mm] \ \ \,\left(\frac{q}{p}\right) & \text{ellers.}\end{cases}$

Utledes på stedet, én linje: produktet $\displaystyle \frac{p-1}{2}\cdot\frac{q-1}{2}$ er odde nøyaktig når begge faktorene er odde, og $\displaystyle \frac{p-1}{2}$ er odde nøyaktig når $p\equiv 3\pmod 4$ . Altså er fortegnet $-1$ bare i det ene tilfellet der begge primtallene er $\equiv 3\pmod 4$ .

Intuisjon for hvorfor loven er nyttig: den lar deg bytte et symbol med stor nevner mot ett med liten nevner. Etter byttet reduserer du telleren modulo den nye, lille nevneren (periodisiteten), og da er tallene plutselig små. Det er en nedstigning, og den stopper alltid.

Snu-regelen — den formen du bruker

\equiv 3\pmod 4

Hvorfor kjeden alltid stopper

\displaystyle \left(\frac qp\right)

✏️Ett snu-steg: (13/97)

Avgjør om $x^2\equiv 13\pmod{97}$ har løsning.

Steg 1: restene modulo $4$ .

13=3\cdot 4+1

, så

13\equiv 1\pmod 4

. Og

97=24\cdot 4+1

, så

97\equiv 1\pmod 4

. Minst ett er

\equiv 1

, altså ingen fortegnsfaktor.

Steg 2: snu, etter den kvadratiske resiprositetsloven.
$\left(\frac{13}{97}\right)=\left(\frac{97}{13}\right).$

Steg 3: reduser telleren (periodisiteten). $97=7\cdot 13+6$ , så $97\equiv 6\pmod{13}$ :
$\left(\frac{97}{13}\right)=\left(\frac{6}{13}\right).$

Steg 4: faktoriser og splitt (multiplikativiteten). $6=2\cdot 3$ :
$\left(\frac{6}{13}\right)=\left(\frac{2}{13}\right)\left(\frac{3}{13}\right).$

Steg 5: de to små symbolene. Fra kap. 4.1 har vi, ved Eulers kriterium, at $\displaystyle \left(\frac{2}{13}\right)=-1$ og $\displaystyle \left(\frac{3}{13}\right)=1$ . (Kontroll av den siste: $4^2=16\equiv 3\pmod{13}$ , så $3$ er en kvadratisk rest.)

Steg 6: sett sammen.
$\left(\frac{13}{97}\right)=(-1)\cdot 1=-1.$

Konklusjon i ord. Siden $\displaystyle \left(\frac{13}{97}\right)=-1$ , er $13$ en kvadratisk ikke-rest modulo $97$ , og kongruensen $x^2\equiv 13\pmod{97}$ har ingen løsning.

Sluttsvar: $\displaystyle \left(\frac{13}{97}\right)=-1$ ; ingen løsning.

Regn på arbeidsmengden, for den er hele argumentet for dette kapitlet. Med resiprositet: én snuoperasjon, én divisjon med rest, én faktorisering, to kjente symboler — fire linjer. Med Eulers kriterium alene: $13^{48}\bmod 97$ , altså seks kvadreringer og to multiplikasjoner med tall opp mot $10\,000$ før reduksjon. Begge er riktige, men bare den ene er behagelig under tidspress.

📝Oppgave 1

Skriv ned, for hvert av parene under, om resiprositetsloven gir fortegnsbytte eller ikke. Begrunn med restene modulo $4$ .

a) $\displaystyle \left(\frac{5}{101}\right)$
b) $\displaystyle \left(\frac{11}{79}\right)$
c) $\displaystyle \left(\frac{7}{61}\right)$

📝Oppgave 2

Regn ut $\displaystyle \left(\frac{7}{53}\right)$ med resiprositetsloven, og avgjør om $x^2\equiv 7\pmod{53}$ har løsning.

Løkke 2: De to supplementsreglene

~12 minutter.

Resiprositetsloven krever at begge tall er odde primtall. To tellere faller derfor utenfor: $-1$ og $2$ . De har hver sin regel, og de kalles supplementsreglene fordi de supplerer loven — uten dem stopper reduksjonen.

— naturlig pausepunkt —

Supplementsregel 1: (−1/p)

\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=\begin{cases}\ \ \,1 & \text{hvis } p\equiv 1\pmod 4,\\ -1 & \text{hvis } p\equiv 3\pmod 4.\end{cases}

Supplementsregel 2: (2/p) og 8-regelen

\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}=\begin{cases}\ \ \,1 & \text{hvis } p\equiv 1\ \text{eller}\ 7\pmod 8,\\ -1 & \text{hvis } p\equiv 3\ \text{eller}\ 5\pmod 8.\end{cases}

$p$	$p\bmod 8$	$\displaystyle \left(\frac 2p\right)$
$79$	$7$	$1$
$83$	$3$	$-1$
$89$	$1$	$1$
$53$	$5$	$-1$
$103$	$7$	$1$

Hvorfor de to tilfellene trenger egne regler

-1

✏️Supplementsreglene i bruk

Regn ut $\displaystyle \left(\frac{-1}{89}\right)$ , $\displaystyle \left(\frac{2}{83}\right)$ og $\displaystyle \left(\frac{2}{103}\right)$ , og avgjør for hver om den tilhørende kongruensen $x^2\equiv a\pmod p$ har løsning.

Første symbol: $\displaystyle \left(\frac{-1}{89}\right)$ . Her bruker vi supplementsregelen for

-1

, som ser på

p

modulo

4

. Vi har

89=22\cdot 4+1

, altså

89\equiv 1\pmod 4

, og dermed

\left(\frac{-1}{89}\right)=1.

Kongruensen

x^2\equiv -1\pmod{89}

har to løsninger. (Kontroll:

34^2=1156=13\cdot 89-1\equiv -1\pmod{89}

✓, så løsningene er

x\equiv 34

x\equiv 55

Andre symbol: $\displaystyle \left(\frac{2}{83}\right)$ . Nå er telleren $2$ , så vi bruker 8-regelen og ser på $p$ modulo $8$ . Vi har $83=10\cdot 8+3$ , altså $83\equiv 3\pmod 8$ , som er en av de to «indre» restene:
$\left(\frac{2}{83}\right)=-1.$
Kongruensen $x^2\equiv 2\pmod{83}$ har ingen løsning.

Tredje symbol: $\displaystyle \left(\frac{2}{103}\right)$ . Igjen 8-regelen: $103=12\cdot 8+7$ , altså $103\equiv 7\equiv -1\pmod 8$ , som gir $+1$ :
$\left(\frac{2}{103}\right)=1.$
Kongruensen $x^2\equiv 2\pmod{103}$ har to løsninger. (Kontroll: $38^2=1444=14\cdot 103+2\equiv 2$ ✓.)

Sluttsvar: $\displaystyle \left(\frac{-1}{89}\right)=1$ (to løsninger), $\displaystyle \left(\frac{2}{83}\right)=-1$ (ingen løsning), $\displaystyle \left(\frac{2}{103}\right)=1$ (to løsninger).

Merk at ingen av de tre krevde en eneste potensberegning — bare tre divisjoner med rest. Det er verdien av supplementsreglene, og det er grunnen til at $\displaystyle \left(\frac 2p\right)$ må sitte utenat: den erstatter et tungt regnestykke med en resttest.

📝Oppgave 3

Bruk supplementsreglene til å regne ut:

a) $\displaystyle \left(\frac{-1}{97}\right)$ og $\displaystyle \left(\frac{-1}{107}\right)$
b) $\displaystyle \left(\frac{2}{79}\right)$ og $\displaystyle \left(\frac{2}{53}\right)$
c) $\displaystyle \left(\frac{-2}{89}\right)$

Løkke 3: Reduksjonsalgoritmen

~13 minutter.

Nå har du alle delene. Det som gjør sjangeren mekanisk, er å gjøre dem i samme rekkefølge hver gang — for da krymper tallene monotont, og du kan kontrollere deg selv underveis.

Reduksjonsalgoritmen i fem steg

\displaystyle \left(\frac ap\right)

Føringsmalen for en F-oppgave

p

✏️Full reduksjon: (39/67)

Avgjør om $x^2\equiv 39\pmod{67}$ har løsning.

(i) Restene i margen.

67=16\cdot 4+3

, så

67\equiv 3\pmod 4

. Og

67=8\cdot 8+3

, så

67\equiv 3\pmod 8

(ii) Kjeden.

Telleren $39<67$ , så det er ingenting å redusere. Vi faktoriserer: $39=3\cdot 13$ , og splitter (multiplikativitet):
$\left(\frac{39}{67}\right)=\left(\frac{3}{67}\right)\left(\frac{13}{67}\right).$

Første faktor, $\displaystyle \left(\frac{3}{67}\right)$ . Her er $3\equiv 3$ og $67\equiv 3\pmod 4$ — begge $\equiv 3$ , så resiprositeten gir fortegnsbytte:
$\left(\frac{3}{67}\right)=-\left(\frac{67}{3}\right).$
Reduser telleren (periodisitet): $67=22\cdot 3+1$ , så $67\equiv 1\pmod 3$ :
$\left(\frac{3}{67}\right)=-\left(\frac{1}{3}\right)=-1,$
siden $\displaystyle \left(\frac 13\right)=1$ ( $1$ er alltid en kvadratisk rest).

Andre faktor, $\displaystyle \left(\frac{13}{67}\right)$ . Her er $13\equiv 1\pmod 4$ , så ikke begge er $\equiv 3$ — ingen fortegnsfaktor:
$\left(\frac{13}{67}\right)=\left(\frac{67}{13}\right).$
Reduser (periodisitet): $67=5\cdot 13+2$ , så $67\equiv 2\pmod{13}$ :
$\left(\frac{13}{67}\right)=\left(\frac{2}{13}\right).$
Nå er telleren $2$ , altså 8-regelen: $13=1\cdot 8+5$ , så $13\equiv 5\pmod 8$ , som gir $-1$ :
$\left(\frac{13}{67}\right)=-1.$

Sett sammen. To faktorer, begge $-1$ — altså et partall antall minustegn:
$\left(\frac{39}{67}\right)=(-1)\cdot(-1)=1.$

(iii) Konklusjon. Siden $\displaystyle \left(\frac{39}{67}\right)=1$ , er $39$ en kvadratisk rest modulo $67$ , og kongruensen $x^2\equiv 39\pmod{67}$ har to løsninger.

Kontroll ved å finne dem: $21^2=441=6\cdot 67+39\equiv 39\pmod{67}$ ✓. Løsningene er $x\equiv 21$ og $x\equiv 67-21=46\pmod{67}$ .

Sluttsvar: $\displaystyle \left(\frac{39}{67}\right)=1$ ; to løsninger, $x\equiv 21$ og $x\equiv 46\pmod{67}$ .

Tell stegene: to snuoperasjoner, to reduksjoner, én bruk av 8-regelen. Fem linjer arbeid, alle med tall under $70$ . Det er kode D-realistisk, og det er hva du skal kjenne igjen som «en normal F-oppgave».

📝Oppgave 4

Avgjør om $x^2\equiv 15\pmod{101}$ har løsning. Før kjeden med regelnavn ved hvert steg.

📝Oppgave 5

Avgjør om $x^2\equiv 14\pmod{71}$ har løsning.

📝Oppgave 6

Avgjør om $x^2\equiv 45\pmod{59}$ har løsning, og oppgi antall løsninger.

Løkke 4: Kjeder med tre faktorer

~12 minutter.

Eksamensoppgavene har typisk en teller som faktoriserer i to eller tre primtall, og et primtall $p$ i tresifret klasse. Da er kjeden 4–5 steg, og fortegnsbokføringen begynner å bety noe. Vi tar to slike, den siste på eksamensnivå og ført som en A-besvarelse.

— naturlig pausepunkt —

✏️Eksamensnivå: (66/103)

Avgjør om kongruensen $x^2\equiv 66\pmod{103}$ har løsning, og oppgi antall løsninger.

(i) Restene i margen.

103=25\cdot 4+3

, så

103\equiv 3\pmod 4

. Og

103=12\cdot 8+7

, så

103\equiv 7\pmod 8

. Vi trenger begge: telleren har faktoren

2

(ii) Kjeden.

Telleren er $66<103$ , og $66=2\cdot 3\cdot 11$ . Splitt (multiplikativitet):
$\left(\frac{66}{103}\right)=\left(\frac{2}{103}\right)\left(\frac{3}{103}\right)\left(\frac{11}{103}\right).$

Faktor 1: $\displaystyle \left(\frac{2}{103}\right)$ — 8-regelen. $103\equiv 7\equiv -1\pmod 8$ , altså
$\left(\frac{2}{103}\right)=1.$

Faktor 2: $\displaystyle \left(\frac{3}{103}\right)$ . Både $3\equiv 3$ og $103\equiv 3\pmod 4$ , så fortegnsbytte (resiprositet):
$\left(\frac{3}{103}\right)=-\left(\frac{103}{3}\right).$
Reduser (periodisitet): $103=34\cdot 3+1$ , så $103\equiv 1\pmod 3$ :
$\left(\frac{3}{103}\right)=-\left(\frac 13\right)=-1.$

Faktor 3: $\displaystyle \left(\frac{11}{103}\right)$ . Både $11\equiv 3$ og $103\equiv 3\pmod 4$ , så fortegnsbytte (resiprositet):
$\left(\frac{11}{103}\right)=-\left(\frac{103}{11}\right).$
Reduser (periodisitet): $103=9\cdot 11+4$ , så $103\equiv 4\pmod{11}$ :
$\left(\frac{11}{103}\right)=-\left(\frac{4}{11}\right)=-1,$
siden $4=2^2$ er et kvadrat og gir symbolet $1$ .

Sett sammen — tell minustegnene. Vi har to minustegn (fra faktor 2 og faktor 3), altså et partall:
$\left(\frac{66}{103}\right)=1\cdot(-1)\cdot(-1)=1.$

(iii) Konklusjon. Siden $\displaystyle \left(\frac{66}{103}\right)=1$ , er $66$ en kvadratisk rest modulo $103$ , og kongruensen $x^2\equiv 66\pmod{103}$ har nøyaktig to løsninger modulo $103$ .

Kontroll. Løsningene er $x\equiv 13$ og $x\equiv 90\pmod{103}$ : $13^2=169=103+66\equiv 66$ ✓, og $90=103-13$ ✓.

Sluttsvar: $\displaystyle \left(\frac{66}{103}\right)=1$ ; kongruensen har to løsninger.

Tre merknader om føringen, som er det som gir uttelling her.

Først: hvert steg har et navn. Instruksen på hvert eksamenssett er at alle svar skal begrunnes, og i denne sjangeren er regelnavnet begrunnelsen. « $\displaystyle \left(\frac{3}{103}\right)=-1$ » alene er et sluttall uten metode.

Dernest: fortegnstellingen står eksplisitt. Med to fortegnsbytter er det lett å miste ett, og å skrive «to minustegn, altså partall, altså $+1$ » er både raskere og lettere å kontrollere enn å gange fortegn linje for linje.

Til sist: oppgaven spurte ikke om løsningene. Å finne dem modulo $103$ er en helt annen og mye tyngre jobb enn å avgjøre løsbarheten — Legendre-symbolet sier at de finnes, ikke hva de er. Kontrollen over er tatt med for din del, ikke som en del av besvarelsen. Spør oppgaven bare om løsbarhet eller antall, stopper du ved konklusjonssetningen.

📝Oppgave 7

Avgjør om $x^2\equiv 35\pmod{73}$ har løsning. Før kjeden fullstendig, med regelnavn.

📝Oppgave 8

Avgjør om $x^2\equiv 34\pmod{83}$ har løsning.

Løkke 5: Reglene brukt på restklasser

~10 minutter.

En variant som dukker opp som bevisoppgave: i stedet for konkrete tall spør oppgaven om alle primtall av en gitt form. «For hvilke primtall $p$ er $3$ en kvadratisk rest?» Svaret er en betingelse modulo $12$ , og veien dit er de samme tre reglene — brukt på restklasser i stedet for tall.

✏️For hvilke primtall er 3 en kvadratisk rest?

Vis at for odde primtall $p>3$ er $\displaystyle \left(\frac 3p\right)=1$ nøyaktig når $p\equiv\pm 1\pmod{12}$ .

Vi regner

\displaystyle \left(\frac 3p\right)

med resiprositetsloven, og deler i to tilfeller etter

p\bmod 4

. Innenfor hvert tilfelle deler vi videre etter

p\bmod 3

, siden det er det som bestemmer telleren etter snuingen. Til sammen gir det fire tilfeller, og vi tar alle.

Tilfelle 1: $p\equiv 1\pmod 4$ . Da er ikke begge $\equiv 3$ , så resiprositeten gir ingen fortegnsfaktor:
$\left(\frac 3p\right)=\left(\frac p3\right).$
Nå er $\displaystyle \left(\frac p3\right)$ bestemt av $p\bmod 3$ , som er $1$ eller $2$ (ikke $0$ , siden $p>3$ er primtall):

- $p\equiv 1\pmod 3$ : $\displaystyle \left(\frac p3\right)=\left(\frac 13\right)=1$ .
- $p\equiv 2\pmod 3$ : $\displaystyle \left(\frac p3\right)=\left(\frac 23\right)=-1$ ved 8-regelen, siden $3\equiv 3\pmod 8$ .

Tilfelle 2: $p\equiv 3\pmod 4$ . Nå er begge $\equiv 3\pmod 4$ , så resiprositeten gir fortegnsbytte:
$\left(\frac 3p\right)=-\left(\frac p3\right).$

- $p\equiv 1\pmod 3$ : $\displaystyle \left(\frac 3p\right)=-\left(\frac 13\right)=-1$ .
- $p\equiv 2\pmod 3$ : $\displaystyle \left(\frac 3p\right)=-\left(\frac 23\right)=-(-1)=1$ .

Samle de fire tilfellene i en tabell.

$p\bmod 4$	$p\bmod 3$	$\displaystyle \left(\frac 3p\right)$	$p\bmod{12}$
$1$	$1$	$1$	$1$
$1$	$2$	$-1$	$5$
$3$	$1$	$-1$	$7$
$3$	$2$	$1$	$11$

Siste kolonne kommer fra det kinesiske restteoremet (kap. 2.4): restene modulo

4

og modulo

3

bestemmer til sammen resten modulo

12

entydig, siden

\gcd(3,4)=1

. For eksempel er det ene tallet som er

\equiv 1\pmod 4

\equiv 1\pmod 3

, nettopp

1

modulo

12

; og det som er

\equiv 3\pmod 4

\equiv 2\pmod 3

, er

11

.
Konklusjon. Symbolet er

1

nøyaktig i radene der

p\equiv 1

eller

p\equiv 11\pmod{12}

, altså nøyaktig når

p\equiv\pm 1\pmod{12}. \qquad\blacksquare

Kontroll med tall.

p=11

11\equiv 11\pmod{12}

, så

3

skal være en rest — og

5^2=25\equiv 3\pmod{11}

✓.

p=13

13\equiv 1\pmod{12}

, og

4^2=16\equiv 3\pmod{13}

✓.

p=17

17\equiv 5\pmod{12}

, så

3

skal ikke være en rest — restene modulo

17

\{1,2,4,8,9,13,15,16\}

, og

3

er ikke blant dem ✓.

p=19

19\equiv 7\pmod{12}

, så

3

skal ikke være rest — restene modulo

19

\{1,4,5,6,7,9,11,16,17\}

✓.
Legg merke til strukturen i beviset, for den er malen for hele denne oppgavetypen: uttømmende case-analyse. Fire tilfeller, alle behandlet, ingen hoppet over. En case-analyse som mangler en rest, er en byggefeil i et bevis — det samme kravet møter du igjen i Del 6.

Broen til primitive røtter

p

📝Oppgave 9

a) Vis at for odde primtall

p\ne 5

\displaystyle \left(\frac 5p\right)=1

nøyaktig når

p\equiv\pm 1\pmod 5

.
b) Bruk resultatet til å avgjøre om

x^2\equiv 5\pmod{89}

x^2\equiv 5\pmod{97}

har løsning.

Typiske feil

De fem feilene under er dokumentert i arkivets løsningsforslag som noe fasiten advarer mot. Fire av dem snur svaret helt.

- Glemmer fortegnsfaktoren i resiprositetsloven. Dette er den mest belagte feilen i sjangeren. Symptomet er at «to løsninger» og «ingen løsning» bytter plass, og du merker det ikke. Motmiddelet: skriv begge primtallenes rest modulo $4$ i margen før hver snuing, hver gang — også midt i en kjede, der tallene har skiftet.

- Forveksler de to supplementsreglene. $\displaystyle \left(\frac{-1}{p}\right)$ ser på $p\bmod 4$ ; $\displaystyle \left(\frac 2p\right)$ ser på $p\bmod 8$ . Bytter du modulusene, får du feil svar i omtrent halvparten av tilfellene. Motmiddelet: skriv opp både $p\bmod 4$ og $p\bmod 8$ når primtallet introduseres, og knytt hver til sin regel: « $4$ hører til $-1$ , $8$ hører til $2$ ».

- Reduserer ikke telleren mellom stegene. Etter en snuing er telleren typisk mye større enn den nye nevneren, og hele poenget med nedstigningen er å redusere den. Glemmer du det, vokser tallene i stedet for å krympe, og kjeden tar aldri slutt. Symptom: en kjede på over åtte steg.

- Faktoriserer ikke telleren først. Resiprositetsloven gjelder for primtall. Snur du $\displaystyle \left(\frac{15}{101}\right)$ direkte til $\displaystyle \left(\frac{101}{15}\right)$ , har du brukt loven på et sammensatt tall, og resultatet er ikke gyldig. Splitt alltid over faktorene først.

- Feil paritetsvurdering modulo $4$ eller $8$ . Er $83$ kongruent med $3$ eller $5$ modulo $8$ ? ( $3$ , siden $83=80+3$ .) Dette er ren aritmetikk, men under tidspress er det en reell feilkilde. Motmiddelet: trekk fra nærmeste multiplum av $8$ og skriv det ned; ikke gjør det i hodet.

Og en femte som er en føringsfeil, ikke en regnefeil: å stoppe ved symbolverdien. Oppgaven spør om løsbarhet eller antall løsninger. Skriv konklusjonssetningen — instruksen på hvert sett er at alle svar skal begrunnes, og et tall i $\{1,-1\}$ er ikke et svar på spørsmålet «har kongruensen løsning?».

Begrepsbank

Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 60 minutter gjelder kjernestoffet over.

Under kode D er banken eksamensverktøyet, ikke pynt. Dette kapitlet har det ene kortet i hele boka du er helt avhengig av å ha pugget — 8-regelen for $\displaystyle \left(\frac 2p\right)$ , siden beviset for den er for langt å gjenskape under eksamen. Resten kan i prinsippet utledes, men de er så billige å huske at det ville være sløsing å utlede dem.

Slik pugges de: faktakortene ved aktiv gjenkalling (dekk til, skriv ned, sjekk), og reduksjonsalgoritmen ved å kjøres på nye tall. Tre nye symboler regnet med lukket bok er mer verdt enn tre gjennomlesninger.

Fortegnsfaktoren, lest på tre måter

\displaystyle (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}

$p\bmod 4$	$q\bmod 4$	fortegn
$1$	$1$	$+$
$1$	$3$	$+$
$3$	$1$	$+$
$3$	$3$	$-$

De symbolene du kan lese av direkte

\displaystyle \left(\frac 1p\right)=1

Bokføringen av en kjede

\left(\frac{39}{67}\right)=\left(\frac{3}{67}\right)\left(\frac{13}{67}\right)\quad\text{(multiplikativitet)}

Kontroll av en kjede — tre måter

+1

Hvorfor du ikke skal snu et sammensatt tall

\displaystyle \left(\frac{15}{101}\right)=\left(\frac{101}{15}\right)

Å planlegge kjeden før du regner

p

Litt om loven selv

\displaystyle \left(\frac ap\right)

De generelle reglene for små tellere

\displaystyle \left(\frac ap\right)=1

Teller	$\displaystyle \left(\frac ap\right)=1$ nøyaktig når
$-1$	$p\equiv 1\pmod 4$
$2$	$p\equiv\pm 1\pmod 8$
$-2$	$p\equiv 1$ eller $3\pmod 8$
$3$	$p\equiv\pm 1\pmod{12}$
$5$	$p\equiv\pm 1\pmod 5$

Antall løsninger — hele svaret

x^2\equiv a\pmod p,\qquad p\ \text{odde primtall}

$\displaystyle \left(\frac ap\right)$	Antall løsninger	Løsningene
$1$	to	$x\equiv\pm x_0\pmod p$
$-1$	ingen	—
$0$ (altså $p\mid a$ )	én	$x\equiv 0\pmod p$

Tidsbudsjettet for en F-oppgave

p\bmod 4

Del av arbeidet	Tid
Skrive $p\bmod 4$ og $p\bmod 8$ , faktorisere telleren	~1 min
Kjeden, 3–5 snuoperasjoner med reduksjon	~4 min
Fortegnstelling og konklusjonssetning	~1 min
Kontroll (tell fortegn på nytt, evt. annen splitting)	~2 min

Når kongruensen ikke står på formen x²≡a

x^2+bx+c\equiv 0\pmod p,

Restmengden som en halvdel

p

Selvtesten for Del 4

\displaystyle \left(\frac ap\right)

Hvorfor snuing gjør tallene mindre

\displaystyle \left(\frac{13}{97}\right)

Steg	Symbol	Nevner
start	$\displaystyle \left(\frac{13}{97}\right)$	$97$
snu	$\displaystyle \left(\frac{97}{13}\right)$	$13$
reduser	$\displaystyle \left(\frac{6}{13}\right)$	$13$
splitt	$\displaystyle \left(\frac{2}{13}\right)\left(\frac{3}{13}\right)$	$13$

De fire innpakningene i arkivet

x^2\equiv a\pmod p

Repetisjonsoppgaver

Symbol- og formelliste

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.