Læringsmål

Oversikt over læringsmål dekket i MA1301 Tallteori

Kilde: Læringsmålene er utformet av Skolesaga på grunnlag av emnets eksamensoppgaver, sensorveiledninger og emnebeskrivelse. De er ikke institusjonens offisielle læringsutbyttebeskrivelser.

155 kompetansemål39 av 39 kapitler har kompetansemål

Alle kompetansemål

•gjøre rede for hvordan MA1301 vurderes: én skriftlig eksamen på fire timer der alle svar skal begrunnes
0.1Eksamenskartet: fem søyler, fast dramaturgi, alt begrunnes
•forklare hva hjelpemiddelkoden i emnet innebærer, og hvorfor den krever at apparatet sitter i hodet
0.1Eksamenskartet: fem søyler, fast dramaturgi, alt begrunnes
•prioritere lesingen etter hvor ofte temaene faktisk forekommer i arkivet
0.1Eksamenskartet: fem søyler, fast dramaturgi, alt begrunnes
•planlegge de fire timene på eksamen ut fra at delpunktene teller likt
0.1Eksamenskartet: fem søyler, fast dramaturgi, alt begrunnes
•avgjøre om et tall deler et annet, og begrunne det ut fra definisjonen
1.1Delelighet, primtall og aritmetikkens fundamentalteorem
•bruke divisjonsalgoritmen til å finne kvotient og rest, også for negative tall
1.1Delelighet, primtall og aritmetikkens fundamentalteorem
•faktorisere et tall i primtall med prøvedivisjon, og avgjøre om et tall er et primtall
1.1Delelighet, primtall og aritmetikkens fundamentalteorem
•finne største felles divisor og minste felles multiplum fra primtallsfaktoriseringen, og kontrollere svaret med produktregelen
1.1Delelighet, primtall og aritmetikkens fundamentalteorem
•kjøre Euklids algoritme som divisjonskjede og lese av største felles divisor
1.2Euklids algoritme frem og baklengs (Bézout)
•gjøre rede for hvorfor algoritmen virker, ut fra at gcd er uendret når man erstatter et tall med resten
1.2Euklids algoritme frem og baklengs (Bézout)
•skrive største felles divisor som en kombinasjon av de to opprinnelige tallene ved substitusjon baklengs
1.2Euklids algoritme frem og baklengs (Bézout)
•vise at to uttrykk med en ukjent er relativt primiske ved å presentere tallet 1 som en kombinasjon av dem
1.2Euklids algoritme frem og baklengs (Bézout)
•avgjøre om en likning av typen ax+by=c har heltallsløsninger, og begrunne svaret
1.3Lineære diofantiske likninger (ax + by = c)
•finne én løsning ved å skalere opp resultatet fra Euklids algoritme baklengs
1.3Lineære diofantiske likninger (ax + by = c)
•skrive hele løsningsmengden med en fri parameter, og kontrollere den ved innsetting
1.3Lineære diofantiske likninger (ax + by = c)
•finne den minste positive løsningen og alle løsninger i et gitt intervall
1.3Lineære diofantiske likninger (ax + by = c)
•regne med kongruenser og redusere store uttrykk underveis ved hjelp av regnereglene
1.4Lineære kongruenser (ax ≡ b mod m)
•avgjøre om en kongruens av typen ax ≡ b er løsbar, og hvor mange løsninger den har
1.4Lineære kongruenser (ax ≡ b mod m)
•forkorte en kongruens riktig, med den nødvendige betingelsen på modulusen
1.4Lineære kongruenser (ax ≡ b mod m)
•finne den modulære inversen med Euklids algoritme baklengs og bruke den til å løse kongruensen
1.4Lineære kongruenser (ax ≡ b mod m)
•kjøre Euklids algoritme frem og baklengs på firesifrede tall uten å se på oppskriften
1.5Drill: Euklid, diofant og lineær kongruens
•løse en diofantisk likning fullstendig, med løsbarhetskommentar og hele løsningsmengden
1.5Drill: Euklid, diofant og lineær kongruens
•løse en lineær kongruens og oppgi alle inkongruente løsninger modulo den opprinnelige modulusen
1.5Drill: Euklid, diofant og lineær kongruens
•kontrollere eget arbeid på alle stegene, siden det ikke finnes hjelpemidler å slå opp i på eksamen
1.5Drill: Euklid, diofant og lineær kongruens
•gjennomføre Euklids algoritme frem og baklengs under tidspress, med fullstendig føring
1.PPrøver til del 1: Delelighet, Euklids algoritme og diofantiske likninger
•løse en diofantisk likning fullstendig: løsbarhet kommentert, hele løsningsmengden, og løsninger i et gitt intervall
1.PPrøver til del 1: Delelighet, Euklids algoritme og diofantiske likninger
•løse en lineær kongruens og oppgi alle inkongruente løsninger, med modulusen riktig behandlet ved forkorting
1.PPrøver til del 1: Delelighet, Euklids algoritme og diofantiske likninger
•kjede sammen flere teknikker i én oppgave, slik oppgave 1 er bygget på eksamen
1.PPrøver til del 1: Delelighet, Euklids algoritme og diofantiske likninger
•regne ut Eulers ϕ-funksjon fra primtallsfaktoriseringen, også for primtallspotenser
2.1Eulers ϕ-funksjon og Eulers teorem
•bruke Eulers teorem til å redusere en stor eksponent, og alltid sjekke betingelsen først
2.1Eulers ϕ-funksjon og Eulers teorem
•finne resten når en stor potens deles på et tall, ved å kvadrere og multiplisere
2.1Eulers ϕ-funksjon og Eulers teorem
•håndtere tilfellet der grunntallet og modulusen har en felles faktor, ved å dele opp modulusen
2.1Eulers ϕ-funksjon og Eulers teorem
•gjøre rede for hvorfor Fermats lille teorem følger av Eulers teorem, og skrive utledningen
2.2Fermats lille teorem
•redusere en stor eksponent modulo p−1 når modulusen er et primtall, og sjekke vilkåret først
2.2Fermats lille teorem
•bruke den vilkårsfrie formen til å vise delelighetspåstander som gjelder for alle hele tall
2.2Fermats lille teorem
•kjenne igjen når modulusen ikke er et primtall, og velge riktig teorem
2.2Fermats lille teorem
•gjøre rede for hvorfor produktet av alle rester modulo et primtall er −1, ved å pare tall med sine inverser
2.3Wilsons teorem og fakultets-triksene
•finne resten når et fakultet ganget med et tall deles på et primtall, uten å regne ut fakultetet
2.3Wilsons teorem og fakultets-triksene
•skrive store faktorer som små negative rester, og holde orden på fortegnet
2.3Wilsons teorem og fakultets-triksene
•gange med en invers i stedet for å dele, og begrunne hvorfor det er lovlig
2.3Wilsons teorem og fakultets-triksene
•avgjøre om modulene i et system er parvis relativt primiske, og si hva det betyr for løsningen
2.4Det kinesiske restteoremet (CRT)
•løse et system av kongruenser både med formelen og ved suksessiv innsetting
2.4Det kinesiske restteoremet (CRT)
•forenkle hver enkelt kongruens før systemet settes sammen
2.4Det kinesiske restteoremet (CRT)
•håndtere systemer der modulene har en felles faktor, og avgjøre om de har løsning
2.4Det kinesiske restteoremet (CRT)
•velge riktig teorem for hver del av et sammensatt uttrykk, ut fra hva modulusen og leddene er
2.5Restberegning: eksponentreduksjon møter Wilson (fakultetsoppgaven)
•regne restene av et fakultetsledd og et potensledd hver for seg og kombinere dem
2.5Restberegning: eksponentreduksjon møter Wilson (fakultetsoppgaven)
•dele opp modulusen og sette svaret sammen igjen når grunntallet og modulusen har en felles faktor
2.5Restberegning: eksponentreduksjon møter Wilson (fakultetsoppgaven)
•føre hele besvarelsen med navngitte teoremer, sjekkede vilkår og kontroller underveis
2.5Restberegning: eksponentreduksjon møter Wilson (fakultetsoppgaven)
•velge riktig teorem for et gitt uttrykk og en gitt modulus, uten å se på oppskriften
2.6Drill: restberegning med de fire teoremene og CRT
•regne restberegninger og kongruenssystemer på eksamensnivå under tidspress
2.6Drill: restberegning med de fire teoremene og CRT
•løse et system av kongruenser med begge metodene, og bruke den ene som kontroll på den andre
2.6Drill: restberegning med de fire teoremene og CRT
•kontrollere eget arbeid på hvert steg, siden det ikke finnes hjelpemidler å slå opp i på eksamen
2.6Drill: restberegning med de fire teoremene og CRT
•regne ut Eulers ϕ-funksjon og redusere store eksponenter under tidspress, med vilkåret sjekket
2.PPrøver til del 2: Kongruenser og de fire store teoremene
•finne resten av et fakultet ganget med et tall, modulo et primtall, uten å regne ut fakultetet
2.PPrøver til del 2: Kongruenser og de fire store teoremene
•løse et system av kongruenser med begge metodene, og avgjøre løsbarhet når modulene har en felles faktor
2.PPrøver til del 2: Kongruenser og de fire store teoremene
•kombinere flere teoremer i én oppgave, slik signaturoppgaven er bygget på eksamen
2.PPrøver til del 2: Kongruenser og de fire store teoremene
•bygge et RSA-nøkkelpar fra to primtall og en krypteringseksponent
3.1RSA: nøkkelgenerering, kryptering og dekryptering
•finne dekrypteringseksponenten med Euklids algoritme frem og baklengs
3.1RSA: nøkkelgenerering, kryptering og dekryptering
•kryptere og dekryptere en melding for hånd med kvadrer-og-multipliser
3.1RSA: nøkkelgenerering, kryptering og dekryptering
•gjøre rede for hvorfor dekrypteringen gjenoppretter meldingen, også når et av primtallene deler meldingen
3.1RSA: nøkkelgenerering, kryptering og dekryptering
•bygge et RSA-nøkkelpar og finne dekrypteringseksponenten under tidspress
3.2Drill: RSA fra nøkkelpar til dekryptering
•kryptere og dekryptere for hånd med kvadrer-og-multipliser, med kontroll
3.2Drill: RSA fra nøkkelpar til dekryptering
•dekryptere via de to primtallene og sette svaret sammen med det kinesiske restteoremet
3.2Drill: RSA fra nøkkelpar til dekryptering
•føre korrekthetsbeviset, også for meldinger der et av primtallene deler meldingen
3.2Drill: RSA fra nøkkelpar til dekryptering
•dekryptere en RSA-melding for hånd med kvadrer-og-multipliser, under tidspress
3.PPrøver til del 3: RSA og offentlig-nøkkel-kryptografi
•finne dekrypteringseksponenten med Euklids algoritme og kontrollere den
3.PPrøver til del 3: RSA og offentlig-nøkkel-kryptografi
•bygge et helt nøkkelpar fra to primtall og en krypteringseksponent
3.PPrøver til del 3: RSA og offentlig-nøkkel-kryptografi
•føre korrekthetsbeviset for RSA, også for meldinger der et av primtallene deler meldingen
3.PPrøver til del 3: RSA og offentlig-nøkkel-kryptografi
•avgjøre om et tall er et kvadrat modulo et primtall, både ved å kvadrere alle rester og ved regneregler
4.1Kvadratiske rester, Legendre-symbolet og Eulers kriterium
•regne ut Legendre-symbolet ved å redusere telleren, faktorisere den og splitte symbolet over faktorene
4.1Kvadratiske rester, Legendre-symbolet og Eulers kriterium
•bruke Eulers kriterium til å avgjøre løsbarhet, med potensen regnet for hånd ved kvadrer-og-multipliser
4.1Kvadratiske rester, Legendre-symbolet og Eulers kriterium
•svare på hvor mange løsninger en kvadratisk kongruens har, og oppgi løsningene som et pluss-minus-par
4.1Kvadratiske rester, Legendre-symbolet og Eulers kriterium
•bruke resiprositetsloven til å bytte om teller og nevner, med riktig fortegnsfaktor
4.2Kvadratisk resiprositet og supplementsreglene
•avgjøre fortegnsfaktoren ved å lese av begge primtallenes rest ved divisjon med fire
4.2Kvadratisk resiprositet og supplementsreglene
•bruke de to supplementsreglene for minus én og for to, med riktig modulus i hver
4.2Kvadratisk resiprositet og supplementsreglene
•føre en fullstendig reduksjon av et Legendre-symbol med regelnavn ved hvert steg, og konkludere om antall løsninger
4.2Kvadratisk resiprositet og supplementsreglene
•kjøre reduksjonsalgoritmen for Legendre-symbolet uten å se på oppskriften
4.3Drill: Legendre-symbol og resiprositet
•holde fortegnsbokføringen korrekt gjennom en kjede med flere snuoperasjoner
4.3Drill: Legendre-symbol og resiprositet4.PPrøver til del 4: Kvadratiske rester og resiprositet
•velge mellom reduksjonskjede og Eulers kriterium ut fra hvor stort primtallet er
4.3Drill: Legendre-symbol og resiprositet
•kontrollere eget svar på flere uavhengige måter, siden det ikke finnes hjelpemidler å slå opp i på eksamen
4.3Drill: Legendre-symbol og resiprositet
•regne ut Legendre-symbolet under tidspress, med fullstendig føring og regelnavn ved hvert steg
4.PPrøver til del 4: Kvadratiske rester og resiprositet
•velge mellom Eulers kriterium og reduksjonskjeden ut fra hvor stort primtallet er
4.PPrøver til del 4: Kvadratiske rester og resiprositet
•begrunne antall kvadratiske rester og summen av symbolene, ikke bare oppgi tallene
4.PPrøver til del 4: Kvadratiske rester og resiprositet
•forklare hva ordenen til et tall modulo n er, og hvorfor den bare finnes når tallene er relativt primiske
5.1Orden modulo n og «orden deler ϕ(n)»
•finne ordenen ved å teste divisorene av fi-verdien i stigende rekkefølge, og begrunne at svaret er det minste
5.1Orden modulo n og «orden deler ϕ(n)»
•bruke ordenslemmaet begge veier: til å avgjøre hvilke eksponenter som gir én, og til å vise at ordenen deler fi-verdien
5.1Orden modulo n og «orden deler ϕ(n)»
•redusere store eksponenter med ordenen, og finne ordenen til en potens av tallet
5.1Orden modulo n og «orden deler ϕ(n)»
•forklare hva en primitiv rot er, og hvorfor potensene av den treffer alle restene
5.2Primitive røtter: eksistens, verifikasjon og telling
•avgjøre om en modulus i det hele tatt har en primitiv rot, ut fra formen på tallet
5.2Primitive røtter: eksistens, verifikasjon og telling
•verifisere en primitiv rot ved å teste én potens for hver primdivisor av fi-verdien
5.2Primitive røtter: eksistens, verifikasjon og telling
•telle primitive røtter og elementer av en gitt orden, og kontrollere tellingen ved å summere over divisorene
5.2Primitive røtter: eksistens, verifikasjon og telling
•regne ut antall divisorer og divisorsummen fra primtallsfaktoriseringen
5.3Tallteoretiske funksjoner: τ, σ og multiplikativitet
•utlede divisorsummen for en primtallspotens fra den geometriske summen
5.3Tallteoretiske funksjoner: τ, σ og multiplikativitet
•bruke multiplikativitet riktig, med vilkåret om at faktorene er relativt primiske
5.3Tallteoretiske funksjoner: τ, σ og multiplikativitet
•finne det minste tallet med et gitt antall divisorer ved å fordele eksponentene på de minste primtallene
5.3Tallteoretiske funksjoner: τ, σ og multiplikativitet
•kjøre divisortesten og primdivisortesten uten å se på oppskriften, og velge riktig av de to
5.4Drill: orden, primitive røtter og tallteoretiske funksjoner
•telle primitive røtter og elementer av gitt orden, og kontrollere tellingen ved å summere over divisorene
5.4Drill: orden, primitive røtter og tallteoretiske funksjoner
•regne antall divisorer og divisorsum for firesifrede tall, med faktoriseringen ført
5.4Drill: orden, primitive røtter og tallteoretiske funksjoner
•finne det minste tallet med et gitt antall divisorer, og kontrollere svaret
5.4Drill: orden, primitive røtter og tallteoretiske funksjoner
•finne ordenen under tidspress, med begrunnelse for at svaret er det minste
5.PPrøver til del 5: Orden, primitive røtter og tallteoretiske funksjoner
•verifisere en primitiv rot med én potens per primdivisor, og oppgi hvor mange tester som kreves
5.PPrøver til del 5: Orden, primitive røtter og tallteoretiske funksjoner
•telle primitive røtter, elementer av gitt orden og mulige ordener, og kontrollere tellingen
5.PPrøver til del 5: Orden, primitive røtter og tallteoretiske funksjoner
•regne antall divisorer og divisorsum, og finne det minste tallet med et gitt antall divisorer
5.PPrøver til del 5: Orden, primitive røtter og tallteoretiske funksjoner
•velge riktig bevisteknikk ut fra hvordan oppgaven er formulert, og skrive malens første setning før du regner
6.1Bevisteknikker: direkte, kontrapositivt, ved motsigelse og case-analyse
•oversette delelighet til likninger og føre et direkte bevis som ender i en konklusjonssetning
6.1Bevisteknikker: direkte, kontrapositivt, ved motsigelse og case-analyse
•gjennomføre en uttømmende case-analyse der alle rester er behandlet eller utelukkelsene begrunnet
6.1Bevisteknikker: direkte, kontrapositivt, ved motsigelse og case-analyse
•felle en påstand med et regnet moteksempel, og forklare hvorfor mange bekreftelser ikke er et bevis
6.1Bevisteknikker: direkte, kontrapositivt, ved motsigelse og case-analyse
•føre et induksjonsbevis med alle tre stegene merket, og plassere setningen om hypotesen der den faktisk brukes
6.2Matematisk induksjon: strukturen og de fire undertypene
•forklare hvorfor basissteget ikke kan hoppes over, med en falsk påstand som eksempel
6.2Matematisk induksjon: strukturen og de fire undertypene
•gjenkjenne hvilken av de fire undertypene en oppgave hører til, og bruke det tilhørende grepet i steget
6.2Matematisk induksjon: strukturen og de fire undertypene
•finne riktig startverdi i en ulikhet, og avgjøre hvor mange basissteg en rekursjon krever
6.2Matematisk induksjon: strukturen og de fire undertypene
•kjenne igjen hvilken av de fem faste bevisarketypene en oppgave hører til, og skrive førstegrepet uten å slå opp
6.3Delelighets- og primtallsbevis: arketypene
•føre argumentet for at relativt primiske divisorer gir produktet som divisor, på minst to av de tre veiene
6.3Delelighets- og primtallsbevis: arketypene
•vise at et tall er sammensatt ved den geometriske faktoriseringen, med begge faktorer begrunnet som ekte
6.3Delelighets- og primtallsbevis: arketypene
•føre et motsigelsesbevis for at det finnes uendelig mange primtall av en gitt form, med uttømmende case-analyse
6.3Delelighets- og primtallsbevis: arketypene
•føre induksjonsmalen med alle tre stegene uten å se på oppskriften, i alle fire undertyper
6.4Drill: induksjon og delelighets-/primtallsbevis
•kjenne igjen hvilken av de fem arketypene en delelighetspåstand hører til, og skrive førstegrepet direkte
6.4Drill: induksjon og delelighets-/primtallsbevis
•gjennomføre en uttømmende case-analyse med riktig valgt modulus, og begrunne hver rad som mangler
6.4Drill: induksjon og delelighets-/primtallsbevis
•løse todelte bevisoppgaver der lemmaet i første del brukes eksplisitt i andre del
6.4Drill: induksjon og delelighets-/primtallsbevis
•føre et bevis under tidspress med alle strukturkravene på plass, uten å slå opp malen
6.PPrøver til del 6: Bevis: induksjon, delelighet og primtall
•avdekke en falsk påstand ved å prøve små tallverdier før du begynner å bevise den
6.PPrøver til del 6: Bevis: induksjon, delelighet og primtall
•gjennomføre uttømmende case-analyse og velge modulus som lukker alle tilfellene
6.PPrøver til del 6: Bevis: induksjon, delelighet og primtall
•løse todelte oppgaver der lemmaet i første del brukes eksplisitt i andre del
6.PPrøver til del 6: Bevis: induksjon, delelighet og primtall
•utvikle et rasjonalt tall som kjedebrøk ved å lese av kvotientene i Euklids algoritme
7.1Kjedebrøk, konvergenter og Pells likning *(bør kjenne til)*
•utvikle kvadratrota av et tall som periodisk kjedebrøk med hjelpetabellen, og si hvor perioden lukker seg
7.1Kjedebrøk, konvergenter og Pells likning *(bør kjenne til)*
•regne ut konvergentene med rekursjonsskjemaet og kontrollere hver rad
7.1Kjedebrøk, konvergenter og Pells likning *(bør kjenne til)*
•lese den minste løsningen av Pells likning ut av konvergentene, og generere den neste ved kvadrering
7.1Kjedebrøk, konvergenter og Pells likning *(bør kjenne til)*
•skrive parametriseringen av primitive tripler med alle tre betingelsene, og si hva som går galt uten hver av dem
7.2Pytagoreiske tripler: primitiv parametrisering *(bør kjenne til)*
•avgjøre om en trippel er primitiv, og skille mellom primitive og avledede tripler i oppgavesvar
7.2Pytagoreiske tripler: primitiv parametrisering *(bør kjenne til)*
•finne alle primitive tripler med en gitt katet, ved å liste alle faktoriseringer og sile på betingelsene
7.2Pytagoreiske tripler: primitiv parametrisering *(bør kjenne til)*
•bevise delelighetspåstander om tripler ved uttømmende case-analyse på parametrene
7.2Pytagoreiske tripler: primitiv parametrisering *(bør kjenne til)*
•føre et irrasjonalitetsbevis etter malen i fem steg, med laveste-ledd-antakelsen og motsigelsen pekt på
7.3Irrasjonalitet og rasjonale approksimasjoner *(bør kjenne til)*
•avgjøre om en vilkårlig rot er rasjonal ved å se på eksponentene i primtallsfaktoriseringen
7.3Irrasjonalitet og rasjonale approksimasjoner *(bør kjenne til)*
•bruke uendelig nedstigning som alternativ bevisform, med ulikheten som gjør nedstigningen gyldig
7.3Irrasjonalitet og rasjonale approksimasjoner *(bør kjenne til)*
•finne en brøktilnærming med garantert nøyaktighet ved hjelp av konvergentene
7.3Irrasjonalitet og rasjonale approksimasjoner *(bør kjenne til)*
•utvikle kvadratrota som periodisk kjedebrøk under tidspress, med alle kontrollene ført
7.PPrøver til del 7: Spesialtemaer: kjedebrøk, Pell og pytagoreiske tripler
•lese Pell-løsningen ut av konvergentene og kontrollere den ved innsetting
7.PPrøver til del 7: Spesialtemaer: kjedebrøk, Pell og pytagoreiske tripler
•finne alle primitive tripler med en gitt katet, med alle tre betingelsene silt i tabellform
7.PPrøver til del 7: Spesialtemaer: kjedebrøk, Pell og pytagoreiske tripler
•føre et irrasjonalitetsbevis med laveste-ledd-antakelsen og motsigelsen pekt på
7.PPrøver til del 7: Spesialtemaer: kjedebrøk, Pell og pytagoreiske tripler
•føre en besvarelse slik at metoden er synlig: kjeden regnet, vilkåret kommentert, teoremet navngitt og svaret komplett
8.1Bevis- og føringsstandarden + utenat-banken
•kjenne igjen hvilken oppgavetype en eksamenstekst hører til, ut fra ordene i teksten alene
8.1Bevis- og føringsstandarden + utenat-banken
•planlegge fire timer på omtrent ti likt vektede delpunkt, og vite hva du skriver før du forlater et delpunkt
8.1Bevis- og føringsstandarden + utenat-banken
•gjengi hele teorem- og formelapparatet fra hukommelsen, siden det ikke finnes noe å slå opp i på eksamen
8.1Bevis- og føringsstandarden + utenat-banken
•gjennomføre et helt oppgavesett på fire timer med bare penn, papir og en enkel kalkulator
8.2Øvingseksamen 1: de fem søylene (bred kjerne)
•fordele tiden på delpunkt som teller likt, og ta de sikre før de usikre
8.2Øvingseksamen 1: de fem søylene (bred kjerne)
•føre hvert delpunkt slik at metoden er synlig: kjeden regnet, vilkåret kommentert, teoremet navngitt
8.2Øvingseksamen 1: de fem søylene (bred kjerne)
•rette eget arbeid mot en fullstendig fasit, og lese ut av den hva neste repetisjonsøkt skal handle om
8.2Øvingseksamen 1: de fem søylene (bred kjerne)
•gjennomføre et sett med de tunge sjangervariantene på fire timer, uten hjelpemidler
8.3Øvingseksamen 2: karakterskillerne og den sammensatte fakultetsoppgaven
•avgjøre hva du gjør når vilkåret i et teorem ikke er oppfylt, og begrunne omveien
8.3Øvingseksamen 2: karakterskillerne og den sammensatte fakultetsoppgaven
•føre et korrekthetsbevis og et todelt bevis med all struktur på plass under tidspress
8.3Øvingseksamen 2: karakterskillerne og den sammensatte fakultetsoppgaven
•kontrollere tellinger og fortegn på uavhengige måter, siden det ikke finnes noe å slå opp i
8.3Øvingseksamen 2: karakterskillerne og den sammensatte fakultetsoppgaven
•gjennomføre et bredt sett på fire timer der hver kjernesjanger opptrer én gang
8.4Øvingseksamen 3: bredt sett med roterende spesialtema
•prioritere riktig mellom høyfrekvente sjangre og et lavfrekvent spesialtema
8.4Øvingseksamen 3: bredt sett med roterende spesialtema
•føre to ulike bevistyper i samme sett: motsigelse med case-analyse, og induksjon med startverdi
8.4Øvingseksamen 3: bredt sett med roterende spesialtema
•utvikle en kvadratrot som kjedebrøk og lese Pell-løsningen ut av konvergentene, med kontroll
8.4Øvingseksamen 3: bredt sett med roterende spesialtema

Kapitler med kompetansemål

0Eksamenskartet

0.1Eksamenskartet: fem søyler, fast dramaturgi, alt begrunnes
  • gjøre rede for hvordan MA1301 vurderes: én skriftlig eksamen på fire timer der alle svar skal begrunnes
  • forklare hva hjelpemiddelkoden i emnet innebærer, og hvorfor den krever at apparatet sitter i hodet
  • prioritere lesingen etter hvor ofte temaene faktisk forekommer i arkivet
  • planlegge de fire timene på eksamen ut fra at delpunktene teller likt

1Delelighet, Euklids algoritme og diofantiske likninger

1.1Delelighet, primtall og aritmetikkens fundamentalteorem
  • avgjøre om et tall deler et annet, og begrunne det ut fra definisjonen
  • bruke divisjonsalgoritmen til å finne kvotient og rest, også for negative tall
  • faktorisere et tall i primtall med prøvedivisjon, og avgjøre om et tall er et primtall
  • finne største felles divisor og minste felles multiplum fra primtallsfaktoriseringen, og kontrollere svaret med produktregelen
1.2Euklids algoritme frem og baklengs (Bézout)
  • kjøre Euklids algoritme som divisjonskjede og lese av største felles divisor
  • gjøre rede for hvorfor algoritmen virker, ut fra at gcd er uendret når man erstatter et tall med resten
  • skrive største felles divisor som en kombinasjon av de to opprinnelige tallene ved substitusjon baklengs
  • vise at to uttrykk med en ukjent er relativt primiske ved å presentere tallet 1 som en kombinasjon av dem
1.3Lineære diofantiske likninger (ax + by = c)
  • avgjøre om en likning av typen ax+by=c har heltallsløsninger, og begrunne svaret
  • finne én løsning ved å skalere opp resultatet fra Euklids algoritme baklengs
  • skrive hele løsningsmengden med en fri parameter, og kontrollere den ved innsetting
  • finne den minste positive løsningen og alle løsninger i et gitt intervall
1.4Lineære kongruenser (ax ≡ b mod m)
  • regne med kongruenser og redusere store uttrykk underveis ved hjelp av regnereglene
  • avgjøre om en kongruens av typen ax ≡ b er løsbar, og hvor mange løsninger den har
  • forkorte en kongruens riktig, med den nødvendige betingelsen på modulusen
  • finne den modulære inversen med Euklids algoritme baklengs og bruke den til å løse kongruensen
1.5Drill: Euklid, diofant og lineær kongruens
  • kjøre Euklids algoritme frem og baklengs på firesifrede tall uten å se på oppskriften
  • løse en diofantisk likning fullstendig, med løsbarhetskommentar og hele løsningsmengden
  • løse en lineær kongruens og oppgi alle inkongruente løsninger modulo den opprinnelige modulusen
  • kontrollere eget arbeid på alle stegene, siden det ikke finnes hjelpemidler å slå opp i på eksamen
1.PPrøver til del 1: Delelighet, Euklids algoritme og diofantiske likninger
  • gjennomføre Euklids algoritme frem og baklengs under tidspress, med fullstendig føring
  • løse en diofantisk likning fullstendig: løsbarhet kommentert, hele løsningsmengden, og løsninger i et gitt intervall
  • løse en lineær kongruens og oppgi alle inkongruente løsninger, med modulusen riktig behandlet ved forkorting
  • kjede sammen flere teknikker i én oppgave, slik oppgave 1 er bygget på eksamen

2Kongruenser og de fire store teoremene

2.1Eulers ϕ-funksjon og Eulers teorem
  • regne ut Eulers ϕ-funksjon fra primtallsfaktoriseringen, også for primtallspotenser
  • bruke Eulers teorem til å redusere en stor eksponent, og alltid sjekke betingelsen først
  • finne resten når en stor potens deles på et tall, ved å kvadrere og multiplisere
  • håndtere tilfellet der grunntallet og modulusen har en felles faktor, ved å dele opp modulusen
2.2Fermats lille teorem
  • gjøre rede for hvorfor Fermats lille teorem følger av Eulers teorem, og skrive utledningen
  • redusere en stor eksponent modulo p−1 når modulusen er et primtall, og sjekke vilkåret først
  • bruke den vilkårsfrie formen til å vise delelighetspåstander som gjelder for alle hele tall
  • kjenne igjen når modulusen ikke er et primtall, og velge riktig teorem
2.3Wilsons teorem og fakultets-triksene
  • gjøre rede for hvorfor produktet av alle rester modulo et primtall er −1, ved å pare tall med sine inverser
  • finne resten når et fakultet ganget med et tall deles på et primtall, uten å regne ut fakultetet
  • skrive store faktorer som små negative rester, og holde orden på fortegnet
  • gange med en invers i stedet for å dele, og begrunne hvorfor det er lovlig
2.4Det kinesiske restteoremet (CRT)
  • avgjøre om modulene i et system er parvis relativt primiske, og si hva det betyr for løsningen
  • løse et system av kongruenser både med formelen og ved suksessiv innsetting
  • forenkle hver enkelt kongruens før systemet settes sammen
  • håndtere systemer der modulene har en felles faktor, og avgjøre om de har løsning
2.5Restberegning: eksponentreduksjon møter Wilson (fakultetsoppgaven)
  • velge riktig teorem for hver del av et sammensatt uttrykk, ut fra hva modulusen og leddene er
  • regne restene av et fakultetsledd og et potensledd hver for seg og kombinere dem
  • dele opp modulusen og sette svaret sammen igjen når grunntallet og modulusen har en felles faktor
  • føre hele besvarelsen med navngitte teoremer, sjekkede vilkår og kontroller underveis
2.6Drill: restberegning med de fire teoremene og CRT
  • velge riktig teorem for et gitt uttrykk og en gitt modulus, uten å se på oppskriften
  • regne restberegninger og kongruenssystemer på eksamensnivå under tidspress
  • løse et system av kongruenser med begge metodene, og bruke den ene som kontroll på den andre
  • kontrollere eget arbeid på hvert steg, siden det ikke finnes hjelpemidler å slå opp i på eksamen
2.PPrøver til del 2: Kongruenser og de fire store teoremene
  • regne ut Eulers ϕ-funksjon og redusere store eksponenter under tidspress, med vilkåret sjekket
  • finne resten av et fakultet ganget med et tall, modulo et primtall, uten å regne ut fakultetet
  • løse et system av kongruenser med begge metodene, og avgjøre løsbarhet når modulene har en felles faktor
  • kombinere flere teoremer i én oppgave, slik signaturoppgaven er bygget på eksamen

3RSA og offentlig-nøkkel-kryptografi

3.1RSA: nøkkelgenerering, kryptering og dekryptering
  • bygge et RSA-nøkkelpar fra to primtall og en krypteringseksponent
  • finne dekrypteringseksponenten med Euklids algoritme frem og baklengs
  • kryptere og dekryptere en melding for hånd med kvadrer-og-multipliser
  • gjøre rede for hvorfor dekrypteringen gjenoppretter meldingen, også når et av primtallene deler meldingen
3.2Drill: RSA fra nøkkelpar til dekryptering
  • bygge et RSA-nøkkelpar og finne dekrypteringseksponenten under tidspress
  • kryptere og dekryptere for hånd med kvadrer-og-multipliser, med kontroll
  • dekryptere via de to primtallene og sette svaret sammen med det kinesiske restteoremet
  • føre korrekthetsbeviset, også for meldinger der et av primtallene deler meldingen
3.PPrøver til del 3: RSA og offentlig-nøkkel-kryptografi
  • dekryptere en RSA-melding for hånd med kvadrer-og-multipliser, under tidspress
  • finne dekrypteringseksponenten med Euklids algoritme og kontrollere den
  • bygge et helt nøkkelpar fra to primtall og en krypteringseksponent
  • føre korrekthetsbeviset for RSA, også for meldinger der et av primtallene deler meldingen

4Kvadratiske rester og resiprositet

4.1Kvadratiske rester, Legendre-symbolet og Eulers kriterium
  • avgjøre om et tall er et kvadrat modulo et primtall, både ved å kvadrere alle rester og ved regneregler
  • regne ut Legendre-symbolet ved å redusere telleren, faktorisere den og splitte symbolet over faktorene
  • bruke Eulers kriterium til å avgjøre løsbarhet, med potensen regnet for hånd ved kvadrer-og-multipliser
  • svare på hvor mange løsninger en kvadratisk kongruens har, og oppgi løsningene som et pluss-minus-par
4.2Kvadratisk resiprositet og supplementsreglene
  • bruke resiprositetsloven til å bytte om teller og nevner, med riktig fortegnsfaktor
  • avgjøre fortegnsfaktoren ved å lese av begge primtallenes rest ved divisjon med fire
  • bruke de to supplementsreglene for minus én og for to, med riktig modulus i hver
  • føre en fullstendig reduksjon av et Legendre-symbol med regelnavn ved hvert steg, og konkludere om antall løsninger
4.3Drill: Legendre-symbol og resiprositet
  • kjøre reduksjonsalgoritmen for Legendre-symbolet uten å se på oppskriften
  • holde fortegnsbokføringen korrekt gjennom en kjede med flere snuoperasjoner
  • velge mellom reduksjonskjede og Eulers kriterium ut fra hvor stort primtallet er
  • kontrollere eget svar på flere uavhengige måter, siden det ikke finnes hjelpemidler å slå opp i på eksamen
4.PPrøver til del 4: Kvadratiske rester og resiprositet
  • regne ut Legendre-symbolet under tidspress, med fullstendig føring og regelnavn ved hvert steg
  • velge mellom Eulers kriterium og reduksjonskjeden ut fra hvor stort primtallet er
  • holde fortegnsbokføringen korrekt gjennom en kjede med flere snuoperasjoner
  • begrunne antall kvadratiske rester og summen av symbolene, ikke bare oppgi tallene

5Orden, primitive røtter og tallteoretiske funksjoner

5.1Orden modulo n og «orden deler ϕ(n)»
  • forklare hva ordenen til et tall modulo n er, og hvorfor den bare finnes når tallene er relativt primiske
  • finne ordenen ved å teste divisorene av fi-verdien i stigende rekkefølge, og begrunne at svaret er det minste
  • bruke ordenslemmaet begge veier: til å avgjøre hvilke eksponenter som gir én, og til å vise at ordenen deler fi-verdien
  • redusere store eksponenter med ordenen, og finne ordenen til en potens av tallet
5.2Primitive røtter: eksistens, verifikasjon og telling
  • forklare hva en primitiv rot er, og hvorfor potensene av den treffer alle restene
  • avgjøre om en modulus i det hele tatt har en primitiv rot, ut fra formen på tallet
  • verifisere en primitiv rot ved å teste én potens for hver primdivisor av fi-verdien
  • telle primitive røtter og elementer av en gitt orden, og kontrollere tellingen ved å summere over divisorene
5.3Tallteoretiske funksjoner: τ, σ og multiplikativitet
  • regne ut antall divisorer og divisorsummen fra primtallsfaktoriseringen
  • utlede divisorsummen for en primtallspotens fra den geometriske summen
  • bruke multiplikativitet riktig, med vilkåret om at faktorene er relativt primiske
  • finne det minste tallet med et gitt antall divisorer ved å fordele eksponentene på de minste primtallene
5.4Drill: orden, primitive røtter og tallteoretiske funksjoner
  • kjøre divisortesten og primdivisortesten uten å se på oppskriften, og velge riktig av de to
  • telle primitive røtter og elementer av gitt orden, og kontrollere tellingen ved å summere over divisorene
  • regne antall divisorer og divisorsum for firesifrede tall, med faktoriseringen ført
  • finne det minste tallet med et gitt antall divisorer, og kontrollere svaret
5.PPrøver til del 5: Orden, primitive røtter og tallteoretiske funksjoner
  • finne ordenen under tidspress, med begrunnelse for at svaret er det minste
  • verifisere en primitiv rot med én potens per primdivisor, og oppgi hvor mange tester som kreves
  • telle primitive røtter, elementer av gitt orden og mulige ordener, og kontrollere tellingen
  • regne antall divisorer og divisorsum, og finne det minste tallet med et gitt antall divisorer

6Bevis: induksjon, delelighet og primtall

6.1Bevisteknikker: direkte, kontrapositivt, ved motsigelse og case-analyse
  • velge riktig bevisteknikk ut fra hvordan oppgaven er formulert, og skrive malens første setning før du regner
  • oversette delelighet til likninger og føre et direkte bevis som ender i en konklusjonssetning
  • gjennomføre en uttømmende case-analyse der alle rester er behandlet eller utelukkelsene begrunnet
  • felle en påstand med et regnet moteksempel, og forklare hvorfor mange bekreftelser ikke er et bevis
6.2Matematisk induksjon: strukturen og de fire undertypene
  • føre et induksjonsbevis med alle tre stegene merket, og plassere setningen om hypotesen der den faktisk brukes
  • forklare hvorfor basissteget ikke kan hoppes over, med en falsk påstand som eksempel
  • gjenkjenne hvilken av de fire undertypene en oppgave hører til, og bruke det tilhørende grepet i steget
  • finne riktig startverdi i en ulikhet, og avgjøre hvor mange basissteg en rekursjon krever
6.3Delelighets- og primtallsbevis: arketypene
  • kjenne igjen hvilken av de fem faste bevisarketypene en oppgave hører til, og skrive førstegrepet uten å slå opp
  • føre argumentet for at relativt primiske divisorer gir produktet som divisor, på minst to av de tre veiene
  • vise at et tall er sammensatt ved den geometriske faktoriseringen, med begge faktorer begrunnet som ekte
  • føre et motsigelsesbevis for at det finnes uendelig mange primtall av en gitt form, med uttømmende case-analyse
6.4Drill: induksjon og delelighets-/primtallsbevis
  • føre induksjonsmalen med alle tre stegene uten å se på oppskriften, i alle fire undertyper
  • kjenne igjen hvilken av de fem arketypene en delelighetspåstand hører til, og skrive førstegrepet direkte
  • gjennomføre en uttømmende case-analyse med riktig valgt modulus, og begrunne hver rad som mangler
  • løse todelte bevisoppgaver der lemmaet i første del brukes eksplisitt i andre del
6.PPrøver til del 6: Bevis: induksjon, delelighet og primtall
  • føre et bevis under tidspress med alle strukturkravene på plass, uten å slå opp malen
  • avdekke en falsk påstand ved å prøve små tallverdier før du begynner å bevise den
  • gjennomføre uttømmende case-analyse og velge modulus som lukker alle tilfellene
  • løse todelte oppgaver der lemmaet i første del brukes eksplisitt i andre del

7Spesialtemaer: kjedebrøk, Pell og pytagoreiske tripler

7.1Kjedebrøk, konvergenter og Pells likning *(bør kjenne til)*
  • utvikle et rasjonalt tall som kjedebrøk ved å lese av kvotientene i Euklids algoritme
  • utvikle kvadratrota av et tall som periodisk kjedebrøk med hjelpetabellen, og si hvor perioden lukker seg
  • regne ut konvergentene med rekursjonsskjemaet og kontrollere hver rad
  • lese den minste løsningen av Pells likning ut av konvergentene, og generere den neste ved kvadrering
7.2Pytagoreiske tripler: primitiv parametrisering *(bør kjenne til)*
  • skrive parametriseringen av primitive tripler med alle tre betingelsene, og si hva som går galt uten hver av dem
  • avgjøre om en trippel er primitiv, og skille mellom primitive og avledede tripler i oppgavesvar
  • finne alle primitive tripler med en gitt katet, ved å liste alle faktoriseringer og sile på betingelsene
  • bevise delelighetspåstander om tripler ved uttømmende case-analyse på parametrene
7.3Irrasjonalitet og rasjonale approksimasjoner *(bør kjenne til)*
  • føre et irrasjonalitetsbevis etter malen i fem steg, med laveste-ledd-antakelsen og motsigelsen pekt på
  • avgjøre om en vilkårlig rot er rasjonal ved å se på eksponentene i primtallsfaktoriseringen
  • bruke uendelig nedstigning som alternativ bevisform, med ulikheten som gjør nedstigningen gyldig
  • finne en brøktilnærming med garantert nøyaktighet ved hjelp av konvergentene
7.PPrøver til del 7: Spesialtemaer: kjedebrøk, Pell og pytagoreiske tripler
  • utvikle kvadratrota som periodisk kjedebrøk under tidspress, med alle kontrollene ført
  • lese Pell-løsningen ut av konvergentene og kontrollere den ved innsetting
  • finne alle primitive tripler med en gitt katet, med alle tre betingelsene silt i tabellform
  • føre et irrasjonalitetsbevis med laveste-ledd-antakelsen og motsigelsen pekt på

8Eksamenstrening

8.1Bevis- og føringsstandarden + utenat-banken
  • føre en besvarelse slik at metoden er synlig: kjeden regnet, vilkåret kommentert, teoremet navngitt og svaret komplett
  • kjenne igjen hvilken oppgavetype en eksamenstekst hører til, ut fra ordene i teksten alene
  • planlegge fire timer på omtrent ti likt vektede delpunkt, og vite hva du skriver før du forlater et delpunkt
  • gjengi hele teorem- og formelapparatet fra hukommelsen, siden det ikke finnes noe å slå opp i på eksamen
8.2Øvingseksamen 1: de fem søylene (bred kjerne)
  • gjennomføre et helt oppgavesett på fire timer med bare penn, papir og en enkel kalkulator
  • fordele tiden på delpunkt som teller likt, og ta de sikre før de usikre
  • føre hvert delpunkt slik at metoden er synlig: kjeden regnet, vilkåret kommentert, teoremet navngitt
  • rette eget arbeid mot en fullstendig fasit, og lese ut av den hva neste repetisjonsøkt skal handle om
8.3Øvingseksamen 2: karakterskillerne og den sammensatte fakultetsoppgaven
  • gjennomføre et sett med de tunge sjangervariantene på fire timer, uten hjelpemidler
  • avgjøre hva du gjør når vilkåret i et teorem ikke er oppfylt, og begrunne omveien
  • føre et korrekthetsbevis og et todelt bevis med all struktur på plass under tidspress
  • kontrollere tellinger og fortegn på uavhengige måter, siden det ikke finnes noe å slå opp i
8.4Øvingseksamen 3: bredt sett med roterende spesialtema
  • gjennomføre et bredt sett på fire timer der hver kjernesjanger opptrer én gang
  • prioritere riktig mellom høyfrekvente sjangre og et lavfrekvent spesialtema
  • føre to ulike bevistyper i samme sett: motsigelse med case-analyse, og induksjon med startverdi
  • utvikle en kvadratrot som kjedebrøk og lese Pell-løsningen ut av konvergentene, med kontroll
Tilbake til MA1301 Tallteori