6.3 Delelighets- og primtallsbevis: arketypene

De fem faste bevisarketypene: relativt primiske ⇒ mn|k, 2ⁿ−1 sammensatt når n er sammensatt, p|C(p,k), uendelig mange primtall av en type, og primtall-tvillingtypen (p, p+8, p+16) via case-analyse modulo 3.

60 min

10 oppgaver

Delelighets-primtallsbevisarketypene

Din fremgang i kapitlet

0 / 10 oppgaver

Kapitlets plass i kurset

Bygger på

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

Brukes videre i

6.4Drill: induksjon og delelighets-/primtallsbevis

Delelighets- og primtallsbevis er sjanger I og forekommer i ~8 av 15 sett — ~53 %. Sammen med induksjon (sjanger J, 8 av 15) betyr det at hvert eneste sett 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».

Det gode med sjangeren er at den er arketypisk: arkivet bruker fem faste påstandsformer om og om igjen, med nye tall. Kjenner du de fem, kjenner du sjangeren.

Arketype	Påstanden	Verktøyet
1	$\gcd(m,n)=1$ , $m\mid k$ , $n\mid k$ $\Rightarrow mn\mid k$	fundamentalteoremet, Bézout eller Euklids lemma
2	$2^n-1$ er sammensatt når $n$ er sammensatt	geometrisk sum-faktorisering
3	$p\mid\binom pk$ for $1\le k\le p-1$	$k!(p-k)!\binom pk=p!$ og Euklids lemma
4	det finnes uendelig mange primtall av en gitt form	Euklid-stil motsigelse
5	$p$ , $p+8$ , $p+16$ alle primtall $\Rightarrow p=3$	case-analyse modulo $3$

Formen oppgaven kommer i, er ofte todelt: del a beviser et lemma, del b anvender det. Arkivets nyere sett bruker den formen jevnlig, og den er verdt å kjenne igjen — for da vet du at del a skal brukes i del b, og at du har fått halve løsningen gratis.
De to best belagte feilene i sjangeren: en ufullstendig case-analyse (en glemt rest), og et argument der teoremet som bærer det, ikke er navngitt. Begge er føringsfeil, og begge koster selv når matematikken er riktig.
Prioritet: høyeste prioritet. Sjangeren kommer hvert år, arketypene er fem, og de er alle ført komplett i dette kapitlet.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en bestemt, enkel kalkulator. Arketypene er former, ikke fakta, og de kan ikke slås opp. Det som må sitte, er hvilken påstand som hører til hvilket argument.

Må sitte utenat:

- de fem arketypene med sitt førstegrep — se tabellen over
- Euklids lemma ( $p$ primtall, $p\mid ab\Rightarrow p\mid a$ eller $p\mid b$ ) og aritmetikkens fundamentalteorem, med navn
- den geometriske faktoriseringen $x^n-1=(x-1)(x^{n-1}+\dots+x+1)$ , og den generelle formen $x^d-1\mid x^n-1$ når $d\mid n$
- Euklid-trikset: i «uendelig mange primtall»-bevis konstruerer du et tall av produktet av den antatte listen, pluss eller minus $1$
- at et primtall $p>3$ har $p\equiv 1$ eller $2\pmod 3$ — det er utelukkelsen som starter arketype 5

Utledes på stedet:

- Bézout-veien til arketype 1 — tre linjer: $\gcd(m,n)=1$ gir $mx+ny=1$ , gang med $k$ , og bruk at $mn$ deler begge ledd. Ført ut i løkke 1.
- $p\mid\binom pk$ — tre linjer fra $k!(p-k)!\binom pk=p!$ og Euklids lemma. Ført ut i løkke 3.
- $\sigma$ -formelen for den geometriske summen $\displaystyle 1+x+\dots+x^{d-1}=\frac{x^d-1}{x-1}$ — én linje ved å gange opp. Ført ut i løkke 2.
- at $30\mid n^5-n$ — delelighet med $2$ , $3$ og $5$ hver for seg, og så arketype 1. Ført ut i oppgave 10.

Selvtest, tre minutter: dekk til boka og skriv ned de fem arketypene med ett stikkord for argumentet i hver. Klarer du i tillegg å si hvilke tre ulike veier som fører til arketype 1, sitter kapitlets kjerne — for det er det stedet i faget der fasitpraksisen tydeligst honorerer likeverdige metoder.

Forkunnskaper

Fra boka: kap. 6.1 (de fire bevisteknikkene, og særlig case-analyse og motsigelse) og kap. 1.1 (delelighet, Euklids lemma, aritmetikkens fundamentalteorem, og motsigelsesbeviset for at det finnes uendelig mange primtall). Til arketype 1 får du bruk for Bézout fra kap. 1.2, og til arketype 3 binomialkoeffisientene fra kap. 2.2.

Sist du var her. De tre resultatene dette kapitlet står helt på, ferdig oppfrisket:

Euklids lemma. Er $p$ et primtall og $p\mid ab$ , så er $p\mid a$ eller $p\mid b$ . Kravet om at $p$ er primtall er nødvendig: $6\mid 4\cdot 9$ , men $6\nmid 4$ og $6\nmid 9$ .

Aritmetikkens fundamentalteorem. Hvert helt tall $n\ge 2$ har en primtallsfaktorisering
$n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r},$
og den er entydig opp til rekkefølgen på faktorene.

Bézouts identitet. For alle hele tall $a,b$ finnes det hele tall $x,y$ med
$\gcd(a,b)=ax+by,$
og koeffisientene leses ut av Euklids algoritme baklengs (kap. 1.2). Spesielt: er $\gcd(a,b)=1$ , finnes $x,y$ med $ax+by=1$ .

Fra videregående: Direkte bevis og moteksempler, Kontrapositiv og kontradiksjon og Bevis i algebra dekker bevislogikken; delelighetsteorien bygges fra grunnen i boka.

Tidsanslag for kapitlet: ~60 minutter lesetid, fordelt på fem løkker à 10–14 minutter — én per arketype. Regner og skriver du med penn underveis, legg til omtrent halvparten.

Fem påstander som kommer igjen

Se på disse fem oppgavetekstene, hentet fra fem ulike årganger i arketypisk form:

- «Vis at hvis $\gcd(m,n)=1$ og både $m$ og $n$ deler $k$ , så deler $mn$ tallet $k$ .»
- «Vis at $2^n-1$ er sammensatt når $n$ er sammensatt.»
- «Vis at $p$ deler $\binom pk$ for $1\le k\le p-1$ .»
- «Vis at det finnes uendelig mange primtall som er kongruent med $2$ modulo $3$ .»
- «Vis at det eneste primtallet $p$ der også $p+8$ og $p+16$ er primtall, er $p=3$ .»

De ser ut som fem helt ulike oppgaver. De er fem faste arketyper, og hver av dem har ett bestemt førstegrep. Tallene skifter fra år til år — $2^n-1$ kan bli $3^n-1$ , $p+8,p+16$ kan bli $p+4,p+8$ , modulo $3$ kan bli modulo $4$ — men argumentet er det samme.

Det er derfor denne sjangeren er så lønnsom å forberede. Til forskjell fra en regnesjanger, der du må gjøre arbeidet på nytt hver gang, kan et bevisargument gjenkjennes. Bruker du to minutter på å se hvilken arketype oppgaven er, har du resten av veien kartlagt.

Hverdagsankeret for arketype 1, den mest brukte av de fem: tenk på et tannhjul som møter start hvert $m$ -te steg og et annet som møter start hvert $n$ -te steg. Når møter begge start samtidig? Etter $mn$ steg — men bare hvis periodene ikke har noen felles faktor. Har de en felles faktor, kommer sammentreffet tidligere, og $mn$ er ikke svaret. Det er nøyaktig hva betingelsen $\gcd(m,n)=1$ gjør i arketypen.

Og en advarsel om hva som IKKE er nok. Arketype 1 er falsk uten primiskhets-betingelsen: $4\mid 12$ og $6\mid 12$ , men $24\nmid 12$ . Å bruke arketypen uten å sjekke $\gcd$ -en er en dokumentert felle, og den er lett å unngå — én linje.

— naturlig pausepunkt —

Løkke 1: Arketype 1 — relativt primiske faktorer

~14 minutter.

Den mest brukte av de fem, og den ene der arkivets fasiter eksplisitt honorerer tre ulike veier. Vi fører alle tre komplett.

📜Arketype 1: relativt primiske faktorer deler produktet

m,n,k

være positive hele tall med

\gcd(m,n)=1,\qquad m\mid k,\qquad n\mid k.

Da er

mn\mid k.

Betingelsen $\gcd(m,n)=1$ er nødvendig. Moteksempel uten den: $m=4$ , $n=6$ , $k=12$ . Da er $4\mid 12$ og $6\mid 12$ , men $24\nmid 12$ . Grunnen er at $4$ og $6$ deler faktoren $2$ , så « $4$ ganger $6$ » teller den faktoren to ganger.

Tre fullgode bevis. Løsningsforslagene i arkivet godtar alle tre, og det er verdt å kunne minst to — den ene kan være stengt hvis oppgaven har gitt deg opplysninger i en bestemt form.

Vei A — via Bézout (kap. 1.2). Utledes på stedet, tre linjer.

Siden $\gcd(m,n)=1$ , finnes hele tall $x,y$ med
$mx+ny=1.$
Gang med $k$ :
$k=kmx+kny.$
Nå er $n\mid k$ , så $k=nc$ for et helt tall $c$ , og $m\mid k$ , så $k=md$ for et helt tall $d$ . Sett $k=nc$ i det første leddet og $k=md$ i det andre:
$k=(nc)mx+(md)ny=mn(cx+dy).$
Siden $cx+dy$ er et helt tall, er $mn\mid k$ . $\blacksquare$

Vei B — via Euklids lemma (kap. 1.1).

Skriv $k=md$ for et helt tall $d$ (fra $m\mid k$ ). Fra $n\mid k$ har vi $n\mid md$ . Siden $\gcd(m,n)=1$ , deler ikke $n$ noen del av $m$ — presist: ved Euklids lemma, anvendt på hver primfaktor $q$ i $n$ , følger det at $q$ må dele $d$ (den kan ikke dele $m$ , for da ville $q$ vært en felles divisor i $m$ og $n$ ). Gjentar vi for alle primfaktorer med multiplisitet, får vi $n\mid d$ , altså $d=ne$ og
$k=md=mne.$
Altså $mn\mid k$ . $\blacksquare$

Vei C — via aritmetikkens fundamentalteorem (kap. 1.1).

Se på primtallsfaktoriseringene. For hvert primtall $p$ skriv $v_p(x)$ for eksponenten til $p$ i $x$ . Da betyr $m\mid k$ at $v_p(m)\le v_p(k)$ for alle $p$ , og likeså for $n$ . Siden $\gcd(m,n)=1$ , har $m$ og $n$ ingen felles primfaktorer, så for hvert $p$ er minst én av $v_p(m)$ , $v_p(n)$ lik $0$ . Derfor er
$v_p(mn)=v_p(m)+v_p(n)=\max\bigl(v_p(m),v_p(n)\bigr)\le v_p(k)$
for alle $p$ , og dermed $mn\mid k$ . $\blacksquare$

Hvilken vei er raskest? Vei A, hvis du er trygg på Bézout — den er tre linjer og krever ingen omtale av primtall. Vei C er den mest gjennomsiktige. Vei B er den fasitene oftest fører. Ingen av dem er feil, og du skal aldri kalle en annen students vei feil fordi den ikke er din.

Arketype 1 og de tre veiene

\gcd(m,n)=1

Vei	Førstegrep	Lengde
Bézout	$mx+ny=1$ , gang med $k$	tre linjer
Euklids lemma	$k=md$ , vis at $n\mid d$	fire linjer
Fundamentalteoremet	sammenlign eksponenter primtall for primtall	fem linjer

✏️Arketype 1 anvendt: delelighet med 15

a) Vis at hvis

3\mid k

5\mid k

, så er

15\mid k

.
b) Gjelder det samme med

4

6

i stedet for

3

5

, altså at

4\mid k

6\mid k

gir

24\mid k

? Begrunn.

a) Arketype 1, ført med Bézout-veien.

Først vilkåret: $\gcd(3,5)=1$ , siden $3$ og $5$ er ulike primtall. Denne linjen skal stå — den er det arketypen krever.

Bézout (kap. 1.2) gir hele tall $x,y$ med $3x+5y=1$ . Konkret finner vi dem ved inspeksjon:
$3\cdot 2+5\cdot(-1)=6-5=1,$
så $x=2$ , $y=-1$ .

Gang likningen med $k$ :
$k=3\cdot 2k+5\cdot(-1)k=6k-5k.$

Nå bruker vi antakelsene. Fra $5\mid k$ er $k=5c$ , og fra $3\mid k$ er $k=3d$ , med $c,d$ hele tall. Sett $k=5c$ i det første leddet og $k=3d$ i det andre:
$k=3\cdot 2\cdot(5c)+5\cdot(-1)\cdot(3d)=15(2c)-15(d)=15(2c-d).$

Siden $2c-d$ er et helt tall, er $15\mid k$ . $\blacksquare$

Kontroll med tall. $k=30$ : $3\mid 30$ , $5\mid 30$ , og $15\mid 30$ ✓. $k=45$ : $3\mid 45$ , $5\mid 45$ , $15\mid 45$ ✓.

Den korte veien, også fullgod — via Euklids lemma. Fra $3\mid k$ er $k=3d$ . Fra $5\mid k$ er $5\mid 3d$ , og siden $5$ er et primtall som ikke deler $3$ , gir Euklids lemma at $5\mid d$ . Altså $d=5e$ og $k=15e$ . To linjer, og like gyldig.

b) Nei — og moteksempelet er lite.

Ta $k=12$ :
- $4\mid 12$ ✓ ( $12=4\cdot 3$ )
- $6\mid 12$ ✓ ( $12=6\cdot 2$ )
- $24\mid 12$ ? Nei, siden $12<24$ .

Altså holder ikke påstanden. $\blacksquare$

Hvorfor den feiler, presist. Arketypen krever $\gcd(m,n)=1$ , og
$\gcd(4,6)=2\ne 1.$
Faktoren $2$ finnes i både $4$ og $6$ , så produktet $4\cdot 6=24$ teller den to ganger. Det riktige svaret er ikke $mn$ , men det minste felles multiplum:
$\operatorname{lcm}(4,6)=12,$
og $12\mid k$ gjelder faktisk (og er det beste man kan si).

Den generelle riktige formen er derfor: er $m\mid k$ og $n\mid k$ , så er $\operatorname{lcm}(m,n)\mid k$ . Og siden $\displaystyle \operatorname{lcm}(m,n)=\frac{mn}{\gcd(m,n)}$ (kap. 1.1), faller den sammen med arketypen nøyaktig når $\gcd(m,n)=1$ .

Om føringen — tre ting som gir uttelling:

1. $\gcd$ -linjen står i a). Uten den er arketypen brukt uten belegg.
2. Bézout-koeffisientene er funnet, ikke antatt. « $3\cdot 2+5\cdot(-1)=1$ » med tall.
3. Moteksempelet i b) er regnet ut, og forklaringen peker på nøyaktig hvilken betingelse som brøt.

Merk at b) er den viktigste halvparten av eksempelet. Å kunne arketypen uten å kunne betingelsen er å ha et verktøy uten sikring — og fellen «brukte arketypen på ikke-primiske faktorer» er dokumentert i arkivets typiske feil.

📝Oppgave 1

Vis at hvis $7\mid k$ og $11\mid k$ , så er $77\mid k$ . Bruk arketype 1, og skriv $\gcd$ -linjen eksplisitt.

📝Oppgave 2

Vis at hvis $\gcd(m,n)=1$ , $m\mid k$ og $n\mid k$ , så er $mn\mid k$ — via Bézout.

Forklar til slutt hvor i beviset betingelsen $\gcd(m,n)=1$ ble brukt.

Løkke 2: Arketype 2 — to i n-te minus én er sammensatt

~12 minutter.

Den mest algebraiske av de fem, og den som hviler på én faktorisering du bør kunne kaldt.

Den geometriske faktoriseringen

x

📜Arketype 2: to i n-te minus én er sammensatt når n er sammensatt

n

være et sammensatt tall, altså

n=ab

med

1<a<n

1<b<n

. Da er

2^n-1\ \text{sammensatt}.

Bevis. Skriv $n=ab$ med $a,b\ge 2$ . Ved den geometriske faktoriseringen med $x=2^a$ og $m=b$ :
$2^n-1=2^{ab}-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).$

Vi har altså skrevet $2^n-1$ som et produkt av to faktorer. Nå må vi vise at ingen av dem er $1$ — det er den delen som glemmes, og uten den er ikke beviset ferdig:

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

Begge faktorene er dermed ekte, og $2^n-1$ er sammensatt. $\blacksquare$

Kontroll med tall.

$n$	faktorisering av $n$	$2^n-1$	faktorer fra beviset
$4$	$2\cdot 2$	$15$	$2^2-1=3$ og $5$
$6$	$2\cdot 3$	$63$	$2^2-1=3$ og $21$
$9$	$3\cdot 3$	$511$	$2^3-1=7$ og $73$
$15$	$3\cdot 5$	$32\,767$	$2^3-1=7$ og $4681$

Den kontrapositive formen, som ofte er det oppgaven ber om: er

2^n-1

et primtall, må

n

være et primtall. Det er samme utsagn (kap. 6.1), og du kan velge fritt hvilken du fører.
⚠ Den omvendte påstanden er FALSK. At

n

er et primtall, gir ikke at

2^n-1

er et primtall:

2^{11}-1=2047=23\cdot 89.

11

er primtall,

2047

er ikke. Å blande de to er en dokumentert felle, og moteksempelet

n=11

er det minste — så det er verdt å huske.

Sammensatt tall og primtall — definisjonene du arbeider fra

p>1

Mersenne-tall og den omvendte påstanden

M_p=2^p-1,\qquad p\ \text{primtall}

$p$	$2^p-1$	primtall?
$2$	$3$	ja
$3$	$7$	ja
$5$	$31$	ja
$7$	$127$	ja
$11$	$2047$	nei $=23\cdot 89$
$13$	$8191$	ja

✏️Arketype 2 med tall: faktoriser to i tolvte minus én

a) Vis at

2^{12}-1

er sammensatt, og gi tre ulike ekte divisorer ved å bruke arketype 2 på tre ulike oppdelinger av

12

.
b) Er

2^{13}-1

sammensatt? Hva sier arketype 2 om det?

a) Tre oppdelinger av $12$ , tre faktorer.

Vi har $2^{12}-1=4096-1=4095$ .

Ved den geometriske faktoriseringen er $2^d-1$ en divisor i $2^{12}-1$ for hver divisor $d$ i $12$ . Divisorene av $12$ er $1,2,3,4,6,12$ , og de gir:

$d$	$2^d-1$	deler $4095$ ?
$2$	$3$	$4095=3\cdot 1365$ ✓
$3$	$7$	$4095=7\cdot 585$ ✓
$4$	$15$	$4095=15\cdot 273$ ✓
$6$	$63$	$4095=63\cdot 65$ ✓

Tre ekte divisorer er derfor

3

7

63

— eller

15

, om du vil. Alle er

>1

<4095

, så

2^{12}-1

er sammensatt.

\blacksquare

Argumentet skrevet ut for én av dem, slik det skal føres: sett

12=3\cdot 4

, altså

a=3

b=4

. Da er

2^{12}-1=\bigl(2^3\bigr)^4-1=\bigl(2^3-1\bigr)\bigl(2^{9}+2^{6}+2^{3}+1\bigr)=7\cdot(512+64+8+1)=7\cdot 585.

Begge faktorer er

>1

, så tallet er sammensatt.
Kontroll:

7\cdot 585=4095

✓. Og den fulle faktoriseringen er

4095=3^2\cdot 5\cdot 7\cdot 13

— som du kan finne ved prøvedivisjon (kap. 1.1), men som oppgaven ikke ba om.

b) Hva arketypen sier — og ikke sier.

$13$ er et primtall, så $13$ er ikke sammensatt, og arketype 2 sier ingenting om $2^{13}-1$ . Arketypen har hypotesen « $n$ sammensatt», og den er ikke oppfylt.
Å slutte «altså er $2^{13}-1$ et primtall» ville være å bruke den omvendte påstanden, som er falsk ( $n=11$ gir $2047=23\cdot 89$ ).
For å svare må vi faktisk undersøke tallet:

$2^{13}-1=8192-1=8191.$

Er $8191$ et primtall? Vi prøvedividerer med primtall opp til $\sqrt{8191}\approx 90{,}5$ : $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89$ . Ingen av dem deler $8191$ , så $8191$ er et primtall.

(En snarvei som halverer arbeidet: en primdivisor $q$ i $2^p-1$ med $p$ primtall må oppfylle $q\equiv 1\pmod{2p}$ — altså $q\equiv 1\pmod{26}$ her, som bare gir kandidatene $53$ og $79$ under $90$ . Det følger av at ordenen til $2$ modulo $q$ er $p$ , og at ordenen deler $q-1$ (kap. 5.1). Snarveien er ikke pensum, men den er et fint eksempel på at Del 5 og Del 6 er samme apparat.)

Sluttsvar: a) $2^{12}-1=4095$ er sammensatt, med ekte divisorer $3$ , $7$ og $63$ ; b) arketypen sier ingenting siden $13$ er primtall, og $2^{13}-1=8191$ er faktisk et primtall.

Om føringen — det som skiller et fullt svar fra et halvt i b): å si hvorfor arketypen ikke gjelder, og å avvise den omvendte påstanden eksplisitt. En besvarelse som svarer «nei, $13$ er primtall så $2^{13}-1$ er primtall» har brukt et argument som er ugyldig, og som tilfeldigvis ga riktig svar denne gangen.

📝Oppgave 3

a) Vis at

2^{21}-1

er sammensatt, og gi to ulike ekte divisorer.
b) Vis den generelle påstanden: er

d\mid n

, så deler

2^d-1

tallet

2^n-1

📝Oppgave 4

Vis at hvis $2^n+1$ er et primtall (med $n\ge 1$ ), så må $n$ være en toerpotens.

(Krevende — grepet er beslektet med arketype 2, men faktoriseringen er en annen.)

Løkke 3: Arketype 3 — primtallet deler binomialkoeffisienten

~11 minutter.

Den korteste av de fem, og den som oftest står som del a i en todelt oppgave.

— naturlig pausepunkt —

📜Arketype 3: primtallet deler binomialkoeffisienten

p

være et primtall og

1\le k\le p-1

. Da er

p\ \Big|\ \binom pk.

Bevis. Per definisjon er
$\binom pk=\frac{p!}{k!\,(p-k)!},$
og siden binomialkoeffisienten er et helt tall, kan vi gange opp:
$k!\,(p-k)!\cdot\binom pk=p!.$

Høyresiden $p!=1\cdot 2\cdots p$ er delelig med $p$ , så
$p\ \Big|\ k!\,(p-k)!\cdot\binom pk.$

Ved Euklids lemma (kap. 1.1), anvendt gjentatte ganger på produktet, deler $p$ minst én av faktorene. Vi utelukker de to første:

- $p\nmid k!$ : fordi $1\le k\le p-1$ , er alle faktorene i $k!=1\cdot 2\cdots k$ strengt mindre enn $p$ . Et primtall deler ikke et produkt av tall som alle er mindre enn det selv (igjen Euklids lemma: da måtte $p$ delt en av dem, og et positivt tall under $p$ kan ikke være delelig med $p$ ).
- $p\nmid (p-k)!$ : samme argument, siden $1\le p-k\le p-1$ .

Altså må $p$ dele den siste faktoren:
$p\ \Big|\ \binom pk.\qquad\blacksquare$

Hvor betingelsen $1\le k\le p-1$ brukes: i begge utelukkelsene. For $k=0$ eller $k=p$ er $\binom pk=1$ , som ikke er delelig med $p$ — så betingelsen er nødvendig, og randtilfellene er nettopp de to som faller utenfor.

Kontroll med tall.

$p$	$k$	$\binom pk$	delelig med $p$ ?
$5$	$2$	$10$	$10=5\cdot 2$ ✓
$7$	$3$	$35$	$35=7\cdot 5$ ✓
$7$	$2$	$21$	$21=7\cdot 3$ ✓
$11$	$5$	$462$	$462=11\cdot 42$ ✓
$5$	$0$	$1$	nei — utenfor betingelsen

⚠ Kravet om at $p$ er et primtall er nødvendig. For

n=4

k=2

\binom 42=6

, og

4\nmid 6

. Beviset bryter nøyaktig der Euklids lemma brukes — det gjelder bare for primtall.

Arketype 3 og hva den brukes til

p

✏️Todelt oppgave: lemmaet i a, anvendelsen i b

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

(a+b)^p\equiv a^p+b^p\pmod p

for alle hele tall

a,b

.
c) Bruk b) til å vise ved induksjon at

a^p\equiv a\pmod p

for alle hele tall

a\ge 1

a) Per definisjon er

\binom pk=\dfrac{p!}{k!(p-k)!}

, og siden binomialkoeffisienten er et helt tall, gir omskriving

k!\,(p-k)!\cdot\binom pk=p!.

Høyresiden er delelig med $p$ (den har $p$ som faktor), så $p$ deler venstresiden.

Ved Euklids lemma (kap. 1.1) deler $p$ minst én av faktorene på venstresiden. Vi utelukker to av dem:

- $k!=1\cdot 2\cdots k$ har alle faktorer $\le k\le p-1<p$ , så $p\nmid k!$ .
- $(p-k)!$ har alle faktorer $\le p-k\le p-1<p$ , så $p\nmid (p-k)!$ .

Altså må $p\mid\binom pk$ . $\blacksquare$

b) Ved binomialformelen er
$(a+b)^p=\sum_{k=0}^{p}\binom pk a^{p-k}b^{k}=a^p+\underbrace{\sum_{k=1}^{p-1}\binom pk a^{p-k}b^k}_{\text{mellomleddene}}+b^p.$

Etter a) er hver koeffisient $\binom pk$ i mellomsummen delelig med $p$ , siden $1\le k\le p-1$ . Altså er hele mellomsummen delelig med $p$ , og modulo $p$ faller den bort:
$(a+b)^p\equiv a^p+b^p\pmod p.\qquad\blacksquare$

Kontroll med tall. $p=5$ , $a=b=1$ : venstre side $2^5=32\equiv 2\pmod 5$ ; høyre side $1+1=2$ ✓. $p=3$ , $a=2$ , $b=1$ : $27\equiv 0\pmod 3$ og $8+1=9\equiv 0$ ✓.

c) Induksjon på $a$ (kap. 6.2).

La $P(a)$ være påstanden $a^p\equiv a\pmod p$ .

(1) Basissteg ( $a=1$ ). $1^p=1\equiv 1\pmod p$ ✓.

(2) Induksjonshypotese. Anta at det for en $a\ge 1$ gjelder $a^p\equiv a\pmod p$ .

(3) Induksjonssteg. Vi skal vise $(a+1)^p\equiv a+1\pmod p$ .

Etter b) med $b=1$ :
$(a+1)^p\equiv a^p+1^p=a^p+1\pmod p.$

Her bruker vi induksjonshypotesen: $a^p\equiv a$ , så
$(a+1)^p\equiv a+1\pmod p,$
som er $P(a+1)$ .

Ved induksjonsprinsippet holder $a^p\equiv a\pmod p$ for alle hele $a\ge 1$ . $\blacksquare$

Kontroll med tall. $p=5$ : $2^5=32=6\cdot 5+2\equiv 2$ ✓; $3^5=243=48\cdot 5+3\equiv 3$ ✓; $4^5=1024=204\cdot 5+4\equiv 4$ ✓.

Om føringen — hvorfor denne oppgaveformen er verdt å kjenne igjen. Tre delpunkt, der hvert bygger på det forrige. Det betyr:

- Del a er ikke pynt. Den skal brukes i b, og b skal brukes i c. Ser du strukturen, vet du at du har fått veien kartlagt.
- Henvisningene skal skrives: «etter a)», «etter b)». Det viser at du bruker det du har vist, og ikke starter forfra.
- Alle tre induksjonsstegene står i c), med hypotesesetningen på riktig sted.

Den andre veien til c), også fullgod: Fermats lille teorem (kap. 2.2) gir $a^{p-1}\equiv 1$ når $p\nmid a$ ; gang med $a$ og få $a^p\equiv a$ . For $p\mid a$ er begge sider $\equiv 0$ . To tilfeller, begge nevnt — og det er en case-analyse som må være uttømmende. Denne veien er kortere, men den forutsetter Fermat; induksjonsveien forutsetter bare a).

Merk at c) er et av de best belagte eksempeloppgavene i arkivet, og at den nesten alltid kommer som del b eller c i en todelt oppgave med a) som lemma. Kjenner du kjeden a → b → c, kjenner du hele oppgaven.

📝Oppgave 5

a) Regn ut

\binom 7k

for

k=0,1,\dots,7

og kontrollér arketype 3 for

p=7

.
b) Vis at

\binom{4}{2}

ikke er delelig med

4

, og forklar presist hvor beviset for arketype 3 bryter sammen når

p

ikke er et primtall.

Løkke 4: Arketype 4 — uendelig mange primtall av en gitt form

~13 minutter.

Nå den lengste av de fem, og den som følger en fast mal du kan skrive før du vet hvilken form oppgaven spør om.

Euklid-trikset: tallet du konstruerer

N

Målform	Velg $N$	Da er
alle primtall (Euklid)	$N=p_1p_2\cdots p_r+1$	$N$ har en primdivisor utenfor listen
$\equiv 2\pmod 3$	$N=3p_1\cdots p_r-1$	$N\equiv -1\equiv 2\pmod 3$
$\equiv 3\pmod 4$	$N=4p_1\cdots p_r-1$	$N\equiv -1\equiv 3\pmod 4$

📜Arketype 4: uendelig mange primtall kongruent med 2 modulo 3

Det finnes uendelig mange primtall

p

med

p\equiv 2\pmod 3.

Bevis ved motsigelse.

Anta, for å komme til en motsigelse, at det bare finnes endelig mange. Merk at $2$ er ett av dem ( $2\equiv 2\pmod 3$ ), så listen er ikke tom. La den være
$p_1=2,\ p_2,\ \dots,\ p_r.$

Konstruér tallet
$N=3\,p_1p_2\cdots p_r-1.$

Steg 1: $N>1$ . Produktet er minst $2$ , så $N\ge 3\cdot 2-1=5>1$ .

Steg 2: $N\equiv 2\pmod 3$ . Leddet $3p_1\cdots p_r$ er delelig med $3$ , så $N\equiv -1\equiv 2\pmod 3$ .

Steg 3: $N$ er odde. Produktet inneholder $p_1=2$ , så $3p_1\cdots p_r$ er et partall, og $N$ er et partall minus $1$ , altså odde. Spesielt er $2\nmid N$ .

Steg 4: $3\nmid N$ . Fra steg 2 har $N$ rest $2$ modulo $3$ .

Steg 5: en av $N$ s primdivisorer er $\equiv 2\pmod 3$ . Her kommer case-analysen. Faktoriser $N$ i primtall (etter aritmetikkens fundamentalteorem). Hver primdivisor $q$ i $N$ har, ved divisjonsalgoritmen, en rest $q\equiv 0$ , $1$ eller $2\pmod 3$ . Vi behandler alle tre:

- $q\equiv 0\pmod 3$ : da er $3\mid q$ , og siden $q$ er primtall er $q=3$ . Men steg 4 sa $3\nmid N$ . Utelukket.
- $q\equiv 1\pmod 3$ for ALLE primdivisorer: da er $N$ et produkt av tall som alle er $\equiv 1\pmod 3$ , og et slikt produkt er selv $\equiv 1\pmod 3$ . Men steg 2 sa $N\equiv 2$ . Utelukket.
- $q\equiv 2\pmod 3$ for minst én primdivisor: dette er den eneste gjenstående muligheten, og den må derfor inntreffe.

Altså finnes en primdivisor $q$ i $N$ med $q\equiv 2\pmod 3$ .

Steg 6: $q$ er ikke i listen. Var $q=p_i$ for en $i$ , ville $q$ delt både $3p_1\cdots p_r$ og $N$ . Da ville $q$ delt differansen
$3p_1\cdots p_r-N=1,$
altså $q\mid 1$ — umulig, siden $q\ge 2$ .

Motsigelsen. $q$ er et primtall $\equiv 2\pmod 3$ som ikke står i listen $p_1,\dots,p_r$ . Men listen skulle inneholde alle slike primtall. Motsigelse.

Konklusjon. Antakelsen var gal: det finnes uendelig mange primtall $\equiv 2\pmod 3$ . $\blacksquare$

Merk hvor de to kritiske stegene ligger. Steg 5 er case-analysen som gir deg primtallet du trenger, og steg 6 er setningen som viser at det er nytt. Begge glemmes rutinemessig, og begge er egne føringspoeng.

✏️Arketypen med tall: hvordan konstruksjonen ser ut i praksis

Følg beviset for arketype 4 med en konkret, kort «liste»: anta feilaktig at $2$ og $5$ er de eneste primtallene $\equiv 2\pmod 3$ . Konstruér $N$ , faktoriser det, og pek på det nye primtallet.

Den antatte listen:

p_1=2

p_2=5

. (Begge er

\equiv 2\pmod 3

2=0\cdot 3+2

5=1\cdot 3+2

✓.)

Konstruksjonen.
$N=3\cdot 2\cdot 5-1=30-1=29.$

Kontroller de tre kravene:

- $N>1$ : $29>1$ ✓
- $N\equiv 2\pmod 3$ : $29=9\cdot 3+2$ ✓
- $N$ ikke delelig med $2$ eller $5$ : $29$ er odde og ender ikke på $0$ eller $5$ ✓

Faktoriser $N$ . $29$ er et primtall (prøvedivisjon med $2,3,5$ er nok, siden $\sqrt{29}<6$ ).

Det nye primtallet er altså $q=29$ selv, og
$29\equiv 2\pmod 3.$

$29$ står ikke i listen $\{2,5\}$ , så listen var ikke komplett — nøyaktig motsigelsen beviset trenger.

Prøv med den utvidede listen. Legg til $29$ : listen er nå $\{2,5,29\}$ , og
$N=3\cdot 2\cdot 5\cdot 29-1=870-1=869.$

Faktoriser: $869=11\cdot 79$ . Kontroll: $11\cdot 79=869$ ✓.

Restene modulo $3$ : $11=3\cdot 3+2\equiv 2$ , og $79=26\cdot 3+1\equiv 1$ .

Her er case-analysen synlig i praksis: de to primdivisorene har restene $2$ og $1$ . Ikke alle kan være $\equiv 1$ , for da ville produktet vært $\equiv 1$ , mens $869\equiv 2\pmod 3$ (kontroll: $869=289\cdot 3+2$ ✓). Og faktisk er $11\equiv 2$ — det nye primtallet.

*Merk at $11$ er mindre enn $29$ . Konstruksjonen gir deg et nytt primtall av rett form, ikke det neste i rekken. Det er nok for beviset: alt du trenger, er at det ikke er i listen.

Gjenta én gang mer, med listen $\{2,5,11,29\}$ :
$N=3\cdot 2\cdot 5\cdot 11\cdot 29-1=9570-1=9569.$
Faktoriser: $9569=7\cdot 1367$ . Kontroll: $7\cdot 1367=9569$ ✓. Restene: $7\equiv 1\pmod 3$ og $1367=455\cdot 3+2\equiv 2$ . Så $1367$ er den nye — og $1367$ er et primtall (prøvedivisjon opp til $\sqrt{1367}\approx 37$ ).

Hva eksempelet er godt for, og hva det ikke er. Det viser mekanikken: hvordan $N$ velges, hvorfor restene tvinger frem et primtall av rett form, og hvorfor det nye primtallet ikke kan være i listen. Men det er ikke beviset — beviset er argumentet i teoremet over, som gjelder for en vilkårlig endelig liste. Å regne tre runder er en illustrasjon, og illustrasjoner beviser ingenting om uendelig mange tilfeller (kap. 6.1).

Om føringen: skal du bruke et konkret eksempel i en besvarelse, si tydelig at det er en illustrasjon. Skriver du det som om det var beviset, har du levert en allpåstand bekreftet med eksempler — og det gir ikke uttelling.*

📝Oppgave 6

Vis at det finnes uendelig mange primtall $p$ med $p\equiv 3\pmod 4$ .

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

Løkke 5: Arketype 5 — primtallstripler via case-analyse modulo 3

~12 minutter.

Den siste arketypen, og den korteste å føre når du har sett grepet én gang.

— naturlig pausepunkt —

Restene til et primtall over 3

p>3

📜Arketype 5: det eneste primtallet der p, p+8 og p+16 alle er primtall

Det eneste primtallet

p

der både

p+8

p+16

også er primtall, er

p=3.

Bevis.

Først: $p=3$ virker. $3$ , $3+8=11$ og $3+16=19$ er alle primtall ✓.

Så: ingen andre virker. Vi viser at antakelsen « $p$ , $p+8$ , $p+16$ alle primtall og $p\ne 3$ » fører til en motsigelse.

Case-analyse modulo $3$ . Ved divisjonsalgoritmen er $p\equiv 0$ , $1$ eller $2\pmod 3$ . Vi behandler alle tre:

Tilfelle $p\equiv 0\pmod 3$ . Da er $3\mid p$ , og siden $p$ er et primtall, er $p=3$ . Det er tilfellet vi alt har behandlet, og det er utelukket av antakelsen $p\ne 3$ .

Tilfelle $p\equiv 1\pmod 3$ . Da er
$p+8\equiv 1+8=9\equiv 0\pmod 3,$
så $3\mid p+8$ . Men $p+8\ge 2+8=10>3$ , så $p+8$ har en ekte divisor $3$ og er dermed sammensatt. Det strider mot at $p+8$ skulle være et primtall. Utelukket.

Tilfelle $p\equiv 2\pmod 3$ . Da er
$p+16\equiv 2+16=18\equiv 0\pmod 3,$
så $3\mid p+16$ . Og $p+16\ge 18>3$ , så $p+16$ er sammensatt. Det strider mot antakelsen. Utelukket.

Alle tre tilfellene er dekket, og de to som ikke er $p=3$ , er utelukket. Altså er $p=3$ det eneste primtallet med egenskapen. $\blacksquare$

Kontroll ved å prøve. Vi tester alle primtall opp til $50$ :

$p$	$p+8$	$p+16$	alle primtall?
$2$	$10$	$18$	nei ( $10=2\cdot 5$ )
$3$	$11$	$19$	ja
$5$	$13$	$21$	nei ( $21=3\cdot 7$ )
$7$	$15$	$23$	nei ( $15=3\cdot 5$ )
$11$	$19$	$27$	nei ( $27=3^3$ )
$13$	$21$	$29$	nei ( $21=3\cdot 7$ )
$17$	$25$	$33$	nei (begge sammensatte)
$19$	$27$	$35$	nei
$23$	$31$	$39$	nei ( $39=3\cdot 13$ )

Mønsteret er tydelig: for

p\equiv 1\pmod 3

(

p=7,13,19

) faller

p+8

; for

p\equiv 2\pmod 3

(

p=5,11,17,23

) faller

p+16

. Nøyaktig som case-analysen forutsier.
Hvorfor modulo $3$ er det riktige valget: differansene

8

16

\equiv 2

\equiv 1\pmod 3

, altså ulike og ikke-null. Da løper

p

p+8

p+16

gjennom alle tre restklassene modulo

3

, og ett av dem må være delelig med

3

✏️Eksamensnivå: samme grep, andre tall — p og p i annen pluss tjue

a) Vis at det eneste primtallet

p

der både

p+4

p+8

også er primtall, er

p=3

.
b) Vis at det eneste primtallet

p

der

p^2+20

også er et primtall, er

p=3

a) Arketype 5, med differanse $4$ .

Først: $p=3$ virker. $3$ , $7$ og $11$ er alle primtall ✓.

Case-analyse modulo $3$ . Merk først at differansen er $4\equiv 1\pmod 3$ , som ikke er $0$ — så arketypen er anvendelig. Ved divisjonsalgoritmen er $p\equiv 0,1$ eller $2\pmod 3$ , og vi behandler alle tre:

Tilfelle $p\equiv 0$ : da er $3\mid p$ , og siden $p$ er primtall, $p=3$ . Behandlet over.

Tilfelle $p\equiv 1$ : da er
$p+8\equiv 1+8=9\equiv 0\pmod 3.$
Så $3\mid p+8$ , og $p+8\ge 10>3$ , altså er $p+8$ sammensatt. Utelukket.

Tilfelle $p\equiv 2$ : da er
$p+4\equiv 2+4=6\equiv 0\pmod 3.$
Så $3\mid p+4$ , og $p+4\ge 6>3$ , altså er $p+4$ sammensatt. Utelukket.

Alle tre tilfeller dekket. Altså er $p=3$ det eneste. $\blacksquare$

Kontroll: $p=5$ gir $9=3^2$ (faller) ✓; $p=7$ gir $11$ og $15=3\cdot 5$ (faller) ✓; $p=11$ gir $15$ (faller) ✓; $p=13$ gir $17$ og $21=3\cdot 7$ (faller) ✓.

b) Samme grep, men nå på et kvadrat.

Først: $p=3$ virker. $p^2+20=9+20=29$ , som er et primtall ✓.

Case-analyse modulo $3$ , med den ene nye ingrediensen: kvadrattall har rest $0$ eller $1$ modulo $3$ (kap. 6.1).

Tilfelle $3\mid p$ : siden $p$ er primtall, er $p=3$ . Behandlet over.

Tilfelle $3\nmid p$ : da er $p\equiv 1$ eller $2\pmod 3$ , og i begge tilfeller er
$p^2\equiv 1\pmod 3$
(fordi $1^2=1$ og $2^2=4\equiv 1$ ). Altså
$p^2+20\equiv 1+20=21\equiv 0\pmod 3,$
så $3\mid p^2+20$ .

Og $p^2+20\ge 2^2+20=24>3$ , så $p^2+20$ har $3$ som ekte divisor og er sammensatt. Utelukket.

Begge tilfeller er dekket. Altså er $p=3$ det eneste primtallet der $p^2+20$ også er et primtall. $\blacksquare$

Kontroll med tall.

$p$	$p^2+20$	primtall?
$2$	$24$	nei ( $24=3\cdot 8$ )
$3$	$29$	ja
$5$	$45$	nei ( $45=3\cdot 15$ )
$7$	$69$	nei ( $69=3\cdot 23$ )
$11$	$141$	nei ( $141=3\cdot 47$ )
$13$	$189$	nei ( $189=3\cdot 63$ )

Alle de sammensatte er delelige med

3

— nøyaktig som case-analysen forutsier.
Om føringen — de fire tingene som gir uttelling i denne arketypen:
1. At $p=3$ virker, er sjekket. Oppgaven sier «det eneste», og det innebærer at det er ett. Å bare utelukke de andre er halve svaret.
2. Case-analysen er uttømmende, og tilfellet

3\mid p

er utelukket med et argument («siden

p

er primtall, er

p=3

») — ikke bare hoppet over.
3. Størrelsesargumentet står:

3\mid p+8

gjør

p+8

sammensatt bare fordi

p+8>3

. Uten den linjen er argumentet ufullstendig —

3

er selv delelig med

3

uten å være sammensatt.
4. Kvadratrest-observasjonen i b) er begrunnet, ikke antatt:

1^2\equiv 1

2^2\equiv 1

, altså

p^2\equiv 1

i begge mulige tilfeller.
Punkt 3 er det som oftest mangler, og det er verdt en ekstra tanke: «delelig med $3$ » og «sammensatt» er ikke det samme. Tallet $3$ er delelig med $3$ og er et primtall. Argumentet trenger derfor både delelighet og at tallet er større enn $3$ .

📝Oppgave 7

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

Skriv størrelsesargumentet eksplisitt.

📝Oppgave 8

Avgjør om påstanden er sann: «Det eneste primtallet $p$ der både $p+6$ og $p+12$ også er primtall, er $p=3$ .»

Begrunn svaret, og forklar hvorfor arketype 5 ikke kan brukes her.

📝Oppgave 9

Vis at det eneste primtallet $p$ der $p$ , $p+2$ og $p+6$ og $p+8$ alle er primtall, ikke finnes for $p>5$ — det vil si: for $p>5$ kan ikke alle fire være primtall.

Hint om valg av modulus: fire tall, og differansene er $2$ , $6$ , $8$ .

(Krevende — men case-analysen er bare fem rader.)

📝Oppgave 10

Todelt oppgave.

a) Vis at $30\mid n^5-n$ for alle heltall $n$ .
b) Bruk arketype 1 til å begrunne oppsplittingen du gjorde i a), og forklar hvorfor det ikke ville holdt å splitte $30$ som $6\cdot 5$ uten videre kontroll.

Typiske feil

De fem feilene under er dokumentert i arkivets løsningsforslag som noe fasitene fører eksplisitt imot. Alle er føringsfeil eller manglende betingelser — ikke regnefeil.

- Ufullstendig case-analyse. Den best belagte enkeltfeilen i bevisdelen. I arketype 5 er det tilfellet $p\equiv 0\pmod 3$ som glemmes, fordi det «bare» gir $p=3$ — men det tilfellet er svaret, og det skal utelukkes med et argument. Tell radene: en case-analyse modulo $m$ har $m$ rader.

- Arketype 1 brukt uten $\gcd$ -sjekken. $4\mid 12$ og $6\mid 12$ , men $24\nmid 12$ . Betingelsen $\gcd(m,n)=1$ er nødvendig, og linjen «og $\gcd(m,n)=1$ » er egne poeng. Ved oppsplitting av et sammensatt tall: sjekk at faktorene er parvis relativt primiske.

- Teoremet ikke navngitt. Euklids lemma og aritmetikkens fundamentalteorem bærer argumentene i denne sjangeren, og navnene skal stå: «ved Euklids lemma deler $p$ en av faktorene». Instruksen på hvert sett er at alle svar skal begrunnes, og i et bevis er navnet på resultatet en del av begrunnelsen.

- Størrelsesargumentet mangler i arketype 5. « $3\mid p+8$ » gir ikke at $p+8$ er sammensatt — tallet $3$ er selv delelig med $3$ og er et primtall. Du trenger både delelighet og at tallet er større enn $3$ . Én linje.

- Motsigelsesbeviset avsluttes ikke med en klar umulighet. I arketype 4 er det «ikke i listen»-setningen som er motsigelsen: «var $q=p_i$ , ville $q\mid 1$ — umulig». Uten den renner beviset ut, og det er dokumentert som en typisk mangel.

Og fire feil som er spesifikke for de enkelte arketypene:

- Arketype 2: å glemme å vise at begge faktorene er ekte. En faktorisering der én faktor kan være $1$ , viser ikke at tallet er sammensatt.
- Arketype 2: å tro på den omvendte påstanden. $n$ primtall gir ikke at $2^n-1$ er primtall — $2^{11}-1=2047=23\cdot 89$ .
- Arketype 3: å glemme betingelsen $1\le k\le p-1$ . For $k=0$ og $k=p$ er koeffisienten $1$ , og påstanden er falsk.
- Arketype 5: å bruke den når $3$ deler differansen. $p,p+6,p+12$ har løsningen $p=5$ . Sjekk differansen først.

Begrepsbank

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

Under kode D er banken eksamensverktøyet, ikke pynt. Arketypene er former, og former pugges ved å brukes: skriv arketype 1 og arketype 5 ut på nytt med nye tall, med lukket bok. Det er mer verdt enn tre gjennomlesninger.

Kort: de fem arketypene på én side

\gcd(m,n)=1

#	Påstanden	Førstegrepet
1	$\gcd(m,n)=1$ , $m\mid k$ , $n\mid k\Rightarrow mn\mid k$	Bézout: $mx+ny=1$ , gang med $k$
2	$2^n-1$ sammensatt når $n$ sammensatt	$n=ab$ , faktoriser med $x^b-1$ , $x=2^a$
3	$p\mid\binom pk$ for $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$ , motsigelse
5	$p,p+a,p+2a$ alle primtall $\Rightarrow p=3$	case-analyse modulo $3$ (krever $3\nmid a$ )

Kort: arketype 1 i tre veier

\gcd(m,n)=1,\ m\mid k,\ n\mid k\ \Longrightarrow\ mn\mid k

Kort: den geometriske faktoriseringen

x^d-1=(x-1)\bigl(x^{d-1}+x^{d-2}+\dots+x+1\bigr)

Kort: to i n-te minus én

n

Kort: primtallet deler binomialkoeffisienten

p\ \text{primtall},\ 1\le k\le p-1\ \Longrightarrow\ p\ \Big|\ \binom pk

Kort: uendelig mange primtall av en gitt form

p_1,\dots,p_r

Form	$N$
alle primtall	$p_1\cdots p_r+1$
$\equiv 2\pmod 3$	$3p_1\cdots p_r-1$
$\equiv 3\pmod 4$	$4p_1\cdots p_r-1$

Kort: primtallstripler modulo 3

p

Kort: todelte bevisoppgaver

p\mid\binom pk

Kort: å splitte et sammensatt tall

d\mid k

$d$	splitt	$\gcd$ -kontroll
$6$	$2\cdot 3$	$\gcd(2,3)=1$ ✓
$12$	$4\cdot 3$	$\gcd(4,3)=1$ ✓
$24$	$8\cdot 3$	$\gcd(8,3)=1$ ✓
$30$	$2\cdot 3\cdot 5$	alle par $=1$ ✓

$d$	splitt	hvorfor
$12$	$6\cdot 2$	$\gcd(6,2)=2$
$24$	$6\cdot 4$	$\gcd(6,4)=2$ ; $k=12$ er moteksempel

Kort: hvilken modulus velger du

d

Kort: når case-analysen etterlater ett åpent tilfelle

m

Kort: kontrollene i sjanger I

m

Kort: teoremnavnene i sjanger I

n=qm+r

Navn	Hva det sier	Hvor
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
det kinesiske restteoremet	system av kongruenser med primiske moduler	kap. 2.4

Kort: tidsbudsjettet for en I-oppgave

Eksamen er 4 timer på rundt ti likt vektede delpunkt, altså ~24 minutter per delpunkt . Arbeid Tid Lese oppgaven og kjenne igjen arketypen ~2 min Skrive antakelsene og velge modulus/vei ~2 min Argumentet (case-analyse, faktorisering, Bézout) ~7-10 min Betingelses- og størrelsessjekker ~2 min Konklusjonssetning ~1 min Kontroll med to-tre tallverdier ~2 min Til sammen 16-19 minutter for et rent bevisdelpunkt. Er oppgaven todelt, regn med hele budsjettet på ~24 minutter for begge — del a er typisk kortere enn del b. Hvor tiden går galt: i å velge modulus i en case-analyse. Regelen som sparer mest: velg den modulusen som dreper flest ledd, eller den som differansene i oppgaven ikke er delelige med. Hva du IKKE skal bruke tid på: å faktorisere store tall du ikke trenger. I arketype 2 holder det å finne én ekte faktor; hele faktoriseringen er ikke etterspurt. Realistisk forventning: når du kjenner arketypen, er dette blant de raskeste delpunktene i settet — fem til tolv linjer. Og selv om argumentet ikke går helt i lås, gir riktig arketype med riktig førstegrep og en påbegynt case-analyse reell uttelling.

Arbeid	Tid
Lese oppgaven og kjenne igjen arketypen	~2 min
Skrive antakelsene og velge modulus/vei	~2 min
Argumentet (case-analyse, faktorisering, Bézout)	~7–10 min
Betingelses- og størrelsessjekker	~2 min
Konklusjonssetning	~1 min
Kontroll med to–tre tallverdier	~2 min

Kort: selvdiagnose for delelighetsbevis

\gcd(m,n)=1

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.