5.4 Drill: orden, primitive røtter og tallteoretiske funksjoner
Den «øvre halvdelens» repertoar drillet: finn og verifiser orden, verifiser og generer primitive røtter, tell elementer av gitt orden, og regn τ/σ + minste-n-med-gitt-τ — sjangrene som skiller C fra A.
Teorien står i kap. 5.1–kap. 5.3. Her er poenget noe annet: at prosedyrene skal gå automatisk. Del 5 er den «øvre halvdelen» som skiller C fra A, og forskjellen ligger nesten alltid i om metoden sitter — ikke i om studenten forstår teorien.
Variantkatalogen du møter i arkivet, og som oppgavene under dekker:
| Variant | Antall oppgaver her |
|---|---|
| Finn ordenen med divisortesten | 3 |
| Verifiser en primitiv rot med primdivisortesten | 2 |
| Tell elementer av gitt orden, eller generer alle primitive røtter | 2 |
| Regn og fra faktoriseringen | 3 |
| Minste med gitt | 2 |
| Kjedet G+H-oppgave i eksamensform | 1 |
Prioritet: kunne. Dette er ikke stedet å starte om du har knapt med tid — de fem søylene (Del 1–3) kommer først. Men her ligger marginen mellom C og A, sammen med resiprositeten i kap. 4.2.
Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en enkel kalkulator. Den kan ikke regne , kan ikke faktorisere for deg, og kjenner ingen - eller -formler.
Må sitte utenat, og det er dette du driller inn her:
- divisortesten for orden: , list divisorene, test dem stigende
- ordenslemmaet
- primdivisortesten: for hver primdivisor av
- eksistenskriteriet
- antallene primitive røtter og elementer av orden
- og at , , er multiplikative
- minste--oppskriften: faktoriser måltallet, trekk fra , store eksponenter på små primtall
- kvadrer-og-multipliser, som ligger under alt potensarbeidet
Utledes på stedet:
- — Eulers teorem + ordenslemmaet, én linje
- — tre linjer
- — den geometriske summen, to linjer
- odde kvadrattall, og — to–tre linjer hver
Selvtest, tre minutter: dekk til boka og skriv ned de tre prosedyrene (divisortesten, primdivisortesten, minste--oppskriften) i stikkord. Klarer du å si hvor mange potenser hver av de to første krever, sitter kjernen — det er nettopp forskjellen mellom dem.
Prosedyrer pugges ved å kjøres, ikke ved å leses. Tretten regnede oppgaver med lukket bok er mer verdt enn tretten gjennomlesninger.
Forkunnskaper
Hele Del 5: kap. 5.1 (orden, ordenslemmaet, potensformelen), kap. 5.2 (primitive røtter, eksistens, telling) og kap. 5.3 (, , multiplikativitet, minste-). Du bør også ha fra kap. 2.1 og kvadrer-og-multipliser i fingrene.
Sist du var her. De fem resultatene du bruker i oppgavene under, ferdig oppfrisket:
Ordenslemmaet. , og spesielt .
Potensformelen. .
Primdivisortesten. er primitiv rot for hver primdivisor av .
Antallene. primitive røtter; elementer av orden .
og . og , begge fra faktoriseringen.
Fra videregående kreves ingenting.
Løsningsoppskriftene
~12 minutter. Les dem, og bruk dem som referanse mens du regner — men legg dem bort før du tar de siste fem oppgavene.
Del 5 har tre prosedyrer, ikke én. De ser like ut, men de svarer på ulike spørsmål og krever ulikt mye arbeid. Det er verdt å holde dem skarpt fra hverandre.
Oppskrift: finn ordenen (divisortesten)
For :
1. Sjekk og si det. Uten det finnes ingen orden.
2. Regn fra faktoriseringen av .
3. List divisorene av stigende.
4. Test dem stigende med kvadrer-og-multipliser. Første med er ordenen.
5. Konkludér: «, og de mindre divisorene ga ikke .»
Antall potenser: så mange divisorer du må gjennom — typisk 3–5, siden du stopper ved første treff.
Snarveien: lander en potens på , er ordenen det dobbelte av den eksponenten. Se etter tall rett under modulusen.
Oppskriften må sitte utenat. Steg 5 er det som glemmes, og «minste»-begrunnelsen er egne poeng — instruksen på hvert eksamenssett er at alle svar skal begrunnes.
Oppskrift: verifiser en primitiv rot (primdivisortesten)
For «er en primitiv rot modulo ?»:
1. Sjekk formen på : primitiv rot finnes bare for , , , . Er ikke slik, er svaret «finnes ikke».
2. Sjekk .
3. Regn og faktoriser den. List de ulike primdivisorene .
4. Regn for hver — én potens per primdivisor.
5. Konkludér: alle gir primitiv rot; én lik gir «nei».
Antall potenser: antall ulike primfaktorer i — nesten alltid eller . Det er derfor denne testen er billigere enn divisortesten, og forskjellen er hele poenget med å holde de to prosedyrene fra hverandre.
Gratis utelukkelse: en kvadratisk rest kan ikke være primitiv rot. Sjekk først — for avgjør 8-regelen (kap. 4.2) det på ett sekund.
Når testen feiler, les av informasjonen: er , deler ordenen , og du har innsnevret den gratis.
Oppskrift: τ, σ og minste n
For og :
1. Faktoriser . (Del ut , , , , , i tur og orden.)
2. — legg til på hver eksponent og gang sammen.
3. , der (summer direkte for små eksponenter).
4. Kontrollér: , og .
For «minste med »:
1. Faktoriser måltallet på alle måter i faktorer .
2. Eksponentene er for hver faktorisering.
3. Sorter synkende og plasser på — store eksponenter på små primtall.
4. Regn ut alle kandidatene og velg den minste.
5. Kontrollér ved å regne av svaret.
Begge oppskriftene må sitte utenat. Merk at -oppgaver er blant de raskeste delpunktene i hele faget: fem minutter når faktoriseringen går greit.
De fem kontrollpunktene
Under kode D er selvkontroll den eneste kontrollen du har. Disse fem tar til sammen under ett minutt.
1. Deler ordenen ? Alltid. Får du noe annet, er det regnefeil, ikke et nytt svar.
2. Er ? Eulers teorem krever det. En rask sjekk på slutten av en ordensoppgave.
3. Er alle primdivisorene testet? Tell dem: antall tester = antall ulike primfaktorer i . Én test er nesten aldri nok.
4. Summerer -ene til ? er fullstendighetskontrollen på enhver telling av elementer etter orden.
5. Gir kandidaten riktig ? I minste--oppgaven: regn av svaret ditt og se at du får måltallet.
Legg til to gratis grovkontroller:
- alltid (for ), og .
- — for er , og ✓.
Gjennomregnet eksamenscase
~15 minutter.
Her er en typisk Del 5-oppgave med fire delpunkt som bygger på hverandre — G og H kombinert, 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 —
La .
a) Vis at er en primitiv rot modulo .
b) Hvor mange primitive røtter finnes modulo ?
c) Hvor mange elementer har orden modulo ?
d) Regn ut og , og forklar hvorfor er relevant for delpunkt a).
Del a)
Steg 1: formen på modulusen. er et primtall, altså på formen med — så en primitiv rot finnes.
Steg 2: vilkåret. , siden er primtall og .
Steg 3: og faktoriseringen.
De ulike primdivisorene er og , så vi skal regne to potenser:
Steg 4: regn dem. Vi bygger opp de suksessive kvadratene, og bruker små representanter der vi kan:
| potens | utregning | verdi mod |
|---|---|---|
Test 1 (): ✓
Test 2 (): ✓
Steg 5: konklusjon. Begge testene er bestått, så ved primdivisortesten er
og er en primitiv rot modulo .
Sensorblikk på del a). Fire ting gir uttelling, hver for seg. (1) Faktoriseringen står skrevet — det er den som forklarer hvorfor nettopp og er de riktige eksponentene. (2) Begge primdivisorene er testet. Én test alene ville vært ufullstendig, og det er den best belagte feilen i sjangeren. (3) Testen er navngitt («ved primdivisortesten»). (4) Konklusjonen står som en setning med ordenen oppgitt.
Merk også at er nøyaktig som forventet: er en kvadratrot av , og modulo et primtall er kvadratrøttene av bare . Får du noe annet i den raden, er det regnefeil.
Del b)
Antall primitive røtter er
Med og multiplikativiteten (kap. 2.1):
Det finnes primitive røtter modulo , av rester i alt.
Sensorblikk på del b). Dette delpunktet er gratis når formelen sitter: to linjer, ingen potensberegning. Men «» alene er et sluttall uten metode — utregningen av er begrunnelsen, og den skal stå.Den vanlige feilen her er å svare . Det er antall rester, ikke antall primitive røtter.
Del c)
Ordenen deler , så tellingsteoremet gjelder: antall elementer av orden er . Med :
Seks elementer har orden modulo .
(Vil man ha dem, er de med , altså — og fra tabellen i a).)
Sensorblikk på del c). To ting kreves: at sjekkes (ellers finnes ingen slike elementer), og at formelen brukes — ikke selv. Å svare «» i stedet for «» er den dokumenterte fellen.
Del d)
og fra faktoriseringen :
Kontroll: divisorene i er — ni stykker ✓ (og et oddetall, som det skal være for et kvadrattall). Summen er ✓.
Hvorfor er relevant for a): tallet er nøyaktig antall divisorer av , altså antall mulige ordener modulo — og dermed antall potenser en full divisortest (kap. 5.1) ville krevd i verste fall.
Primdivisortesten trengte bare to. Forholdet mot er hele gevinsten ved å bruke den riktige prosedyren, og det er derfor de to skal holdes fra hverandre.
Sluttsvar: a) er en primitiv rot, med orden ; b) ; c) ; d) og , og er antall mulige ordener — mot to tester i primdivisortesten.
Sensorblikk på hele oppgaven. Tidsbruk: a) ~8 min, b) ~2 min, c) ~2 min, d) ~3 min — til sammen ~15 minutter for fire delpunkt. Det er slik en drillet Del 5-oppgave skal føles: ett tungt delpunkt med potensregning, og tre nesten gratis når formlene sitter.
Legg merke til at delpunkt b), c) og d) ikke krevde en eneste ny potensberegning. Det er det typiske mønsteret i sjangeren, og det er grunnen til at tellingsformlene er verdt å pugge selv om de ser trivielle ut.
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.
Slik er de gruppert:
- Oppgave 1–3: finn ordenen (divisortesten)
- Oppgave 4–5: verifiser en primitiv rot (primdivisortesten)
- Oppgave 6–7: telling og generering
- Oppgave 8–10: og
- Oppgave 11–12: minste med gitt
- Oppgave 13: kjedet G+H-oppgave i eksamensform
Del dem gjerne over to økter. Oppgave 1–7 er én naturlig økt (~22 min), oppgave 8–13 en annen (~18 min).
— naturlig pausepunkt —
Finn .
Finn .
b) Bruk svaret til å finne resten når deles på .
c) Hva er perioden i desimalutviklingen av ?
Vis at er en primitiv rot modulo .
Vis at er en primitiv rot modulo .
Bruk at er en primitiv rot modulo (oppgave 5).
a) Hvor mange primitive røtter finnes modulo ?
b) Hvor mange elementer har orden modulo ?
c) Finn dem.
Det er oppgitt at er en primitiv rot modulo .
a) Hvor mange primitive røtter finnes modulo ?
b) Finn dem alle.
Finn og .
Finn og .
b) Kommentér noe uventet i svarene.
Finn det minste positive heltallet med .
b) Sammenlign med svaret i oppgave 11 og forklar forskjellen.
La .
a) Vis at er en primitiv rot modulo .
b) Hvor mange primitive røtter finnes modulo ?
c) Hvor mange elementer har orden modulo ?
d) Regn ut og , og si hva betyr for hvor mange mulige ordener det finnes modulo .
De seks feilene under er dokumentert i arkivets løsningsforslag som noe fasiten advarer mot.
- Ordenen ikke verifisert som den minste. Å vise for én er ikke nok. Test divisorene stigende, og skriv setningen om at de mindre ble utelukket. Se oppgave 1–3: alle tre har den setningen med.
- Primitiv rot konkludert uten at alle primdivisorene er testet. Antall tester = antall ulike primfaktorer i . Skriv opp eksponentlisten før du regner, så du ser hvor mange du skal ha. I oppgave 5 var det tre.
- i stedet for . Den best belagte feilen i sjanger H. Kontrollen: skal være .
- Feil primtallsfordeling i minste--oppgaven. Største eksponent på minste primtall. , men mye større — samme , uspiselig tall.
- Teller elementer av gitt orden som i stedet for . Modulo har elementer orden — ikke . Kontrollen: summér over divisorene av og se at du får .
- Bruker multiplikativiteten uten . Gjelder både , og . .
Og to arbeidsvaner som koster tid uten å være feil:
- Å kjøre full divisortest når primdivisortesten holder. De to prosedyrene svarer på ulike spørsmål: «hva er ordenen?» krever divisortesten, «er ordenen maksimal?» krever bare primdivisortesten. Forskjellen kan være seks potenser mot to.
- Å regne potenser med store tall. Bruk små representanter: gjør kvadreringen mye lettere enn .
Prosedyrekort
Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 75 minutter gjelder oppskriftene, 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 et primtall mellom og og et tall , og regn. Et kort du har lest fem ganger, hjelper deg ikke 24. november.
2. Regn .
3. List divisorene stigende.
4. Test dem stigende med kvadrer-og-multipliser; første er ordenen.
5. Konkludér: «; de mindre divisorene ga ikke .»
Snarveier: bygg hver potens på den forrige; se etter (da er ordenen det dobbelte); stopp ved første treff.
Kontroller: deler svaret ? Er ?
Antall potenser: 3–5 typisk.
Kjør den nå, på og , uten å se på oppskriften. (Svar: med divisorer . Testene gir , , , , og — ordenen er . For : , og , så .)
2. ?
3. Regn , faktoriser den, og list de ulike primdivisorene .
4. Regn for hver — én potens per primdivisor.
5. Alle ⟹ primitiv rot. Én ⟹ nei (og ordenen deler den eksponenten).
Antall potenser = antall ulike primfaktorer i . Nesten alltid eller .
Gratis utelukkelse: er , kan ikke være primitiv rot. For : 8-regelen.
Planlegging som halverer arbeidet: velg en mellompotens du kan gjenbruke. For er alle tre eksponentene (, , ) bygget lett på og .
Forventet mønster ved «ja»: testen for gir .
Kjør den nå, på , , uten å se. (Svar: ; test og . ✓, og ✓ — altså primitiv rot.)
Alle tre er gratis når formlene sitter — ingen potensberegning.
Fullstendighetskontrollen:
Konstruksjonene:
- ett element av orden : ;
- alle av orden : potensene av det med eksponent relativt primisk til ;
- alle primitive røtter: med .
Vilkåret: tellingsformelen for orden krever at har en primitiv rot. Modulo gjelder den ikke.
De vanlige fellene: å svare i stedet for , og i stedet for .
Kjør dem nå, for : (Svar: ; primitive røtter ; mulige ordener ; elementer av orden : ; kontroll ✓.)
Arbeidsflyten: faktoriser → regn per primtallspotens → gang sammen → kontrollér.
-verdier verdt å kjenne igjen:
Kontrollene: ; ; ; odde kvadrattall.
Vilkåret for multiplikativitet: . Alltid.
Kjør dem nå, på og . (Svar: gir og . Og gir og .)
2. Eksponentene er .
3. Sorter synkende; største eksponent på , neste på , så , .
4. Regn ut alle kandidatene; velg minste.
5. Kontrollér av svaret.
Fasit for de vanlige måltallene:
| minste |
Mønsteret: store primfaktorer i tvinger store eksponenter og dermed store svar ( gir , mens gir ). Er et primtall , er svaret entydig .
Vanligste feil: å glemme en faktorisering av , eller å plassere eksponentene feil.
Kjør oppskriften nå, på . (Kandidater blant andre , , ; minste er .)
Den ene tingen som skiller en effektiv besvarelse fra en treg: å velge riktig prosedyre.
| Spørsmålet | Prosedyre | Antall potenser |
|---|---|---|
| «Hva er ordenen til ?» | divisortesten (alle divisorer, stigende) | 3–5 |
| «Er en primitiv rot?» | primdivisortesten (én per primdivisor) | 2–3 |
| «Hvor mange har orden ?» | tellingsformelen | 0 |
Poenget: primdivisortesten svarer bare på om ordenen er maksimal — den gir deg ikke ordenen når svaret er nei (bare en innsnevring). Divisortesten gir ordenen, men koster mer.
Og tellingsspørsmålene krever ingen regning i det hele tatt. Det er verdt å merke seg under tidspress: de er gratis poeng.
Feil valg av prosedyre er den vanligste grunnen til at et Del 5-delpunkt tar femten minutter i stedet for åtte.
Sjekk deg selv: hvilken prosedyre til «vis at har orden modulo »? (Svar: her er , så det er primitiv-rot-spørsmålet i forkledning — bruk primdivisortesten, tre potenser, ikke åtte.)
Den enkeltvanen som sparer mest tid i potensregningen: erstatt en rest med sin negative motpart når den er nær modulusen.
Regelen: er , skriv , altså et negativt tall med liten absoluttverdi.
Eksempler fra dette kapitlet:
| I stedet for | Skriv | Kvadratet blir |
|---|---|---|
| i stedet for | ||
| i stedet for | ||
| i stedet for | ||
| i stedet for |
Gevinsten: tallene du kvadrerer, holder seg under i absoluttverdi, så produktene blir små nok å regne i hodet. Under kode D, med bare en enkel kalkulator, er det forskjellen mellom fem og femten minutter på en primdivisortest.
Og fortegnet er gratis informasjon: ender du på , har du enten funnet ordenen (snarveien) eller bestått -testen. Begge er ting du vil se.
Vanen å legge til seg: skriv resten som negativ med en gang du får et tall over , i stedet for å bære det med deg.
Eksamen er 4 timer på rundt ti likt vektede delpunkt, altså ~24 minutter per delpunkt.
| Oppgavetype | Tid |
|---|---|
| Finn ordenen | ~8 min |
| Verifiser en primitiv rot (2–3 tester) | ~7 min |
| Tell primitive røtter / elementer av orden | ~2 min |
| Finn elementene av orden | ~6 min |
| og av et firesifret tall | ~5 min |
| Minste med gitt | ~7 min |
| Kjedet G+H-oppgave (4 delpunkt) | ~15 min |
Merk hvor billige tellespørsmålene er. De er ren gjengivelse av og — to minutter hver, og ubesvarelige uten formelen. Det er den beste avkastningen på pugging i hele Del 5.
Hvor tiden går galt: i potensberegningene (bruk små representanter) og i valg av prosedyre (primdivisortesten når spørsmålet er «er ordenen maksimal?»).
Realistisk forventning: en drillet Del 5-oppgave med fire delpunkt tar ~15 minutter, der ett delpunkt er tungt og tre er nesten gratis.
Sitter Del 5? Dekk til boka, sett fem minutter, og svar:
- ☐ Hva er definisjonen av , og hvilket vilkår kreves?
- ☐ Hva sier ordenslemmaet, begge veier?
- ☐ Hvorfor deler ordenen ?
- ☐ Hva er de fem stegene i divisortesten?
- ☐ Hva er primdivisortesten, og hvor mange potenser krever den?
- ☐ For hvilke finnes primitive røtter?
- ☐ Hvor mange primitive røtter, og hvor mange elementer av orden ?
- ☐ Hva er -formelen, og hva er ?
- ☐ Hva er de fire stegene i minste--oppskriften?
- ☐ Hva er fullstendighetskontrollen på en ordenstelling?
Ti spørsmål. Det er hele Del 5.
Står mer enn tre åpne: gå tilbake til teorikapitlene (kap. 5.1–kap. 5.3) og les løkkene på nytt før du tar prøvene i kap. 5.P.
Står tre eller færre åpne: hopp rett til prøvene. Du lærer mer av å regne dem under tidspress enn av å lese kapitlene en tredje gang.
Og uansett: regn tre nye ordener og verifiser to nye primitive røtter med lukket bok. Prosedyrer pugges ved å kjøres.
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.