6.4 Drill: induksjon og delelighets-/primtallsbevis

Hele bevisrepertoaret drillet med full struktur: induksjon (alle fire undertyper + sterk), de fem delelighets-/primtallsarketypene, og todelte lemma-så-anvend-oppgaver — der bevisstrukturen i seg selv gir uttelling.

80 min

14 oppgaver

Drillinduksjondelelighets-/primtallsbevis

Din fremgang i kapitlet

0 / 14 oppgaver

Kapitlets plass i kurset

Bygger på

6.3Delelighets- og primtallsbevis: arketypene

Brukes videre i

6.PPrøver til del 6: Bevis: induksjon, delelighet og primtall

Dette kapitlet driller sjanger I og J: delelighets- og primtallsbevis i ~8 av 15 sett (~53 %), induksjon i 8 av 15 sett (53 %). Til sammen betyr det at hvert eneste sett i arkivet har minst én ren bevisoppgave. Sjangerbokstavene er bokas forkortelser for oppgavetypene, forklart i kap. 0.1; I er «bevis en påstand om delelighet eller primtall», J er «bevis en formel ved matematisk induksjon».

Teorien står i kap. 6.1–kap. 6.3. Her er poenget noe annet: at malene skal gå automatisk. Bevis er en egen ferdighet, og den er den ene i faget der formen gir uttelling for seg selv. Et halvferdig bevis med riktig struktur er verdt mer enn et ferdig svar uten den.

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

Variant	Antall oppgaver her
Induksjon: summeformel	1
Induksjon: delelighet	1
Induksjon: ulikhet med riktig $n_0$	1
Induksjon: kongruensmønster / $a^p\equiv a$	1
Sterk induksjon	1
Arketype 1: relativt primiske faktorer	1
Arketype 2: $2^n-1$ sammensatt	1
Arketype 3: $p\mid\binom pk$	1
Arketype 4: uendelig mange primtall	1
Arketype 5: primtallstripler modulo $3$	1
Todelt oppgave (lemma i a, anvend i b)	2
Case-analyse / umulighet	2

Prioritet: høyeste prioritet. Bevisoppgaven kan ikke reddes med regneferdighet, og den kommer hvert år. Til gjengjeld er repertoaret lite — fem bevisteknikker, fire induksjonsundertyper og fem arketyper, alt ferdig utskrevet i Del 6.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en bestemt, enkel kalkulator. I bevisdelen har kalkulatoren ingenting å bidra med i det hele tatt. Alt kommer fra hodet, og det som må sitte, er former.

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

- induksjonens tre steg — basissteg, hypotese, steg — med setningen «Her bruker vi induksjonshypotesen:»
- de fire bevisteknikkene fra kap. 6.1 med sin åpningssetning
- de fem arketypene fra kap. 6.3 med sitt førstegrep
- at $a\mid b$ betyr $b=at$ , og at det er der hvert delelighetsbevis starter
- at en case-analyse modulo $m$ har $m$ rader
- den geometriske faktoriseringen $x^d-1=(x-1)(x^{d-1}+\dots+1)$
- Euklid-trikset $N=m\,p_1\cdots p_r-1$ i «uendelig mange»-bevis

Utledes på stedet:

- Bézout-veien til arketype 1 — $mx+ny=1$ , gang med $k$ , kryss-substituér; tre linjer
- $p\mid\binom pk$ — fra $k!(p-k)!\binom pk=p!$ og Euklids lemma; tre linjer
- sumformelen $\displaystyle 1+2+\dots+n=\frac{n(n+1)}2$ — Gauss-trikset; to linjer
- kvadratrestene modulo $3$ , $4$ og $8$ — to linjer hver

Selvtest, tre minutter: dekk til boka og skriv ned (i) de tre induksjonsstegene, (ii) de fire åpningssetningene, (iii) de fem arketypene med førstegrep. Tretten linjer til sammen. Klarer du det, har du hele Del 6 tilgjengelig — og det er nettopp den listen som ikke finnes i noen bok du har med deg 24. november.

Former pugges ved å brukes, ikke ved å leses. Fjorten regnede bevis med lukket bok er mer verdt enn fjorten gjennomlesninger.

Forkunnskaper

Hele Del 6: kap. 6.1 (de fire bevisteknikkene), kap. 6.2 (induksjon, de fire undertypene og sterk induksjon) og kap. 6.3 (de fem arketypene). Du bør også ha delelighet og Euklids lemma fra kap. 1.1 og Bézout fra kap. 1.2 friskt.

Sist du var her. De fem resultatene du bruker i oppgavene under, ferdig oppfrisket:

Induksjonens tre steg. (1) Basissteg $P(n_0)$ med tall; (2) hypotese «anta $P(k)$ for en $k\ge n_0$ »; (3) steg, med «Her bruker vi induksjonshypotesen:» der innsettingen skjer.

Arketype 1. $\gcd(m,n)=1$ , $m\mid k$ , $n\mid k$ $\Rightarrow mn\mid k$ . Tre veier: Bézout, Euklids lemma, fundamentalteoremet.

Den geometriske faktoriseringen. $x^d-1=(x-1)(x^{d-1}+\dots+x+1)$ , og $d\mid n\Rightarrow x^d-1$ deler $x^n-1$ .

Arketype 3. $p$ primtall, $1\le k\le p-1$ $\Rightarrow p\mid\binom pk$ . Følger av $k!(p-k)!\binom pk=p!$ og Euklids lemma.

Euklid-trikset. I «uendelig mange primtall $\equiv a\pmod m$ »-bevis: $N=m\,p_1p_2\cdots p_r-1$ .

Fra videregående: Induksjonsbevis, Induksjon, Direkte bevis og moteksempler og Kontrapositiv og kontradiksjon dekker grunnformene.

Tidsanslag for kapitlet: ~80 minutter — ~15 minutter på oppskriftene, ~15 på eksamenscaset, og ~50 på de fjorten oppgavene. Del dem gjerne over to økter.

Løsningsoppskriftene

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

Del 6 har to familier av oppskrifter: induksjonsmalen (én mal, fire undertyper) og arketypene (fem faste argumenter). Det første du gjør i en bevisoppgave, er å avgjøre hvilken familie den hører til.

Oppskrift: velg teknikk på tjue sekunder

Les oppgaveteksten og se etter signalordene:

Ser du …	Velg	Første setning
«for alle $n\ge n_0$ » med formel, sum eller rekursjon	induksjon	«Basissteg ( $n=n_0$ ): …»
«for alle heltall $n$ » uten rekursjon	case-analyse modulo $m$	«Ved divisjonsalgoritmen er $n\equiv r\pmod m$ …»
«det finnes ikke», «uendelig mange», «irrasjonal»	motsigelse	«Anta, for å komme til en motsigelse, at …»
«hvis $P$ så $Q$ » med likning i hypotesen	direkte	«Anta at $P$ . Da finnes $t$ med …»
konklusjon som er lett å negere	kontrapositivt	«Vi viser den kontrapositive: …»
«avgjør om», «er det sant at»	let etter moteksempel først	«Påstanden er falsk. Ta $n=\dots$ »

Deretter: hvilken arketype? Ser du to delelighetsantakelser og et produkt (arketype 1),

2^n-1

(2), en binomialkoeffisient med primtall øverst (3), «uendelig mange» (4), eller primtall med fast avstand (5)?
Er $d$ sammensatt i en delelighetspåstand, splitt i primtallspotenser.

30=2\cdot 3\cdot 5

gir

2+3+5=10

rader case-analyse i stedet for tretti.
Og les hva som spørres. «Vis at» betyr at påstanden er sann; «avgjør om» betyr at den kan være falsk. Tjue sekunders lesing sparer fem minutters famling.

Oppskrift: induksjonsmalen i tre steg

For «vis at $P(n)$ for alle $n\ge n_0$ »:

1. Skriv opp $P(n)$ som en navngitt påstand, og finn $n_0$ hvis oppgaven ikke oppgir den (prøv $n=1,2,3,\dots$ og skriv tabellen).
2. Basissteg ( $n=n_0$ ): regn ut begge sider med tall. Ikke «åpenbart».
3. Induksjonshypotese: «anta at $P(k)$ holder for en $k\ge n_0$ » — som egen linje, med innholdet utskrevet.
4. Skriv ned målet $P(k+1)$ før du regner.
5. Induksjonssteg: koble $k+1$ -tilfellet til $k$ -tilfellet, og skriv «Her bruker vi induksjonshypotesen:» der innsettingen skjer.
6. Avslutt: «Ved induksjonsprinsippet holder $P(n)$ for alle $n\ge n_0$ .»

Koblingen i steg 5, per undertype:

Undertype	Koblingen
sum	$S(k+1)=S(k)+a_{k+1}$ — regn ut $a_{k+1}$ eksplisitt
delelighet	$f(k+1)=A\,f(k)+R$ med $d\mid R$ — se på det raskest voksende leddet for å finne $A$
ulikhet	ulikhetskjede med hypotesen som ledd; restulikheten skal bevises
kongruens	binomialformelen pluss $p\mid\binom pk$

Antall basissteg = antall ledd rekursjonen ser tilbake. Ser steget både

P(k)

P(k-1)

, trengs to.
Oppskriften må sitte utenat. Steg 2 er det som glemmes, og et induksjonsbevis uten basissteg er ikke et bevis — instruksen på hvert eksamenssett er at alle svar skal begrunnes, og i et bevis er strukturen begrunnelsen.
Kontrollen: sett

n=n_0+1

inn i den ferdige formelen og regn ut begge sider direkte.

Oppskrift: de fem arketypene

Arketype 1 — $\gcd(m,n)=1$ , $m\mid k$ , $n\mid k\Rightarrow mn\mid k$ .
Bézout-veien: $mx+ny=1$ ; gang med $k$ ; sett $k=nc$ i første ledd og $k=md$ i andre; få $k=mn(cx+dy)$ . $\gcd$ -linjen skal stå.

Arketype 2 — $2^n-1$ sammensatt når $n$ sammensatt.
$n=ab$ med $a,b\ge 2$ ; ved den geometriske faktoriseringen er $2^n-1=(2^a-1)(2^{a(b-1)}+\dots+1)$ ; vis at begge faktorene er $>1$ .

Arketype 3 — $p\mid\binom pk$ for $1\le k\le p-1$ .
$k!(p-k)!\binom pk=p!$ ; $p$ deler høyresiden; ved Euklids lemma deler $p$ en faktor; utelukk $k!$ og $(p-k)!$ (alle faktorer $<p$ ).

Arketype 4 — uendelig mange primtall $\equiv a\pmod m$ .
Anta endelig liste $p_1,\dots,p_r$ ; sett $N=m\,p_1\cdots p_r-1$ ; vis $N>1$ og $N\equiv -1\pmod m$ ; case-analyse på primdivisorene; vis at den nye ikke er i listen ( $q\mid 1$ ellers).

Arketype 5 — $p$ , $p+a$ , $p+2a$ alle primtall, $3\nmid a\Rightarrow p=3$ .
Sjekk at $p=3$ virker; case-analyse modulo $3$ med alle tre restene; størrelsesargumentet ( $3\mid x$ og $x>3$ gir sammensatt).

Alle fem må sitte utenat med sitt førstegrep. Argumentene er tre til seks linjer og utledes på stedet.

De seks kontrollpunktene

Under kode D er selvkontroll den eneste kontrollen du har. Disse seks tar til sammen under to minutter.

1. Står basissteget der, med begge sider regnet ut? Og med riktig $n_0$ — ikke $1$ av vane.

2. Er hypotesen brukt, og pekt på? Finn linjen med «Her bruker vi induksjonshypotesen:». Finnes den ikke, er det ikke induksjon.

3. Er case-analysen komplett? Tell radene: modulo $m$ gir $m$ rader, med mindre utelukkelsene er skrevet ut.

4. Er $\gcd$ -betingelsen sjekket? Ved hver bruk av arketype 1, og ved hver oppsplitting av et sammensatt tall.

5. Er teoremet navngitt? Euklids lemma, aritmetikkens fundamentalteorem, divisjonsalgoritmen, Bézout, Fermats lille teorem.

6. Prøv påstanden på to–tre tallverdier. Det avdekker en gal påstand på tjue sekunder — og det avdekker om du har lest oppgaven riktig.

Legg til tre gratis grovkontroller:

- I «vis at tallet er sammensatt»: er begge faktorene $>1$ ?
- I «det eneste …»: virker det oppgitte tallet? Sjekk at $p=3$ faktisk gir tre primtall.
- I «uendelig mange»: er $N>1$ ? Ellers har $N$ ingen primdivisor.

— naturlig pausepunkt —

Gjennomregnet eksamenscase

~15 minutter.

Her er en typisk todelt bevisoppgave — lemma i del a, anvendelse i del b — nøyaktig i den formen arkivets nyere sett 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.

✏️Eksamenscase: lemma i a, anvendelse i b

a) Vis at hvis

n

er et sammensatt tall, så er

2^n-1

sammensatt. (4 poeng)

b) Bruk a) til å avgjøre om $2^{35}-1$ er et primtall, og oppgi to ulike ekte divisorer. (3 poeng)

c) Vis at det ikke følger av a) at $2^p-1$ er et primtall når $p$ er et primtall, ved å gi et moteksempel. (3 poeng)

Del a)

Anta at $n$ er sammensatt. Da finnes det, per definisjon (kap. 1.1), hele tall $a,b$ med
$n=ab,\qquad 1<a<n,\quad 1<b<n.$
Spesielt er $a\ge 2$ og $b\ge 2$ .

Steg 1: faktoriser. Ved den geometriske faktoriseringen (kap. 6.3) med $x=2^a$ :
$2^n-1=\bigl(2^a\bigr)^b-1=\bigl(2^a-1\bigr)\Bigl(2^{a(b-1)}+2^{a(b-2)}+\dots+2^a+1\Bigr).$

(Faktoriseringen utledes på stedet ved å gange ut $(x-1)(x^{b-1}+\dots+1)$ : alle mellomledd kansellerer, og bare $x^b$ og $-1$ står igjen.)

Steg 2: vis at begge faktorene er ekte.

- Første faktor: $a\ge 2$ gir $2^a-1\ge 2^2-1=3>1$ .
- Andre faktor: den er en sum av $b\ge 2$ positive ledd, og det største er $2^{a(b-1)}\ge 2^a\ge 4$ . Altså er den $\ge 4+1=5>1$ .

Steg 3: konkludér. $2^n-1$ er et produkt av to hele tall som begge er større enn $1$ , altså sammensatt. $\blacksquare$

Sensorblikk på del a). Fire ting gir uttelling, hver for seg.
(1) Definisjonen av sammensatt tall er brukt til å skrive $n=ab$ med begge faktorer $\ge 2$ — det er «arbeid fra definisjonen»-vanen fra kap. 6.1.
(2) Faktoriseringen er navngitt («ved den geometriske faktoriseringen»), ikke bare skrevet ned.
(3) Steg 2 er der. Dette er den delen som glemmes: en faktorisering der en faktor kan være $1$ , viser ingenting. Uten steg 2 er beviset ufullstendig, selv med feilfri algebra.
(4) Konklusjonen er en setning som knytter faktoriseringen til definisjonen av sammensatt.
Merk også at beviset ikke bruker noe spesielt ved grunntallet $2$ — samme argument viser at $3^n-1$ , $5^n-1$ og så videre er sammensatte når $n$ er det. Å nevne det koster én setning og viser at du har forstått hva som bærer argumentet.

Del b)

Steg 1: er $35$ sammensatt? Ja: $35=5\cdot 7$ , og begge faktorene er $\ge 2$ .

Steg 2: bruk a). Etter a) er $2^{35}-1$ dermed sammensatt, altså ikke et primtall.

Steg 3: finn to ekte divisorer. Beviset i a) gir divisoren $2^a-1$ for hver faktorisering $35=ab$ . De to oppdelingene er $35=5\cdot 7$ og $35=7\cdot 5$ :

- $a=5$ : divisoren er $2^5-1=31$ .
- $a=7$ : divisoren er $2^7-1=127$ .

To ekte divisorer er altså $31$ og $127$ .

Kontroll. $2^{35}-1=34\,359\,738\,367$ . Vi kontrollerer $31$ -delen med den geometriske faktoriseringen i stedet for å dividere det store tallet:
$2^{35}-1=\bigl(2^5\bigr)^7-1=\bigl(2^5-1\bigr)\bigl(2^{30}+2^{25}+\dots+2^5+1\bigr)=31\cdot(\dots).$
Den andre faktoren er en sum av sju toerpotenser og dermed et helt tall ✓. Tilsvarende for $127$ med $a=7$ , $b=5$ .

Sluttsvar: $2^{35}-1$ er ikke et primtall; det er delelig med både $31$ og $127$ .

Sensorblikk på del b). Tre ting:
(1) At $35$ er sammensatt, er sagt med faktoriseringen. Uten den er anvendelsen av a) ubegrunnet.
(2) Henvisningen «etter a)» står. Å bevise a) på nytt her er tidssløsing; å hoppe over henvisningen er et hull.
(3) Divisorene er begrunnet fra beviset, ikke funnet ved prøving. Det er hele poenget med å ha a): den gir deg divisorene gratis, i to varianter.
Merk at oppgaven ba om to divisorer, og at de to oppdelingene av $35$ gir nøyaktig to. Hadde $n$ vært $30$ , ville divisorene $2^2-1=3$ , $2^3-1=7$ , $2^5-1=31$ , $2^6-1=63$ , $2^{10}-1=1023$ og $2^{15}-1=32767$ alle vært tilgjengelige — én for hver ekte divisor i $30$ .

Del c)

Påstanden som skal avvises: «er $p$ et primtall, er $2^p-1$ et primtall».

Merk først hva a) faktisk sier. Del a) er implikasjonen
$n\ \text{sammensatt}\ \Longrightarrow\ 2^n-1\ \text{sammensatt}.$
Den kontrapositive er « $2^n-1$ primtall $\Rightarrow n$ primtall» — samme utsagn (kap. 6.1). Men påstanden i c) er omvendingen, og en omvending er et annet utsagn som godt kan være falsk.

Moteksempel: $p=11$ . $11$ er et primtall, og
$2^{11}-1=2048-1=2047=23\cdot 89.$

Kontroll av faktoriseringen: $23\cdot 89=23\cdot 90-23=2070-23=2047$ ✓.

Altså er $2047$ sammensatt, mens $11$ er et primtall. Påstanden i c) er dermed falsk. $\blacksquare$

At $p=11$ er det minste moteksempelet: $p=2,3,5,7$ gir $3$ , $7$ , $31$ , $127$ — alle primtall. Det er derfor forvekslingen er så lett å gjøre: fire treff på rad.

Sluttsvar: a) bevist ved geometrisk faktorisering med begge faktorer ekte; b) $2^{35}-1$ er sammensatt, med divisorene $31$ og $127$ ; c) moteksempelet $p=11$ , der $2^{11}-1=2047=23\cdot 89$ .

Sensorblikk på del c). To ting, og det første er det viktigste:
(1) Skillet mellom kontrapositiv og omvending er sagt. Det er selve faglige innholdet i delpunktet — a) sier ingenting om primtallseksponenter, og å forklare hvorfor er hva oppgaven spør om.
(2) Moteksempelet er regnet ut, med faktoriseringen synlig og kontrollert. Et oppgitt tall uten utregning er et sluttall uten metode.
Om tidsbruken i hele oppgaven: dette er tre delpunkt à ~24 minutter, altså 72 minutter i eksamenstid — men de er kortere enn budsjettet. Realistisk: a) tar 8–10 minutter, b) tar 4–5, c) tar 5–6. Til sammen under 25 minutter for tre delpunkt. Bevisdelpunkter er ofte de raskeste i settet når malene sitter — og det er en av grunnene til at det er lønnsomt å drille dem.

Oppgavene

~50 minutter til sammen. Fjorten oppgaver, gruppert etter variant.

Regn dem med penn og lukket bok. Det er den eneste treningsformen som ligner eksamen — og i bevisdelen er det særlig malens første setning som må komme av seg selv.

Slik er de gruppert:

- Oppgave 1–4: induksjon, én per undertype (sum, delelighet, ulikhet, kongruens)
- Oppgave 5: sterk induksjon
- Oppgave 6–10: de fem arketypene, én hver
- Oppgave 11–12: todelte oppgaver (lemma i a, anvend i b)
- Oppgave 13–14: case-analyse og umulighet

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

— naturlig pausepunkt —

📝Oppgave 1

(Induksjon, undertype 1: summeformel.)

Vis ved induksjon at $\displaystyle \displaystyle\sum_{i=1}^n\frac{1}{(2i-1)(2i+1)}=\frac{n}{2n+1}$ for alle $n\ge 1$ .

📝Oppgave 2

(Induksjon, undertype 2: delelighet.)

Vis ved induksjon at $5\mid 6^n-1$ for alle $n\ge 1$ .

📝Oppgave 3

(Induksjon, undertype 3: ulikhet.)

a) Finn den minste $n_0$ slik at $3^n>n^3$ for alle $n\ge n_0$ .
b) Bevis påstanden ved induksjon.

📝Oppgave 4

(Induksjon, undertype 4: kongruensmønster.)

En følge er definert ved $u_1=2$ , $u_2=5$ og $u_{n+1}=u_n+u_{n-1}$ for $n\ge 2$ .

Vis ved induksjon at $u_{n+3}\equiv u_n\pmod 2$ for alle $n\ge 1$ .

📝Oppgave 5

(Sterk induksjon.)

En følge er definert ved $b_1=2$ , $b_2=8$ og $b_n=4b_{n-1}-3b_{n-2}$ for $n\ge 3$ .

Vis ved sterk induksjon at $b_n=3^n-1$ for alle $n\ge 1$ .

📝Oppgave 6

(Arketype 1: relativt primiske faktorer.)

Vis at hvis $8\mid k$ og $9\mid k$ , så er $72\mid k$ . Bruk arketype 1, og skriv $\gcd$ -linjen eksplisitt.

📝Oppgave 7

(Arketype 2: to i n-te minus én.)

Vis at $2^{25}-1$ er sammensatt, og gi en ekte divisor. Vis eksplisitt at begge faktorene i faktoriseringen din er større enn $1$ .

📝Oppgave 8

(Arketype 3: primtallet deler binomialkoeffisienten.)

a) Vis at $p\mid\binom pk$ for $1\le k\le p-1$ når $p$ er et primtall.
b) Bruk a) til å vise at $11\mid\binom{11}{4}$ , og kontrollér ved å regne ut $\binom{11}{4}$ .

📝Oppgave 9

(Arketype 4: uendelig mange primtall.)

Vis at det finnes uendelig mange primtall $p$ med $p\equiv 5\pmod 6$ .

Før beviset komplett etter malen, med case-analysen og «ikke i listen»-setningen skrevet ut.

📝Oppgave 10

(Arketype 5: primtallstripler modulo 3.)

Vis at det eneste primtallet $p$ der både $p+10$ og $p+20$ også er primtall, er $p=3$ .

📝Oppgave 11

(Todelt: lemma i a, anvend ved induksjon i b.)

a) Vis at $p\mid\binom pk$ for $1\le k\le p-1$ når $p$ er et primtall, og utled at $(a+b)^p\equiv a^p+b^p\pmod p$ .
b) Bruk a) til å vise ved induksjon at $a^p\equiv a\pmod p$ for alle hele tall $a\ge 1$ .

📝Oppgave 12

(Todelt: lemma i a, anvend i b.)

a) Vis at $\gcd(m,n)=1$ , $m\mid k$ og $n\mid k$ gir $mn\mid k$ .
b) Bruk a) til å vise at $42\mid n^7-n$ for alle heltall $n$ .

📝Oppgave 13

(Case-analyse og umulighet.)

Vis at likningen $x^2+y^2=4z+3$ ikke har løsninger i hele tall.

📝Oppgave 14

(Case-analyse: velg riktig modulus.)

a) Vis at $7\nmid n^2+1$ for alle heltall $n$ .
b) Bruk a) til å vise at likningen $n^2-7m=-1$ ikke har løsninger i hele tall.
c) Avgjør om det samme gjelder for $5$ i stedet for $7$ , altså om $5\nmid n^2+1$ for alle $n$ .

Typiske feil

De seks feilene under er dokumentert i arkivets løsningsforslag som noe fasitene fører eksplisitt imot. Alle er strukturfeil eller manglende betingelser — i bevisdelen er det formen som glipper, ikke aritmetikken.

- Glemt basissteg. Den best belagte enkeltfeilen i hele bevisdelen. Uten basissteg viser induksjonssteget bare en implikasjon, og kap. 6.2 fører en falsk påstand der steget går perfekt igjennom. Kontrollen: står «Basissteg» der som eget merket punkt, med begge sider regnet ut, og med riktig $n_0$ ?

- Hypotesen ikke brukt, eller ikke pekt på. Kommer du gjennom steget uten å ha satt inn $P(k)$ , er beviset ikke et induksjonsbevis. Skriv «Her bruker vi induksjonshypotesen:» der innsettingen skjer — det er den setningen fasitene alltid markerer.

- Ufullstendig case-analyse. En glemt rad. Tell radene: modulo $m$ gir $m$ rader, med mindre utelukkelsene (« $r=0$ er umulig fordi …») eller symmetrien (« $(m-r)^2\equiv r^2$ ») er skrevet ut. «Går på samme måte» er ikke en begrunnelse.

- Teoremet ikke navngitt. Euklids lemma, aritmetikkens fundamentalteorem, divisjonsalgoritmen, Bézout, Fermats lille teorem. Instruksen på hvert sett er at alle svar skal begrunnes, og i et bevis er navnet på resultatet en del av begrunnelsen.

- Arketype 1 brukt uten $\gcd$ -sjekken. $4\mid 12$ og $6\mid 12$ , men $24\nmid 12$ . Splitt alltid i primtallspotenser — da er faktorene automatisk parvis relativt primiske, og linjen «og $\gcd(8,3)=1$ » er én linje å skrive.

- Sirkelbevis. Å regne på begge sider til « $0=0$ » er bare gyldig hvis hvert steg er en ekvivalens og du skriver det. Den trygge formen er å starte i én ende og regne til den andre.

Og fire arketype-spesifikke feil:

- Arketype 2: å glemme at begge faktorene må vises å være $>1$ . En faktorisering der én faktor kan være $1$ , viser ingenting.
- Arketype 2: å tro på den omvendte. $2^{11}-1=2047=23\cdot 89$ , og $11$ er et primtall.
- Arketype 4: å glemme «ikke i listen»-setningen. Den er motsigelsen: «var $q=p_i$ , ville $q\mid 1$ ».
- Arketype 5: å glemme størrelsesargumentet. « $3\mid p+8$ » gir sammensatt bare fordi $p+8>3$ .

Oppskriftskort

Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 80 minutter gjelder oppskriftene, caset og oppgavene over.

Drillkapitlene har få kort, og de er alle prosedyrekort: de skal pugges ved å kjøres, ikke ved å leses. Under kode D finnes ingen mal å slå opp i 24. november — malene er selve det som må komme ut av hodet.

Kort: induksjonens tre steg

P(n_0)

Kort: velg teknikk og arketype

n\ge n_0

Ser du	Velg
«for alle $n\ge n_0$ » med formel/rekursjon	induksjon
«for alle heltall $n$ » uten rekursjon	case-analyse modulo $m$
«det finnes ikke», «uendelig mange»	motsigelse
«hvis $P$ så $Q$ » med likning i hypotesen	direkte
konklusjon lett å negere	kontrapositivt
«avgjør om»	moteksempel først

Ser du	Arketype
to delelighetsantakelser og et produkt	1
$2^n-1$ eller $a^n-1$	2
binomialkoeffisient med primtall øverst	3
«uendelig mange primtall …»	4
primtall med fast avstand	5

Kort: de fem arketypene med førstegrep

\gcd(m,n)=1

#	Påstanden	Førstegrepet
1	$\gcd(m,n)=1$ , $m\mid k$ , $n\mid k\Rightarrow mn\mid k$	$mx+ny=1$ , gang med $k$ , kryss-substituér
2	$n$ sammensatt $\Rightarrow 2^n-1$ sammensatt	$n=ab$ , faktoriser med $x=2^a$ , begge faktorer $>1$
3	$p\mid\binom pk$ , $1\le k\le p-1$	$k!(p-k)!\binom pk=p!$ + Euklids lemma
4	uendelig mange primtall $\equiv a\pmod m$	$N=m\,p_1\cdots p_r-1$ , case-analyse, «ikke i listen»
5	$p,p+a,p+2a$ primtall, $3\nmid a\Rightarrow p=3$	case-analyse mod $3$ + størrelsesargument

Kort: uttømmende case-analyse

n\equiv r\pmod m

Kort: teoremnavnene som skal skrives

n=qm+r

Navn	Hva det gir	Hvor
divisjonsalgoritmen	$n=qm+r$ , $0\le r<m$ — starter hver case-analyse	kap. 1.1
Euklids lemma	$p\mid ab\Rightarrow p\mid a$ eller $p\mid b$	kap. 1.1
aritmetikkens fundamentalteorem	entydig faktorisering; hvert $n\ge 2$ har en primdivisor	kap. 1.1
Bézouts identitet	$\gcd(a,b)=ax+by$	kap. 1.2
Fermats lille teorem	$a^p\equiv a\pmod p$	kap. 2.2
den geometriske faktoriseringen	$x^d-1=(x-1)(x^{d-1}+\dots+1)$	kap. 6.3
induksjonsprinsippet	avslutningssetningen i hvert induksjonsbevis	kap. 6.2

Kort: kontrollene, samlet

n_0

Kort: tidsbudsjettet for sjanger I og J

n_0

Arbeid	Induksjon	Arketype
Lese, velge teknikk, finne $n_0$	~3 min	~2 min
Skrive mal/antakelser	~2 min	~2 min
Regningen	~6–9 min	~7–10 min
Betingelses- og størrelsessjekker	~1 min	~2 min
Konklusjon + tallkontroll	~3 min	~3 min
Til sammen	15–18 min	16–19 min

Kort: selvdiagnose for Del 6

m

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.