4.3 Drill: Legendre-symbol og resiprositet

Hele Legendre-repertoaret drillet til automatikk: reduser (a/p) via multiplikativitet, supplementsregler og resiprositetsloven til et sikkert svar «to løsninger» eller «ingen løsning» — regnereglene som må sitte utenat under kode D.

75 min

13 oppgaver

DrillLegendre-symbolresiprositet

Din fremgang i kapitlet

0 / 13 oppgaver

Kapitlets plass i kurset

Bygger på

4.2Kvadratisk resiprositet og supplementsreglene

Brukes videre i

4.PPrøver til del 4: Kvadratiske rester og resiprositet

Dette kapitlet driller sjanger F, som forekommer i 10 av 15 sett — 67 %. Sjangerbokstavene er bokas forkortelser for oppgavetypene, forklart i kap. 0.1; F er kvadratiske rester og Legendre-symbolet.

Teorien står i kap. 4.1 og kap. 4.2. Her er poenget noe annet: at reduksjonen skal gå automatisk, uten at du tenker på reglene mens du bruker dem. Det er forskjellen mellom å ha lest kapitlet og å ta delpunktet på syv minutter i november.

Variantkatalogen du møter i arkivet, og som oppgavene under dekker:

Variant	Antall oppgaver her
Avgjør løsbarhet med resiprositetsloven	5
Symbol der supplementsreglene for $2$ eller $-1$ bærer svaret	3
Sammensatt teller med tre eller flere primfaktorer	2
Eulers kriterium som metode eller som kontroll	2
«Summér Legendre-symbolene» / tell restene	1

Prioritet: høyeste. Ingen annen sjanger i faget har et bedre forhold mellom drillet tid og sikret uttelling — apparatet er tre regler og en fast rekkefølge.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en enkel kalkulator. Kalkulatoren kan gange og dele med rest, men den kan ikke redusere et Legendre-symbol, og den kan ikke regne $a^{(p-1)/2}\bmod p$ for deg.

Må sitte utenat, og det er dette du driller inn her:

- reduksjonsalgoritmen i fem steg (reduser, faktoriser, splitt og stryk kvadrater, behandle hver faktor, gang sammen)
- resiprositetsloven med fortegnsbytte nøyaktig når $p\equiv q\equiv 3\pmod 4$
- supplementsregelen for $-1$ : $p\bmod 4$
- supplementsregelen for $2$ («8-regelen»): $p\bmod 8$ , med $+1$ for $p\equiv\pm 1$
- konklusjonsregelen: $1$ gir to løsninger, $-1$ gir ingen
- kvadrer-og-multipliser, som du trenger til Eulers kriterium

Utledes på stedet:

- $\displaystyle \left(\frac{-1}{p}\right)$ ut av Eulers kriterium — $(-1)^{(p-1)/2}$ , tre linjer
- $\displaystyle \left(\frac{a^2b}{p}\right)=\left(\frac bp\right)$ — kvadrater faller bort, én linje
- $\displaystyle \left(\frac a3\right)$ og $\displaystyle \left(\frac a5\right)$ — kvadrer restene modulo $3$ og $5$ ; fem sekunder, og du har avslutningen på kjeden
- at summen av alle symboler er $0$ — like mange $+1$ som $-1$

Selvtest, to minutter: dekk til boka og skriv ned de fem stegene i reduksjonsalgoritmen, og de to modulusene ( $4$ og $8$ ) knyttet til riktig supplementsregel. Nøler du på hvilken modulus som hører til hvilken regel, er det den ene tingen å drille før du går videre — det er den feilen som snur svaret.

Prosedyrer pugges ved å kjøres, ikke ved å leses. Tretten regnede symboler med lukket bok er mer verdt enn tretten gjennomlesninger.

Forkunnskaper

Hele Del 4: kap. 4.1 (definisjonen, multiplikativitet, periodisitet, Eulers kriterium) og kap. 4.2 (resiprositetsloven, supplementsreglene, reduksjonsalgoritmen). Du bør også ha faktorisering fra kap. 1.1 og kvadrer-og-multipliser fra kap. 2.1 i fingrene.

Sist du var her. De tre resultatene du skal bruke i hver eneste oppgave under, ferdig oppfrisket:

Resiprositetsloven, praktisk form. For ulike odde primtall:
$\left(\frac pq\right)=\begin{cases}-\left(\frac qp\right) & p\equiv q\equiv 3\pmod 4,\\ \ \ \,\left(\frac qp\right) & \text{ellers.}\end{cases}$

Supplementsreglene.
$\left(\frac{-1}{p}\right)=1\iff p\equiv 1\pmod 4,\qquad \left(\frac{2}{p}\right)=1\iff p\equiv\pm 1\pmod 8.$

Eulers kriterium.
$\left(\frac ap\right)\equiv a^{\frac{p-1}{2}}\pmod p,$
som du her mest bruker som uavhengig kontroll av en kjede.

Fra videregående kreves ingenting.

Løsningsoppskriften

~10 minutter. Les den, og bruk den som referanse mens du regner oppgavene — men legg den bort før du tar de siste fem.

Alle oppgavene i sjanger F går gjennom samme fem steg. Forskjellen mellom variantene ligger bare i steg 4: hvilken regel som gjelder for hvilken faktor.

Oppskrift: Legendre-symbol i fem steg

For $\displaystyle \left(\frac ap\right)$ med $p$ et odde primtall:

1. Margnotat. Skriv $p\bmod 4$ og $p\bmod 8$ . Du trenger begge, til hver sin regel.
2. Reduser telleren modulo $p$ . Er den negativ, legg til $p$ — eller behold $-1$ som egen faktor. Er $p\mid a$ , er svaret $0$ og du er ferdig.
3. Faktoriser telleren, splitt symbolet (multiplikativitet), og stryk alle faktorer med partall eksponent.
4. Behandle hver gjenstående faktor:
- $-1$ → supplementsregel 1, se $p\bmod 4$ ;
- $2$ → supplementsregel 2 (8-regelen), se $p\bmod 8$ ;
- odde primtall $q$ → snu med resiprositetsloven (fortegnsbytte bare hvis $q\equiv p\equiv 3\pmod 4$ ), og gå til steg 2 med det nye symbolet.
5. Tell minustegnene — partall gir $+1$ , oddetall gir $-1$ — og konkludér i ord: to løsninger eller ingen.

Oppskriften må sitte utenat. Steg 1 og steg 5 er de som glemmes: margnotatet fordi det virker overflødig (til du mister et fortegn), og konklusjonssetningen fordi symbolverdien føles som svaret. Begge er egne føringspoeng — instruksen på hvert eksamenssett er at alle svar skal begrunnes.

Tidsbudsjett: 6–8 minutter for en normal F-oppgave, av de ~24 minuttene et delpunkt har. Bruker du femten, er det nesten alltid fordi steg 2 ble hoppet over etter en snuing.

Oppskrift: Eulers kriterium som metode eller kontroll

Noen ganger er kriteriet raskeste vei, og alltid er det den beste kontrollen.

1. Reduser telleren modulo $p$ .
2. Eksponenten er $\displaystyle m=\frac{p-1}{2}$ . Skriv $m$ i binærform.
3. Suksessive kvadrater $a^1,a^2,a^4,a^8,\dots$ modulo $p$ , med reduksjon etter hver kvadrering.
4. Gang sammen de potensene som svarer til ett-erne i binærutviklingen, med reduksjon mellom hver multiplikasjon.
5. Les av: $1$ gir symbolet $+1$ , $p-1$ gir $-1$ . Noe annet er regnefeil.

Når kriteriet er raskest: når $p\le 30$ eller så, når en tidlig potens lander på $-1$ (da er resten gratis), og når $m$ er en toerpotens (da er det bare kvadreringer).

Når det ikke er raskest: for tresifrede primtall. Med $p=137$ er $m=68$ , og det er sju kvadreringer med tall opp mot $20\,000$ før reduksjon. Da bruker du reduksjonsalgoritmen — og kriteriet på én liten faktor som kontroll.

Merk at de to veiene er likeverdige og begge fullgode. Fasitpraksisen i arkivet honorerer dem likt. Si i besvarelsen hvilken du bruker, og bruk gjerne den andre til å kontrollere.

De fire kontrollpunktene

Under kode D er selvkontroll den eneste kontrollen du har — det finnes ingen fasit i rommet og ingenting å slå opp i. Disse fire tar til sammen under ett minutt.

1. Etter margnotatet: stemmer restene? Regn $p-4k$ og $p-8k$ på papiret, ikke i hodet. Er $83$ kongruent med $3$ eller $5$ modulo $8$ ? ( $3$ , siden $83=80+3$ .)

2. Etter hver snuing: ble telleren redusert? Er den nye telleren større enn den nye nevneren, har du glemt steg 2, og kjeden vil ikke ta slutt.

3. Før du ganger sammen: endte hvert delsymbol i $\pm 1$ ? Alt annet er regnefeil, ikke et nytt svar.

4. Til slutt: er antall minustegn talt riktig — både supplementsverdiene og fortegnsbyttene? Og står konklusjonen som en setning med antall løsninger?

Legg til to gratis kontroller:

- Kjedelengden: tresifrede primtall gir 3–5 snuoperasjoner. Blir kjeden på ti, er noe galt.
- Uavhengig vei: splitt telleren annerledes, eller regn ett lite symbol med Eulers kriterium. To veier til samme svar er det nærmeste en fasit du kommer på eksamensdagen.

Gjennomregnet eksamenscase

~15 minutter.

Her er en typisk F-oppgave med tre delpunkt, nøyaktig i den formen arkivet bruker. Underveis står margnotater som sier hva hvert steg gir uttelling for. De er destillert fra hvordan løsningsforslagene i arkivet fører sjangeren, og fra oppgaveinstruksen om at alle svar skal begrunnes.

— naturlig pausepunkt —

✏️Eksamenscase: to symboler og en telling

a) Regn ut

\displaystyle \left(\frac{30}{53}\right)

.
b) Avgjør om

x^2\equiv 42\pmod{61}

har løsning, og oppgi antall løsninger.
c) Hvor mange av tallene

1,2,\dots,60

er kvadratiske rester modulo

61

, og hva er

\displaystyle \sum_{a=1}^{60}\left(\frac{a}{61}\right)

Del a)

Steg 1: margnotat. $53=13\cdot 4+1$ , så $53\equiv 1\pmod 4$ . Og $53=6\cdot 8+5$ , så $53\equiv 5\pmod 8$ .

Steg 2: telleren $30<53$ , ingenting å redusere.

Steg 3: faktoriser og splitt (multiplikativitet). $30=2\cdot 3\cdot 5$ :
$\left(\frac{30}{53}\right)=\left(\frac{2}{53}\right)\left(\frac{3}{53}\right)\left(\frac{5}{53}\right).$

Steg 4, faktor 1 — 8-regelen. $53\equiv 5\pmod 8$ , som er en av de to indre restene:
$\left(\frac{2}{53}\right)=-1.$

Steg 4, faktor 2. $3\equiv 3\pmod 4$ , men $53\equiv 1\pmod 4$ , så ingen fortegnsfaktor (resiprositet):
$\left(\frac{3}{53}\right)=\left(\frac{53}{3}\right)=\left(\frac{2}{3}\right)=-1,$
der vi reduserte $53\equiv 2\pmod 3$ (periodisitet) og brukte 8-regelen på $\displaystyle \left(\frac 23\right)$ , siden $3\equiv 3\pmod 8$ .

Steg 4, faktor 3. $5\equiv 1\pmod 4$ , ingen fortegnsfaktor (resiprositet):
$\left(\frac{5}{53}\right)=\left(\frac{53}{5}\right)=\left(\frac{3}{5}\right),$
etter reduksjonen $53\equiv 3\pmod 5$ . Snu igjen: $3\equiv 3$ , men $5\equiv 1\pmod 4$ , så ingen fortegnsfaktor:
$\left(\frac{3}{5}\right)=\left(\frac{5}{3}\right)=\left(\frac{2}{3}\right)=-1.$

Steg 5: tell minustegnene. Tre minustegn — oddetall:
$\left(\frac{30}{53}\right)=(-1)(-1)(-1)=-1.$

a) Sluttsvar: $\displaystyle \left(\frac{30}{53}\right)=-1$ , så $30$ er en kvadratisk ikke-rest modulo $53$ og $x^2\equiv 30\pmod{53}$ har ingen løsning.

Sensorblikk på del a). Fire ting gir uttelling, og de gir det hver for seg. (1) Faktoriseringen og splittingen er skrevet ut — et symbol med sammensatt teller kan ikke snus, og at du vet det, vises her. (2) Hvert steg har et regelnavn. I denne sjangeren er regelnavnet begrunnelsen, og instruksen på hvert sett er at alle svar skal begrunnes. (3) Fortegnstellingen står eksplisitt: «tre minustegn, altså oddetall». Med tre faktorer er det lett å miste ett. (4) Konklusjonen er en setning om løsbarhet, ikke bare et symbol.
Merk også hva som ikke kreves: løsningene. Oppgaven spurte om symbolet.

Del b)

Steg 1: margnotat. $61=15\cdot 4+1$ , så $61\equiv 1\pmod 4$ . Og $61=7\cdot 8+5$ , så $61\equiv 5\pmod 8$ .

Steg 3: faktoriser og splitt. $42=2\cdot 3\cdot 7$ :
$\left(\frac{42}{61}\right)=\left(\frac{2}{61}\right)\left(\frac{3}{61}\right)\left(\frac{7}{61}\right).$

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

Faktor 2. $61\equiv 1\pmod 4$ , ingen fortegnsfaktor (resiprositet):
$\left(\frac{3}{61}\right)=\left(\frac{61}{3}\right)=\left(\frac 13\right)=1,$
etter reduksjonen $61\equiv 1\pmod 3$ .

Faktor 3. $61\equiv 1\pmod 4$ , ingen fortegnsfaktor (resiprositet):
$\left(\frac{7}{61}\right)=\left(\frac{61}{7}\right)=\left(\frac{5}{7}\right),$
etter reduksjonen $61\equiv 5\pmod 7$ . Snu igjen: $5\equiv 1\pmod 4$ , ingen fortegnsfaktor:
$\left(\frac{5}{7}\right)=\left(\frac{7}{5}\right)=\left(\frac{2}{5}\right)=-1$
ved 8-regelen, siden $5\equiv 5\pmod 8$ (og $7\equiv 2\pmod 5$ ).

Steg 5: tell. To minustegn — partall:
$\left(\frac{42}{61}\right)=(-1)\cdot 1\cdot(-1)=1.$

b) Sluttsvar: $\displaystyle \left(\frac{42}{61}\right)=1$ , så $42$ er en kvadratisk rest modulo $61$ , og kongruensen $x^2\equiv 42\pmod{61}$ har nøyaktig to løsninger modulo $61$ .

Kontroll: løsningene er $x\equiv 15$ og $x\equiv 46$ , siden $15^2=225=3\cdot 61+42\equiv 42$ ✓ og $46=61-15$ ✓.

Sensorblikk på del b). Her er det konklusjonen som er delpunktet. « $\displaystyle \left(\frac{42}{61}\right)=1$ » er et mellomsvar; spørsmålet var om kongruensen har løsning og hvor mange. Skriv «nøyaktig to løsninger modulo $61$ » — tallet to er det oppgaven ber om, og det er den setningen som lukker delpunktet.
Merk også at kontrollen med $15^2$ er tatt med for din del. Den er billig når tallet er lite, men den er ikke en del av besvarelsen — og på et tresifret primtall ville det tatt for lang tid å finne røttene.

Del c)

Antallet. Etter halvparten-regelen er nøyaktig $\displaystyle \frac{p-1}{2}$ av restene $1,\dots,p-1$ kvadratiske rester. Her er
$\frac{61-1}{2}=30.$
Altså er $30$ av tallene $1,\dots,60$ kvadratiske rester modulo $61$ (og de resterende $30$ er ikke-rester).

Begrunnelsen, skrevet ut: kvadreringen $x\mapsto x^2$ er to-til-en på de $60$ ikke-null restene, fordi $x$ og $61-x$ har samme kvadrat, og fordi $x^2\equiv y^2$ gir $61\mid(x-y)(x+y)$ , altså $y\equiv\pm x$ ved Euklids lemma. Et bilde av $60$ elementer under en to-til-en-avbildning har $30$ elementer.

Summen. Summen har $30$ ledd med verdi $+1$ og $30$ ledd med verdi $-1$ , altså
$\sum_{a=1}^{60}\left(\frac{a}{61}\right)=30\cdot 1+30\cdot(-1)=0.$

c) Sluttsvar: $30$ kvadratiske rester, og summen er $0$ .

Sensorblikk på del c). Dette delpunktet krever ingen regning — bare halvparten-regelen og en begrunnelse. Men begrunnelsen er hele uttellingen: « $30$ » alene er et sluttall uten metode. Skriv de to linjene om at kvadreringen er to-til-en. Det er en av de billigste poengene på hele settet, og det er ren gjengivelse fra utenat-listen.
Tidsbruk for hele oppgaven: del a) ~6 min, del b) ~6 min, del c) ~3 min. Til sammen godt innenfor de ~24 minuttene et delpunkt har — og det er slik en drillet F-oppgave skal føles.

Oppgavene

~40 minutter til sammen. Tretten oppgaver, gruppert etter variant.

Regn dem med penn og lukket bok. Det er den eneste treningsformen som ligner eksamen, og forskjellen mellom å ha lest oppskriften og å kunne den viser seg bare her.

Slik er de gruppert:

- Oppgave 1–2: supplementsreglene alene (oppvarming)
- Oppgave 3–7: løsbarhet med resiprositetsloven
- Oppgave 8–9: sammensatt teller med tre eller flere faktorer
- Oppgave 10–11: Eulers kriterium som metode
- Oppgave 12: «summér symbolene» og telling
- Oppgave 13: kjedet oppgave i eksamensform

Del dem gjerne over to økter. Oppgave 1–7 er én naturlig økt (~20 min), oppgave 8–13 en annen (~20 min).

— naturlig pausepunkt —

📝Oppgave 1

Regn ut symbolene under med supplementsreglene alene.

a) $\displaystyle \left(\frac{-1}{113}\right)$ og $\displaystyle \left(\frac{-1}{127}\right)$
b) $\displaystyle \left(\frac{2}{101}\right)$ og $\displaystyle \left(\frac{2}{107}\right)$

📝Oppgave 2

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

📝Oppgave 3

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

📝Oppgave 4

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

📝Oppgave 5

Avgjør om $x^2\equiv 10\pmod{89}$ har løsning, og oppgi løsningene.

📝Oppgave 6

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

📝Oppgave 7

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

📝Oppgave 8

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

📝Oppgave 9

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

📝Oppgave 10

Avgjør om $x^2\equiv 7\pmod{19}$ har løsning, først med Eulers kriterium og deretter med resiprositetsloven. Oppgi løsningene.

📝Oppgave 11

Bruk Eulers kriterium til å avgjøre om $13$ er en kvadratisk rest modulo $23$ , og oppgi løsningene av $x^2\equiv 13\pmod{23}$ hvis de finnes.

📝Oppgave 12

La $p=17$ .
a) Hvor mange av tallene $1,2,\dots,16$ er kvadratiske rester modulo $17$ ? Begrunn uten å lage tabellen.
b) Hva er $\displaystyle \sum_{a=1}^{16}\left(\frac{a}{17}\right)$ ? Begrunn.
c) Kontrollér a) ved å lage tabellen over kvadratiske rester.

📝Oppgave 13

a) Regn ut

\displaystyle \left(\frac{33}{71}\right)

med reduksjonsalgoritmen, ført med regelnavn.
b) Hvor mange løsninger har

x^2\equiv 33\pmod{71}

?
c) Kontrollér én av delfaktorene fra a) med Eulers kriterium.

Typiske feil

De fem feilene under er dokumentert i arkivets løsningsforslag som noe fasiten advarer mot. Fire av dem snur svaret helt — og du merker det ikke, for et galt $\pm 1$ ser like riktig ut som et riktig.

- Glemmer fortegnsfaktoren i resiprositetsloven. Den mest belagte feilen i sjangeren. Symptomet er at «to løsninger» og «ingen løsning» bytter plass. Motmiddelet: skriv begge primtallenes rest modulo $4$ ved hver snuing — også midt i kjeden, der tallene har skiftet. Se oppgave 3 og 13: der ble kjeden avgjort av fortegnsbokføringen.

- 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$ . Motmiddelet: skriv opp begge restene i margnotatet, 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. Glemmer du reduksjonen, vokser tallene og kjeden tar aldri slutt. Symptom: en kjede på over åtte steg.

- Snur et sammensatt tall. Resiprositetsloven gjelder for primtall. Faktoriser og splitt før du snur — se oppgave 7 og 9, der telleren måtte faktoriseres på nytt midt i kjeden.

- Paritetsfeil modulo $4$ eller $8$ . Er $107$ kongruent med $3$ eller $5$ modulo $8$ ? ( $3$ , siden $107=104+3$ .) Ren aritmetikk, men en reell feilkilde under tidspress. Motmiddelet: trekk fra nærmeste multiplum og skriv det ned; ikke gjør det i hodet.

Og to føringsfeil som koster uten å være regnefeil:

- Stopper ved symbolverdien. Oppgaven spør om løsbarhet eller antall løsninger. Skriv setningen.
- Leter etter løsningene når det ikke spørres. Å finne røttene modulo et tresifret primtall er en egen og mye tyngre jobb. Symbolet sier at de finnes, ikke hvor de er — og på et sett med ti delpunkt er den tiden dyr.

Prosedyrekort

Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 75 minutter gjelder oppskriften, casen og oppgavene.

Drillkapitlene har ingen begrepsbank i vanlig forstand. I stedet er kortene her oppskriftskort: hvert av dem er en prosedyre du skal kunne kjøre, ikke et faktum du skal kunne si.

Og det er slik de skal pugges: ikke ved å lese kortet, men ved å kjøre prosedyren på nye tall. Velg selv en teller på to siffer og et primtall mellom $50$ og $150$ , og regn. Et kort du har lest fem ganger, hjelper deg ikke 24. november. En prosedyre du har kjørt fem ganger, gjør det.

Kort: Legendre-symbol i fem steg

p\bmod 4

Kort: fortegnsbokføringen

\equiv 3\pmod 4

Kort: hvor kjeden stopper

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

Kort: Eulers kriterium for hånd

p

Kort: margnotatet

p\bmod 4

Rest	Brukes til
$p\bmod 4$	fortegnsfaktoren i resiprositeten, og $\displaystyle \left(\frac{-1}{p}\right)$
$p\bmod 8$	$\displaystyle \left(\frac 2p\right)$ (8-regelen)

Kort: tidsbudsjettet for sjanger F

Eksamen er 4 timer på rundt ti likt vektede delpunkt, altså ~24 minutter per delpunkt . En F-oppgave skal ligge godt under det. Arbeid Tid Margnotat + faktorisering ~1 min Kjeden, 3-5 snuoperasjoner med reduksjon ~4 min Fortegnstelling + konklusjonssetning ~1 min Kontroll (tell fortegn, evt. annen splitting) ~2 min Til sammen 6-8 minutter. Bruker du femten, er årsaken nesten alltid én av tre: manglende reduksjon mellom stegene, Eulers kriterium på et for stort primtall, eller leting etter løsninger som ikke ble etterspurt. Hva du IKKE skal bruke tid på: å finne røttene når oppgaven bare spør om løsbarhet, og å gjenskape beviset for resiprositetsloven. Konsekvensen for repetisjonsplanen din: dette er et delpunkt du kan gjøre nesten gratis hvis apparatet sitter — og som du taper helt hvis det ikke gjør det. Det finnes ingen halv vei gjennom en reduksjonskjede.

Arbeid	Tid
Margnotat + faktorisering	~1 min
Kjeden, 3–5 snuoperasjoner med reduksjon	~4 min
Fortegnstelling + konklusjonssetning	~1 min
Kontroll (tell fortegn, evt. annen splitting)	~2 min

Kort: tellings- og summeringsoppgaven

1,\dots,p-1

Kort: to veier, begge fullgode

p\approx 100

Reduksjonsalgoritmen	Eulers kriterium
Arbeid for $p\approx 100$	3–5 snuoperasjoner	6–7 kvadreringer med tresifrede tall
Arbeid for $p\approx 20$	2–3 snuoperasjoner	3–4 kvadreringer med små tall
Krever utenat	loven + to supplementsregler	eksponenten $\displaystyle \frac{p-1}{2}$
Feilkilde	glemt fortegnsfaktor	regnefeil i en kvadrering

Kort: selvdiagnose for Del 4

\displaystyle \left(\frac{-1}{p}\right)

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.