6.1 Bevisteknikker: direkte, kontrapositivt, ved motsigelse og case-analyse

Den generelle bevisverktøykassen for tallteori — direkte, kontrapositivt, ved motsigelse, og uttømmende case-analyse modulo m — som bæres inn i alle delelighets- og primtallsbevisene.

55 min

10 oppgaver

Bevisteknikkerdirektekontrapositivtved motsigelsecase-analyse

Din fremgang i kapitlet

0 / 10 oppgaver

Kapitlets plass i kurset

Bygger på

1.1Delelighet, primtall og aritmetikkens fundamentalteorem

Brukes videre i

6.2Matematisk induksjon: strukturen og de fire undertypene 6.3Delelighets- og primtallsbevis: arketypene 7.3Irrasjonalitet og rasjonale approksimasjoner *(bør kjenne til)*

Bevis er obligatorisk i dette emnet: hvert eneste sett i arkivet har minst én ren bevisoppgave. Delelighets- og primtallsbevis er sjanger I og forekommer i ~8 av 15 sett (~53 %); induksjon er sjanger J og forekommer i 8 av 15 sett (53 %). 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».

Dette kapitlet er ikke selv en sjanger. Det er verktøykassen de to bevissjangrene bruker, og det er den ene ferdigheten i faget som gir uttelling for formen sin, ikke bare for svaret.

Hva oppgaven ber om	Teknikken du velger	Hvor den står
«Vis at hvis … så …»	direkte bevis	dette kapitlet
«Vis at hvis $n^2$ er delelig med $3$ , er $n$ delelig med $3$ »	kontrapositivt bevis	dette kapitlet
«Vis at det ikke finnes heltall med …»	bevis ved motsigelse	dette kapitlet
«Vis at $\dots$ for alle heltall $n$ » (uten $n$ -rekursjon)	uttømmende case-analyse modulo $m$	dette kapitlet
«Vis at $\dots$ for alle $n\ge n_0$ » (formel/rekursjon)	induksjon	kap. 6.2
«Vis at $2^n-1$ er sammensatt når $n$ er sammensatt»	arketypene	kap. 6.3

Den best belagte enkeltfeilen i sjangeren er en ufullstendig case-analyse — en besvarelse som behandler restene

1

2

modulo

3

og glemmer

0

. Løsningsforslagene i arkivet lister rutinemessig alle rester eksplisitt, og det er dokumentert praksis at strukturen teller for seg selv.
Prioritet: høyeste prioritet. Bevisdelen kan ikke reddes med regneferdighet, og den kommer hvert år. Til gjengjeld er teknikkene få: fire maler, og de er ferdig utskrevet i dette kapitlet.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en bestemt, enkel kalkulator. Den regner aritmetikk, og et bevis er ikke aritmetikk. Her har kalkulatoren ingenting å bidra med i det hele tatt — bevisformen er en ferdighet, og den må komme fra hodet.

Må sitte utenat:

- de fire malene — direkte, kontrapositivt, motsigelse, case-analyse — med den første setningen i hver
- at $a\mid b$ betyr «det finnes et helt tall $t$ med $b=at$ », for det er der hvert delelighetsbevis starter
- divisjonsalgoritmen $n=qm+r$ med $0\le r<m$ , som er selve grunnlaget for case-analyse
- at en case-analyse modulo $m$ har nøyaktig $m$ tilfeller, og at alle skal skrives

Utledes på stedet:

- kontrapositiv-ekvivalensen ( $P\Rightarrow Q$ er det samme utsagnet som $\neg Q\Rightarrow\neg P$ ) — én linje med en sannhetsbetraktning, og den står i løkke 2
- kvadrattallenes rester ( $n^2\equiv 0$ eller $1\pmod 3$ ; $n^2\equiv 0$ eller $1\pmod 4$ ; $n^2\equiv 1\pmod 8$ for odde $n$ ) — hver av dem er en case-analyse på to eller tre linjer, ført ut i løkke 4
- at et odde tall kan skrives $2k+1$ og et partall $2k$ — det er paritets-case-analysen med $m=2$

Selvtest, to minutter: dekk til boka og skriv ned åpningssetningen i hver av de fire malene. «Anta at …» er ikke nok — hva antar du, og hva skal du frem til? Klarer du å si hva forskjellen er mellom kontrapositiv og omvending, sitter det som glipper oftest.

Forkunnskaper

Fra boka: kap. 1.1 er den ene forutsetningen — delelighet, divisjonsalgoritmen, primtall, Euklids lemma og aritmetikkens fundamentalteorem. Alt annet i kapitlet bygges fra grunnen.

Du får også bruk for kongruensspråket fra kap. 1.4, men bare i den enkleste formen: at $a\equiv b\pmod m$ betyr at $a$ og $b$ har samme rest ved divisjon med $m$ .

Fra videregående er dette de sterkeste ankrene, og de dekker den generelle bevislogikken: Direkte bevis og moteksempler, Kontrapositiv og kontradiksjon, Bevis i algebra, Matematisk argumentasjon og Lese og forstå bevis. Har du hatt R1, er de fire teknikkene i dette kapitlet kjente navn — det nye er at de brukes på delelighet og primtall, og at kravene til føring er strengere.

Tidsanslag for kapitlet: ~55 minutter lesetid, fordelt på fem løkker à 9–13 minutter. Regner og skriver du med penn underveis, legg til omtrent halvparten.

Hvorfor det ikke holder å prøve seg frem

Se på uttrykket $n^2+n+41$ og sett inn $n=0,1,2,3,\dots$ :
$41,\ 43,\ 47,\ 53,\ 61,\ 71,\ 83,\ 97,\ 113,\ 131,\dots$
Alle er primtall. Fortsetter du, får du primtall for $n=10$ , for $n=20$ , for $n=39$ — førti tall på rad, alle primtall. En rimelig person ville sagt seg overbevist.

Men sett inn $n=40$ :
$40^2+40+41=1681=41^2.$
Ikke et primtall. Førti bekreftelser var verdiløse, fordi påstanden gjaldt alle $n$ .

Det er hele grunnen til at faget krever bevis. En påstand om alle heltall handler om uendelig mange tall, og ingen endelig mengde utregninger kan lukke saken. Et bevis er den eneste konstruksjonen som kan, og et bevis virker ved å stenge alle utveier — ikke ved å vise mange eksempler.

Den gode nyheten er at det bare finnes fire dører inn. Alle bevisene i dette emnet er bygget av fire teknikker:

1. Direkte: anta det som er gitt, regn frem til det som skal vises.
2. Kontrapositivt: vis den logisk likeverdige påstanden «hvis ikke konklusjonen, så ikke hypotesen».
3. Ved motsigelse: anta at påstanden er gal, og utled noe umulig.
4. Ved case-analyse: del alle tall inn i endelig mange klasser, og behandle hver klasse.

Den fjerde er den viktigste i tallteori, og grunnen er enkel: divisjonsalgoritmen deler alle heltall inn i $m$ restklasser modulo $m$ . Uendelig mange tall, endelig mange tilfeller. Det er nettopp der uendeligheten blir håndterbar.

Merk hva dette kapitlet IKKE dekker: påstander der $n+1$ -tilfellet bygger på $n$ -tilfellet. De krever induksjon, og de har sitt eget kapittel (kap. 6.2).

— naturlig pausepunkt —

Løkke 1: Direkte bevis, og å arbeide fra definisjonen

~11 minutter.

Vi starter med den enkleste teknikken, og med den ene vanen som bærer alle delelighetsbevis: å oversette $a\mid b$ til en likning.

Utsagn, implikasjon og ekvivalens

7

Å arbeide fra definisjonen

a\mid b\quad\text{betyr}\quad b=at\ \text{for et helt tall }t.

Direkte bevis

P

✏️Direkte bevis: 8 deler kvadratet av et odde tall minus én

Vis at hvis $n$ er et odde heltall, så er $n^2-1$ delelig med $8$ .

Teknikkvalg. Hypotesen «

n

er odde» er lett å bruke — den gir oss en likning. Altså direkte bevis.

Anta at $n$ er odde. Da finnes det et helt tall $k$ med
$n=2k+1.$

Regn ut $n^2-1$ :
$n^2-1=(2k+1)^2-1=4k^2+4k+1-1=4k^2+4k=4k(k+1).$

Nå er vi nesten der: vi har $4$ utenfor parentesen, og trenger én faktor $2$ mer. Den ligger i $k(k+1)$ .

Delargumentet: $k$ og $k+1$ er to etterfølgende heltall, så ett av dem er et partall (dette er case-analyse med $m=2$ , ført ut i løkke 4). Altså er $k(k+1)=2m$ for et helt tall $m$ .

Sett inn:
$n^2-1=4\cdot 2m=8m.$

Konklusjon. Altså er $n^2-1=8\cdot m$ med $m$ et helt tall, det vil si
$8\mid n^2-1\quad\text{for alle odde }n.\qquad\blacksquare$

Kontroll med tall. $n=3$ : $9-1=8=8\cdot 1$ ✓. $n=5$ : $25-1=24=8\cdot 3$ ✓. $n=7$ : $48=8\cdot 6$ ✓. $n=11$ : $120=8\cdot 15$ ✓.

Om føringen. Legg merke til tre ting som er egne føringspoeng, og som en halv besvarelse mangler:

- Antakelsen er oversatt til en likning ( $n=2k+1$ ) i første linje.
- Delargumentet om $k(k+1)$ er skrevet ut. Å skrive «og $k(k+1)$ er åpenbart partall» er svakere; å si hvorfor (to etterfølgende tall) tar fire ord og lukker hullet.
- Konklusjonen står som en setning med det hele tallet identifisert.

Resultatet er verdt å huske i seg selv: kvadratet av et odde tall er alltid $1$ mer enn et multiplum av $8$ , altså $n^2\equiv 1\pmod 8$ . Det brukes i eksempel 4 og i kap. 7.2.

📝Oppgave 1

Vis direkte at hvis $a\mid b$ , så er $a\mid (b^2+3b)$ .

📝Oppgave 2

Vis at $2\mid n^2+n$ for alle heltall $n$ .

Før beviset på to måter:

a) Direkte ved faktorisering.
b) Ved case-analyse på pariteten til $n$ .

Løkke 2: Kontrapositivt bevis

~10 minutter.

Noen ganger er hypotesen ubrukelig og negasjonen av konklusjonen gullkantet. Da snur du påstanden — og det er ikke et nytt bevis, det er nøyaktig samme påstand skrevet på en annen måte.

📜Kontrapositiv-ekvivalensen

For to utsagn

P

Q

(P\Rightarrow Q)\quad\text{og}\quad(\neg Q\Rightarrow\neg P)

samme utsagn — de er sanne samtidig og falske samtidig.

Utledes på stedet, én linje: $P\Rightarrow Q$ er brutt nøyaktig i det tilfellet der $P$ er sann og $Q$ er falsk. $\neg Q\Rightarrow\neg P$ er brutt nøyaktig i det tilfellet der $\neg Q$ er sann og $\neg P$ er falsk — altså der $Q$ er falsk og $P$ er sann. Det er samme tilfelle. Altså har de to implikasjonene nøyaktig samme brudd-situasjon, og da er de logisk likeverdige. $\blacksquare$

Hva det betyr i praksis: du får velge fritt hvilken av de to du vil bevise. Beviser du den ene, har du bevist den andre. Ingenting går tapt, og du trenger ikke si mer enn «vi viser den kontrapositive påstanden».

Eksempel på oversettelsen:

Påstand	Kontrapositiv
$3\mid n^2\Rightarrow 3\mid n$	$3\nmid n\Rightarrow 3\nmid n^2$
$n^2$ odde $\Rightarrow n$ odde	$n$ partall $\Rightarrow n^2$ partall
$p$ primtall og $p\mid ab\Rightarrow p\mid a$ eller $p\mid b$	$p\nmid a$ og $p\nmid b\Rightarrow p\nmid ab$

Legg merke til mønsteret i den øverste raden: den opprinnelige hypotesen «

3\mid n^2

» sier nesten ingenting du kan regne med. Den kontrapositive hypotesen «

3\nmid n

» sier at

n=3k+1

eller

n=3k+2

— to konkrete likninger. Det er hele gevinsten.

Kontrapositivt bevis

P\Rightarrow Q

Kontrapositiv og omvending — hold dem fra hverandre

P\Rightarrow Q

Navn	Formen	Forholdet til $P\Rightarrow Q$
Kontrapositiv	$\neg Q\Rightarrow\neg P$	samme utsagn — beviser du den, er du ferdig
Omvending	$Q\Rightarrow P$	et annet utsagn — kan godt være falsk

✏️Kontrapositivt bevis: 3 deler n når 3 deler n i annen

Vis at hvis $3\mid n^2$ , så er $3\mid n$ .

Teknikkvalg. Hypotesen «

3\mid n^2

» gir bare

n^2=3t

, og derfra er det ingen vei videre uten et primtallsargument. Negasjonen av konklusjonen, «

3\nmid n

», gir derimot to helt konkrete former for

n

. Altså kontrapositivt bevis.

Vi viser den kontrapositive påstanden: hvis $3\nmid n$ , så er $3\nmid n^2$ .

Anta at $3\nmid n$ . Ved divisjonsalgoritmen (kap. 1.1) er $n=3k+r$ med $r\in\{0,1,2\}$ , og siden $3\nmid n$ er $r\ne 0$ . Det gir to tilfeller, og vi behandler begge.

Tilfelle $r=1$ : $n=3k+1$ , og
$n^2=9k^2+6k+1=3(3k^2+2k)+1.$
Altså har $n^2$ rest $1$ ved divisjon med $3$ , så $3\nmid n^2$ .

Tilfelle $r=2$ : $n=3k+2$ , og
$n^2=9k^2+12k+4=3(3k^2+4k+1)+1.$
Altså har $n^2$ igjen rest $1$ , så $3\nmid n^2$ .

Begge tilfeller er dekket, og i begge er $3\nmid n^2$ . Dermed er den kontrapositive påstanden bevist, og siden en påstand og dens kontrapositive er samme utsagn, er den opprinnelige påstanden bevist:
$3\mid n^2\ \Longrightarrow\ 3\mid n.\qquad\blacksquare$

Kontroll med tall. $n=6$ : $n^2=36$ , $3\mid 36$ og $3\mid 6$ ✓. $n=7$ : $n^2=49=3\cdot 16+1$ , og verken $3\mid 49$ eller $3\mid 7$ ✓. $n=8$ : $64=3\cdot 21+1$ ✓.

Den andre veien — også fullgod. Samme påstand følger på én linje ved Euklids lemma (kap. 1.1): $3$ er et primtall, og $3\mid n\cdot n$ , så $3\mid n$ eller $3\mid n$ — altså $3\mid n$ . Den er kortere, og den er like gyldig.

Hvorfor boka viser begge: løsningsforslagene i arkivet honorerer likeverdige metoder eksplisitt, og det er verdt å kjenne begge veier. Men merk forskjellen i hva de krever: Euklids lemma må navngis for å bære argumentet, mens case-analysen må være uttømmende. Hver vei har sitt eget føringskrav.

Sluttsvar: bevist, både kontrapositivt med uttømmende case-analyse og direkte ved Euklids lemma.

Et biprodukt verdt å ta med: utregningen viste at $n^2\equiv 0$ eller $1\pmod 3$ — aldri $2$ . Det er en av de mest brukte småfaktaene i hele bevisdelen, og den kommer igjen i eksempel 3.

📝Oppgave 3

Vis kontrapositivt at hvis $n^2$ er et odde tall, så er $n$ odde.

Skriv eksplisitt hva den kontrapositive påstanden er, før du beviser den.

📝Oppgave 4

Vis at $n^2$ er delelig med $4$ hvis og bare hvis $n$ er et partall.

Før begge retningene, og si tydelig hvilken du fører når.

Løkke 3: Bevis ved motsigelse

~11 minutter.

Den tredje teknikken, og den som brukes til å vise at noe ikke finnes: ingen heltallsløsning, ingen endelig liste over primtallene, ingen brøkform av $\sqrt 2$ .

— naturlig pausepunkt —

Bevis ved motsigelse

\neg Q

Å negere en påstand riktig

n

Påstand	Negasjon
«for alle $n$ gjelder $A(n)$ »	«det finnes en $n$ med ikke- $A(n)$ »
«det finnes en $n$ med $A(n)$ »	«for alle $n$ gjelder ikke- $A(n)$ »
« $A$ og $B$ »	«ikke- $A$ eller ikke- $B$ »
« $A$ eller $B$ »	«ikke- $A$ og ikke- $B$ »

✏️Motsigelse og case-analyse: en likning uten heltallsløsninger

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

Teknikkvalg. Påstanden er en «det finnes ikke»-påstand. Altså bevis ved motsigelse — og motsigelsen finner vi ved å se på restene modulo

3

, altså med en uttømmende case-analyse.

Anta, for å komme til en motsigelse, at det finnes hele tall $x$ og $y$ med
$x^2-3y^2=2.$

Se på likningen modulo $3$ . Leddet $3y^2$ er delelig med $3$ , så
$x^2\equiv 2\pmod 3.$

Nå viser vi at det er umulig, ved case-analyse på $x$ . Ved divisjonsalgoritmen er $x=3k+r$ med $r\in\{0,1,2\}$ . Vi behandler alle tre:

Tilfelle $r=0$ : $x=3k$ gir $x^2=9k^2=3(3k^2)$ , altså $x^2\equiv 0\pmod 3$ .

Tilfelle $r=1$ : $x=3k+1$ gir $x^2=9k^2+6k+1=3(3k^2+2k)+1$ , altså $x^2\equiv 1\pmod 3$ .

Tilfelle $r=2$ : $x=3k+2$ gir $x^2=9k^2+12k+4=3(3k^2+4k+1)+1$ , altså $x^2\equiv 1\pmod 3$ .

Alle tre tilfellene er dekket, og i ingen av dem er $x^2\equiv 2\pmod 3$ . Kvadrattall har altså bare restene $0$ og $1$ modulo $3$ .

Motsigelsen. Vi har utledet at $x^2\equiv 2\pmod 3$ , og samtidig vist at $x^2\equiv 0$ eller $1\pmod 3$ . Da er $2\equiv 0$ eller $2\equiv 1\pmod 3$ , og ingen av dem holder — motsigelse.

Konklusjon. Antakelsen var gal. Altså har $x^2-3y^2=2$ ingen løsninger i hele tall. $\blacksquare$

Kontroll ved å prøve. De minste kandidatene: $x^2-3y^2$ for $x\le 6$ , $y\le 3$ gir verdiene $1,-2,-11,4,1,-8,9,6,-3,16,13,4,25,22,13,36,33,24$ — og $2$ er ikke blant dem. Prøvingen beviser ingenting (det var poenget i kapitlets åpning), men den bekrefter at vi ikke leter etter en løsning som finnes.

Om føringen — tre ting som er egne poeng:

- Antakelsen står i klartekst på første linje, med «for å komme til en motsigelse».
- Case-analysen er uttømmende: alle tre restene modulo $3$ er behandlet, hver med sin egen utregning. Å hoppe over $r=0$ (fordi «det er jo klart») er den best belagte feilen i sjangeren.
- Motsigelsen er navngitt: vi peker på nøyaktig hvilke to uforenlige utsagn vi har.

Merk valget av modulus. Vi valgte $3$ fordi leddet $3y^2$ da forsvinner — det er nesten alltid slik man finner riktig modulus: velg den som dreper flest ledd. For $x^2-5y^2=2$ ville du valgt $5$ , og for $x^2+y^2=4k+3$ ville du valgt $4$ .

📝Oppgave 5

Vis at likningen $x^2-7y^2=3$ ikke har løsninger i hele tall.

📝Oppgave 6

a) Vis at

5\nmid n^2+n+1

for alle heltall

n

.
b) Bruk a) til å vise at likningen

n^2+n+1=5m

ikke har løsninger i hele tall.

Løkke 4: Uttømmende case-analyse modulo m

~13 minutter.

Nå den teknikken som er tallteoriens egen, og den som gir flest trekk når den slurves. Ideen er enkel og kraftig: divisjonsalgoritmen deler uendelig mange tall inn i endelig mange klasser.

📜Divisjonsalgoritmen — bevisverktøyet bak case-analysen

For hvert helt tall

n

og hvert positivt helt tall

m

finnes det entydige hele tall

q

r

med

n=qm+r,\qquad 0\le r<m.

Dette er divisjonsalgoritmen fra kap. 1.1, og i bevissammenheng leses den som en inndeling:

$\text{alle heltall}=\underbrace{\{qm\}}_{r=0}\cup\underbrace{\{qm+1\}}_{r=1}\cup\dots\cup\underbrace{\{qm+(m-1)\}}_{r=m-1}.$

De $m$ klassene dekker alt (fordi $r$ finnes for hver $n$ ) og overlapper ikke (fordi $q$ og $r$ er entydige). Det er nøyaktig det en case-analyse trenger.

Konsekvensen, og hele poenget: for å vise en påstand om alle heltall, holder det å vise den for $m$ tilfeller — én per rest. Uendelig mange tall, $m$ utregninger.

Hvordan du velger $m$ : velg den modulusen som gjør uttrykket enklest. Tre gjenkjennelige situasjoner:

- Skal du vise at noe er delelig med $d$ , prøv $m=d$ først.
- Er det et ledd med faktor $d$ i uttrykket, dreper $m=d$ det leddet.
- Handler påstanden om primtall større enn $3$ , er $m=3$ og $m=2$ (eller $m=6$ ) nesten alltid riktig — for da er $r=0$ utelukket allerede av at tallet er primtall.

Merk at du kan regne med representanten. Kongruensregnereglene (kap. 1.4) sier at $n\equiv r$ gir $n^2\equiv r^2$ , $n^3\equiv r^3$ og så videre. Derfor holder det å sette inn $r$ i uttrykket — du behøver ikke skrive ut $(qm+r)^2$ i full bredde. Si at du bruker regnereglene, så er snarveien begrunnet.

Case-analyse modulo m

m

Kvadrattall modulo 3, 4 og 8

n^2\equiv 0\ \text{eller}\ 1\pmod 3,\qquad n^2\equiv 0\ \text{eller}\ 1\pmod 4,\qquad n^2\equiv 1\pmod 8\ (n\ \text{odde}).

✏️Eksamensnivå: 24 deler kvadratet av et primtall større enn 3, minus én

La $p$ være et primtall med $p>3$ . Vis at $24\mid p^2-1$ .

Teknikkvalg. Påstanden gjelder alle primtall over

3

, altså uendelig mange tall. Men

24=8\cdot 3

, og

\gcd(8,3)=1

— så vi kan vise delelighet med

8

og med

3

hver for seg og sette dem sammen. Begge delene er case-analyser.

Steg 1: $8\mid p^2-1$ .

Siden $p$ er et primtall større enn $3$ , er $p$ odde (ellers ville $2\mid p$ ). Fra eksempel 1 vet vi da at
$8\mid p^2-1.$

Utledningen, gjentatt kort: $p=2k+1$ gir $p^2-1=4k(k+1)$ , og $k(k+1)$ er et partall siden det er to etterfølgende heltall. Altså $p^2-1=8m$ .

Steg 2: $3\mid p^2-1$ .

Ved divisjonsalgoritmen er $p\equiv r\pmod 3$ med $r\in\{0,1,2\}$ . Vi behandler alle tre:

Tilfelle $r=0$ : da er $3\mid p$ . Men $p$ er et primtall større enn $3$ , så den eneste divisoren over $1$ er $p$ selv — og $3\ne p$ . Dette tilfellet er utelukket.

Tilfelle $r=1$ : $p=3k+1$ gir
$p^2-1=(3k+1)^2-1=9k^2+6k=3(3k^2+2k),$
altså $3\mid p^2-1$ .

Tilfelle $r=2$ : $p=3k+2$ gir
$p^2-1=(3k+2)^2-1=9k^2+12k+3=3(3k^2+4k+1),$
altså $3\mid p^2-1$ .

Alle tre tilfellene er dekket — ett utelukket, to regnet ut — og i de mulige tilfellene er $3\mid p^2-1$ .

Steg 3: sett sammen.

Vi har $8\mid p^2-1$ og $3\mid p^2-1$ , og $\gcd(8,3)=1$ . Da er $8\cdot 3=24$ en divisor i $p^2-1$ — det er arketypen «relativt primiske $\Rightarrow$ produktet deler», som føres komplett i kap. 6.3.

Argumentet i én linje, for fullstendighetens skyld: $p^2-1=8a=3b$ . Da er $3\mid 8a$ , og siden $\gcd(3,8)=1$ gir Euklids lemma (kap. 1.1) at $3\mid a$ , altså $a=3c$ og $p^2-1=24c$ .

Konklusjon. For hvert primtall $p>3$ er
$24\mid p^2-1.\qquad\blacksquare$

Kontroll med tall.

$p$	$p^2-1$	$(p^2-1)/24$
$5$	$24$	$1$ ✓
$7$	$48$	$2$ ✓
$11$	$120$	$5$ ✓
$13$	$168$	$7$ ✓
$17$	$288$	$12$ ✓

Hvorfor $p>3$ er nødvendig:

p=3

gir

p^2-1=8

, og

24\nmid 8

p=2

gir

3

, og

24\nmid 3

. Betingelsen i oppgaveteksten er ikke pynt — den er det som utelukker tilfellet

r=0

og sikrer at

p

er odde. En besvarelse som ikke bruker den, har et hull.
Om føringen — de fire tingene som gir uttelling hver for seg:
1. Oppsplittingen i $8$ og $3$ er begrunnet med at de er relativt primiske. Uten den begrunnelsen er sammensettingen i steg 3 et sprang.
2. Case-analysen er uttømmende, og tilfellet

r=0

er utelukket med et argument — ikke bare utelatt.
3. Teoremet er navngitt der det bærer (Euklids lemma i steg 3).
4. Konklusjonen er en setning med kvantoren på plass («for hvert primtall

p>3

»).

Merk den generelle strategien, som er verdt mer enn dette ene resultatet: for å vise delelighet med et sammensatt tall, splitt i relativt primiske faktorer og vis hver for seg. $24=8\cdot 3$ , $30=2\cdot 3\cdot 5$ , $12=4\cdot 3$ . Det gjør case-analysen mye kortere enn en direkte analyse modulo $24$ ville vært — som ville krevd tjuefire tilfeller.

📝Oppgave 7

Vis at $4\nmid n^2+2$ for alle heltall $n$ .

📝Oppgave 8

Vis at $6\mid n^3-n$ for alle heltall $n$ .

Før beviset på to måter:

a) Ved faktorisering pluss delelighet med $2$ og $3$ hver for seg.
b) Ved en uttømmende case-analyse modulo $6$ .

Løkke 5: Moteksempler, og å velge teknikk

~10 minutter.

Til slutt den motsatte oppgaven — å felle en påstand — og beslutningstabellen som knytter de fire teknikkene til det oppgaveteksten sier.

— naturlig pausepunkt —

Allpåstand, eksistenspåstand og moteksempel

n

Form	Sannhetsbevis krever	Falskhetsbevis krever
«for alle $n$ : $A(n)$ »	et generelt argument	ett moteksempel
«det finnes en $n$ : $A(n)$ »	ett eksempel	et generelt argument

Å velge bevisteknikk

P

Det oppgaven ser slik ut	Teknikk	Første setning du skriver
«hvis $P$ så $Q$ », og $P$ er en likning eller delelighet	direkte	«Anta at $P$ . Da finnes $t$ med …»
«hvis $P$ så $Q$ », og $\neg Q$ er lettere å bruke enn $P$	kontrapositivt	«Vi viser den kontrapositive: hvis $\neg Q$ , så $\neg P$ .»
«det finnes ikke …», « $\dots$ er irrasjonal», «uendelig mange …»	motsigelse	«Anta, for å komme til en motsigelse, at …»
«for alle heltall $n$ …» uten rekursjon	case-analyse modulo $m$	«Ved divisjonsalgoritmen er $n\equiv r\pmod m$ …»
«for alle $n\ge n_0$ », formel eller rekursjon	induksjon (kap. 6.2)	«Basissteg: $P(n_0)$ …»
«avgjør om …»	let etter moteksempel først	«Påstanden er falsk. Ta $n=\dots$ »

✏️Å felle en påstand: moteksempel og hva et moteksempel ikke gjør

Avgjør om påstanden er sann: «For alle heltall $n\ge 0$ er $n^2+n+41$ et primtall.»

Les oppgaveteksten. Det står «avgjør om», ikke «vis at». Begge utfall er altså i spill, og vi må si hvilket.

Steg 1: prøv noen verdier.

$n$	$n^2+n+41$	primtall?
$0$	$41$	ja
$1$	$43$	ja
$2$	$47$	ja
$5$	$71$	ja
$10$	$151$	ja
$20$	$461$	ja
$39$	$1601$	ja

Sju treff, og faktisk holder påstanden for alle

n

fra

0

til

39

. Det er et sterkt inntrykk — og det er verdiløst som bevis.
Steg 2: se etter struktur. Leddet

41

er en primtallsfaktor som venter på å bli felles. Setter vi

n=41

, får vi

41^2+41+41=41(41+1+1)=41\cdot 43,

som åpenbart er sammensatt. Men vi kan gjøre det ett hakk tidligere: for

n=40

40^2+40+41=1600+40+41=1681.

Er $1681$ et primtall?

41^2=1681

. Altså

40^2+40+41=41^2=41\cdot 41,

som er sammensatt.

Steg 3: konklusjon. Påstanden er falsk. Moteksempelet er $n=40$ : der er $n^2+n+41=1681=41^2$ , som har divisoren $41$ og derfor ikke er et primtall. $\blacksquare$

Hva de førti bekreftelsene var verdt. Ingenting, som bevis. Påstanden «for alle $n$ » handler om uendelig mange tall, og førti er ikke uendelig mange. Ett moteksempel feller en allpåstand; ingen endelig mengde eksempler bekrefter den.
Den relaterte sanne påstanden, som viser hvor fint skillet er: for $0\le n\le 39$ er $n^2+n+41$ et primtall. Det er en påstand om førti tall, og den kan bevises ved å regne ut alle førti — en uttømmende case-analyse med førti tilfeller. Sant, men uinteressant, og ikke det oppgaven spurte om.
Om føringen. To ting bærer besvarelsen:

- Moteksempelet er regnet ut, ikke bare oppgitt: $1681=41^2$ står der, med faktoriseringen synlig.

- Konklusjonen er en setning som sier at påstanden er falsk. Et tall alene er ikke et svar.
Merk hvorfor $n=40$ og $n=41$ begge virker, og hvorfor det ikke er tilfeldig: $n^2+n+41$ er delelig med $41$ nøyaktig når $n^2+n\equiv 0\pmod{41}$ , altså når $41\mid n(n+1)$ — altså når $n\equiv 0$ eller $n\equiv 40\pmod{41}$ . Ved Euklids lemma er det de eneste mulighetene. Det er en case-analyse som forklarer moteksempelet i stedet for bare å oppgi det, og den typen innsikt er det som skiller et godt svar fra et riktig svar.

📝Oppgave 9

Avgjør om påstandene er sanne. Bevis dem som er sanne, og gi et moteksempel til dem som er falske.

a) For alle heltall $n$ er $n^2+n+1$ et odde tall.
b) For alle heltall $n\ge 1$ er $2^n-1$ et primtall.
c) For alle primtall $p$ er $2^p-1$ et primtall.

📝Oppgave 10

La $p$ være et primtall med $p>3$ . Vis at $p\equiv 1$ eller $p\equiv 5\pmod 6$ .

Bruk deretter dette til å vise at $p^2\equiv 1\pmod{12}$ for alle primtall $p>3$ .

Typiske feil

De fem feilene under er dokumentert i arkivets løsningsforslag som noe fasitene fører eksplisitt imot — og de er alle strukturfeil, ikke regnefeil. Det er verdt å merke seg: i bevisdelen er det formen som glipper, ikke aritmetikken.

- Ufullstendig case-analyse. Den best belagte enkeltfeilen i hele bevisdelen. En besvarelse behandler restene $1$ og $2$ modulo $3$ og glemmer $0$ — eller behandler « $n$ odde» og glemmer « $n$ partall». Kontrollen tar fem sekunder: tell radene. En case-analyse modulo $m$ har nøyaktig $m$ rader, med mindre du skriver hvorfor noen er utelukket eller speilbilder av andre.

- Å bevise en allpåstand med eksempler. «Jeg prøvde $n=1,2,3,4,5$ og det stemte» er ikke et bevis, og det gir ikke delvis uttelling. $n^2+n+41$ ga førti riktige og var likevel falsk. Regelen: eksempler kan felle en allpåstand, aldri bekrefte den.

- Bare én retning vist i en «hvis og bare hvis»-oppgave. Ekvivalens er to implikasjoner. Ser du ordene «hvis og bare hvis», «nøyaktig når» eller «ekvivalent med», skal to bevis stå — eller en kjede der hvert ledd er en ekvivalens. Skriv hvilken retning du fører når, så ser den som retter at begge er der.

- Kontrapositiv forvekslet med omvending. Å bevise $Q\Rightarrow P$ når oppgaven ba om $P\Rightarrow Q$ er å bevise en annen påstand. Kontrollen: i den kontrapositive skal begge deler være negert og rekkefølgen byttet. Er bare rekkefølgen byttet, er du på feil spor.

- Ikke arbeide fra definisjonen. Et delelighetsbevis som aldri skriver $b=at$ , har ingenting å regne med. Første linje i et delelighetsbevis er oversettelsen, og den er egne poeng.

Og tre føringsfeil som koster uten å være feil i matematikken:

- Teoremet ikke navngitt. Bruker du Euklids lemma eller aritmetikkens fundamentalteorem, skal navnet stå. Instruksen på hvert eksamenssett er at alle svar skal begrunnes, og i bevisdelen er navnet på resultatet en del av begrunnelsen.
- Motsigelsesbeviset renner ut. Du treffer noe merkelig og skriver «umulig». Pek på de to uforenlige utsagnene, og trekk konklusjonen: «altså finnes det ingen slike tall».
- Samme bokstav for to ulike faktorer. $b=at$ og $c=at$ antar i tillegg at $b=c$ . Bruk $t$ og $u$ .

Begrepsbank

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

Under kode D er banken eksamensverktøyet, ikke pynt. Det finnes ingen mal å slå opp i 24. november, og bevismalene er nettopp det som må komme ferdig ut av hodet når du leser oppgaven. Merk at kortene her er former, ikke fakta: de pugges ved å brukes. Å skrive tre case-analyser med lukket bok er mer verdt enn tre gjennomlesninger.

Kort: de fire malene, og valget mellom dem

P

Ser du …	Velg
«hvis … så …» med en likning i hypotesen	direkte
konklusjon som er lett å negere ( $d\mid n$ , «odde»)	kontrapositivt
«det finnes ikke», «irrasjonal», «uendelig mange»	motsigelse
«for alle heltall $n$ », delelighet med et lite tall	case-analyse modulo $d$
«for alle $n\ge n_0$ », sumformel, rekursjon	induksjon (kap. 6.2)
«avgjør om», «er det sant at»	let etter moteksempel først

Kort: fra definisjonen

a\mid b\iff b=at\ \text{for et helt tall }t.

Kort: hva «uttømmende» betyr

m

Kort: kvadrattall modulo 3, 4 og 8, og paritet

n^2\equiv 0,1\pmod 3\qquad n^2\equiv 0,1\pmod 4\qquad n^2\equiv 1\pmod 8\ (n\ \text{odde})

Likning	Modulus	Hvorfor den er uløselig
$x^2-3y^2=2$	$3$	krever $x^2\equiv 2$
$x^2+y^2=4k+3$	$4$	to kvadrater gir rest $0,1,2$
$x^2-8y^2=3$	$8$	krever $x^2\equiv 3$

Kort: teoremnavnene du skal bære

n=qm+r

Navn	Hva det sier	Hvor det står
divisjonsalgoritmen	$n=qm+r$ , $0\le r<m$ , entydig	kap. 1.1
Euklids lemma	$p$ primtall, $p\mid ab\Rightarrow p\mid a$ eller $p\mid b$	kap. 1.1
aritmetikkens fundamentalteorem	entydig primtallsfaktorisering	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

Kort: «hvis og bare hvis» i to retninger

\iff

Kort: «uendelig mange»-malen

A

Kort: oversettelsene du gjør uten å tenke

a

Ord	Likning
« $a$ deler $b$ »	$b=at$ , $t$ helt
« $a$ deler ikke $b$ »	$b=at+r$ , $1\le r\le a-1$
« $n$ er et partall»	$n=2k$
« $n$ er odde»	$n=2k+1$
« $n$ er et kvadrattall»	$n=m^2$
« $p$ er et primtall»	$p>1$ , og de eneste positive divisorene er $1$ og $p$
« $a$ og $b$ er relativt primiske»	$\gcd(a,b)=1$ , altså $ax+by=1$ for noen $x,y$ (Bézout)
« $n$ er sammensatt»	$n=ab$ med $1<a,b<n$
« $a\equiv b\pmod m$ »	$a-b=mt$ , altså $m\mid a-b$

Kort: skriveraden, og de tre ugyldige argumentformene

0=0

Kort: tidsbudsjettet for en bevisoppgave

Eksamen er 4 timer på rundt ti likt vektede delpunkt, altså ~24 minutter per delpunkt . Arbeid Tid Lese oppgaven og velge teknikk ~2 min Skrive malens første setning og oversette antakelsene ~2 min Regningen (case-analyse, algebra) ~6-10 min Konklusjonssetning og opprydding ~2 min Kontroll med to-tre tallverdier ~2 min Til sammen 14-18 minutter for et rent bevisdelpunkt. Er oppgaven todelt (lemma i a, anvend i b), regn med hele budsjettet på ~24 minutter for begge. Hvor tiden går galt: i letingen etter riktig teknikk. Bruk tabellen i «velg teknikk»-kortet — tjue sekunder der sparer fem minutters famling. Hva du IKKE skal bruke tid på: å prøve mange tallverdier før du starter. To verdier er nok til å forstå påstanden; flere er tidsbruk uten uttelling. Unntaket er «avgjør om»-oppgaver, der du faktisk leter etter et moteksempel. Realistisk forventning: en bevisoppgave er det delpunktet der struktur alene henter mye. Selv om du ikke kommer helt frem, gir riktig mal med riktig antakelse og en påbegynt case-analyse uttelling — mens et riktig svar uten struktur gir lite.

Arbeid	Tid
Lese oppgaven og velge teknikk	~2 min
Skrive malens første setning og oversette antakelsene	~2 min
Regningen (case-analyse, algebra)	~6–10 min
Konklusjonssetning og opprydding	~2 min
Kontroll med to–tre tallverdier	~2 min

Kort: selvdiagnose for bevisteknikk

a\mid b

Repetisjonsoppgaver

Symbol- og formelliste

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

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