5.3 Tallteoretiske funksjoner: τ, σ og multiplikativitet

Antall divisorer τ(n)=∏(kᵢ+1) og divisorsummen σ(n) via primtallsfaktorisering og multiplikativitet, pluss optimeringsoppgaven «finn minste n med gitt τ(n)» — fordel eksponentene på de minste primtallene.

55 min

8 oppgaver

Tallteoretiske funksjonermultiplikativitet

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

1.1Delelighet, primtall og aritmetikkens fundamentalteorem

Brukes videre i

5.4Drill: orden, primitive røtter og tallteoretiske funksjoner

Tallteoretiske funksjoner er sjanger H, som forekommer i 7 av 15 sett — 47 %. Sjangerbokstavene er bokas forkortelser for oppgavetypene, forklart i kap. 0.1; H dekker

\tau

\sigma

\phi

og multiplikativitet.

Dette er den billigste sjangeren i hele faget. Apparatet er to formler, og oppgavene er ren regning på en faktorisering du finner i hodet. En trent student tar delpunktet på fem minutter.

Hva oppgaven spør om	Verktøy
«Hvor mange divisorer har $n$ ?»	$\tau(n)=\prod(k_i+1)$
«Finn divisorsummen $\sigma(n)$ »	$\displaystyle \sigma(n)=\prod\frac{p_i^{k_i+1}-1}{p_i-1}$
«Finn det minste $n$ med $\tau(n)=$ gitt verdi»	eksponentfordeling (løkke 4)
«Vis at $\tau(n)$ er odde hvis og bare hvis $n$ er et kvadrattall»	bevisoppgave, tre linjer

Optimeringsvarianten — «finn minste

n

med nøyaktig

16

divisorer» — er den mest karakteristiske. Den ser ut som en søkeoppgave, men den er ren faktorisering av måltallet, og oppskriften er kort.
Prioritet: kunne. Sjangeren er lavere frekvent enn de fem søylene, men forholdet mellom innsats og uttelling er svært godt: to formler dekker hele temaet.
Merk sammenhengen med resten av Del 5:

\phi

(kap. 2.1) er også en multiplikativ funksjon, og du bruker den samme faktoriseringsteknikken. Har du

\phi

i fingrene, er

\tau

\sigma

nesten gratis.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en enkel kalkulator. Den kan gange og dele, men den kan ikke faktorisere

n

for deg, og den kjenner ingen

\tau

- eller

\sigma

-formler.

Må sitte utenat:

- $\tau(n)=\prod(k_i+1)$ for $n=\prod p_i^{k_i}$ — antall divisorer
- at $\tau$ , $\sigma$ og $\phi$ er multiplikative: $f(mn)=f(m)f(n)$ når $\gcd(m,n)=1$
- minste- $n$ -oppskriften: faktoriser måltallet, trekk $1$ fra hver faktor, og gi de største eksponentene til de minste primtallene
- at $\tau(n)$ er odde $\iff$ $n$ er et kvadrattall

Utledes på stedet:

- $\sigma$ -formelen ut av den geometriske summen:
$\sigma(p^k)=1+p+p^2+\dots+p^k=\frac{p^{k+1}-1}{p-1}.$
To linjer, og utledningen står i løkke 2. Dette er den ene formelen i kapitlet du ikke behøver pugge — den geometriske summen kjenner du fra videregående.
- $\tau(n)$ odde $\iff$ kvadrattall — tre linjer: alle $k_i+1$ må være odde, altså alle $k_i$ partall.
- $\sigma(n)/n=\sum_{d\mid n}1/d$ — én linje: $d\mapsto n/d$ er en bijeksjon på divisorene.
- $\sigma(n)=n+1\iff n$ er primtall — to linjer.

Selvtest, to minutter: dekk til boka, faktoriser $360$ , og skriv ned $\tau(360)$ og $\sigma(360)$ med utregning. Får du $24$ og $1\,170$ , sitter kapitlets kjerne. Nøler du på om det er $k_i+1$ eller $k_i$ i $\tau$ -formelen, er det den ene tingen å drille — $\tau(n)=\prod k_i$ er en dokumentert felle.

Forkunnskaper

Fra boka: kap. 1.1 (primtallsfaktorisering, divisorer, aritmetikkens fundamentalteorem) er grunnlaget, og kap. 2.1 (multiplikativitet for $\phi$ ) gir mønsteret vi gjenbruker.

Sist du var her. De to resultatene du bruker i hver oppgave:

Aritmetikkens fundamentalteorem. Hvert tall $n>1$ har en entydig primtallsfaktorisering
$n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}.$
Alt i dette kapitlet leses av fra den.

Multiplikativitet. En funksjon $f$ er multiplikativ når
$f(mn)=f(m)f(n)\qquad\text{for }\gcd(m,n)=1.$
Du kjenner det fra $\phi$ : $\phi(20)=\phi(4)\phi(5)=2\cdot 4=8$ .

Fra videregående er den geometriske summen nyttig: $\displaystyle 1+p+\dots+p^k=\frac{p^{k+1}-1}{p-1}$ . Den utleder vi likevel på stedet i løkke 2.

Hvor mange rektangler?

Du har $36$ like fliser og skal legge dem i et rektangel. Hvor mange former kan du velge?
$1\times 36,\quad 2\times 18,\quad 3\times 12,\quad 4\times 9,\quad 6\times 6,\quad 9\times 4,\quad\dots$
Antall muligheter er antall divisorer i $36$ — og det er $9$ : tallene $1,2,3,4,6,9,12,18,36$ .

Legg merke til at $9$ er et oddetall, mens divisorene til de fleste tall kommer i par. Grunnen er at $36=6^2$ er et kvadrattall, så divisoren $6$ er sin egen partner. Det er et lite mønster med en helt presis forklaring, og vi beviser det i løkke 5.

Dette kapitlet handler om to funksjoner av faktoriseringen:

$\tau(n)=\text{antall divisorer},\qquad \sigma(n)=\text{summen av divisorene}.$

For $n=36$ er $\tau(36)=9$ og $\sigma(36)=1+2+3+4+6+9+12+18+36=91$ .

Det bemerkelsesverdige er at ingen av dem krever at du lister divisorene. Begge leses av rett fra primtallsfaktoriseringen med en formel — og for $\tau$ er formelen så enkel at du kan regne $\tau$ av et sekssifret tall i hodet, forutsatt at du kan faktorisere det.

Hvorfor det virker: en divisor av $n=p^{k_1}q^{k_2}$ er ikke noe annet enn et valg av hvor mange $p$ -er og hvor mange $q$ -er du tar med. Antall valg er $(k_1+1)(k_2+1)$ , og der er $\tau$ -formelen. Samme observasjon, ganget ut i stedet for telt, gir $\sigma$ .

Den tredje oppgavetypen går baklengs: «finn det minste tallet med nøyaktig $18$ divisorer». Da faktoriserer du måltallet i stedet, og fordeler eksponentene smart. Det er løkke 4.

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

Løkke 1: Antall divisorer

~11 minutter.

Vi begynner med $\tau$ , som er den enkleste av de to — og den som oftest står i oppgaveteksten.

Antall divisorer τ(n)

\tau(n)

Hvordan divisorene ser ut

n=p_1^{k_1}\cdots p_m^{k_m}

$3^0$	$3^1$	$3^2$
$2^0$	$1$	$3$	$9$
$2^1$	$2$	$6$	$18$
$2^2$	$4$	$12$	$36$

✏️τ(360) og hele divisorstrukturen

Finn $\tau(360)$ , og forklar hva tallet betyr.

Steg 1: faktoriser. Vi deler ut småprimtall:

360=36\cdot 10=(2^2\cdot 3^2)(2\cdot 5)=2^3\cdot 3^2\cdot 5.

Kontroll av faktoriseringen: $2^3\cdot 3^2\cdot 5=8\cdot 9\cdot 5=360$ ✓.

Steg 2: bruk formelen. Eksponentene er $k_1=3$ , $k_2=2$ , $k_3=1$ , så
$\tau(360)=(3+1)(2+1)(1+1)=4\cdot 3\cdot 2=24.$

Steg 3: konkludér i ord. Tallet $360$ har $24$ positive divisorer.

Hva tallet betyr, konkret: en divisor velges ved å bestemme hvor mange $2$ -ere (fire valg: $0,1,2,3$ ), hvor mange $3$ -ere (tre valg) og hvor mange $5$ -ere (to valg) du tar med. Til sammen $4\cdot 3\cdot 2=24$ kombinasjoner.

Kontroll ved å liste noen av dem: $1,2,3,4,5,6,8,9,10,12,15,18,20,24,30,36,40,45,60,72,90,120,180,360$ — det er $24$ tall ✓. (Legg merke til at de kommer i par som ganger til $360$ : $1\cdot 360$ , $2\cdot 180$ , $3\cdot 120$ , og så videre — tolv par.)

Sluttsvar: $\tau(360)=24$ .

Om føringen: faktoriseringen skal stå i besvarelsen. Instruksen på hvert eksamenssett er at alle svar skal begrunnes, og i denne sjangeren er faktoriseringen hele begrunnelsen — formelen er ubrukelig uten den. « $\tau(360)=24$ » alene er et sluttall uten metode.

Merk også at $360$ er et usedvanlig divisorrikt tall for sin størrelse: $24$ divisorer. Det er ingen tilfeldighet at det er antall grader i en sirkel og antall dager i mange gamle kalendere — tall med mange divisorer er praktiske å dele opp.

📝Oppgave 1

Finn $\tau(540)$ og $\tau(1024)$ . Skriv faktoriseringen i begge tilfeller.

Løkke 2: Divisorsummen

~13 minutter.

Nå $\sigma$ . Formelen ser tyngre ut enn $\tau$ -formelen, men den utledes på stedet i to linjer med den geometriske summen — så du behøver ikke pugge den.

— naturlig pausepunkt —

📜Divisorsummen σ(n)

\sigma(n)

er summen av alle positive divisorer i

n

. For

n=\prod_i p_i^{k_i}

$\sigma(n)=\prod_i\frac{p_i^{k_i+1}-1}{p_i-1}.$

Bevis, i to steg.

Steg 1 — primtallspotenser. Divisorene i $p^k$ er nøyaktig $1,p,p^2,\dots,p^k$ , så
$\sigma(p^k)=1+p+p^2+\dots+p^k.$
Dette er en geometrisk sum med kvotient $p$ og $k+1$ ledd. Utledningen av summeformelen, for ordens skyld: kall summen $S$ . Da er
$pS=p+p^2+\dots+p^{k+1},$
og trekker vi $S$ fra $pS$ , faller alle mellomledd bort:
$pS-S=p^{k+1}-1\ \Longrightarrow\ S(p-1)=p^{k+1}-1\ \Longrightarrow\ S=\frac{p^{k+1}-1}{p-1}.$

Steg 2 — generelt $n$ . Hver divisor av $n$ er et produkt $\prod p_i^{e_i}$ med $0\le e_i\le k_i$ , og hvert slikt produkt forekommer nøyaktig én gang. Ganger vi ut
$\left(1+p_1+\dots+p_1^{k_1}\right)\cdots\left(1+p_m+\dots+p_m^{k_m}\right),$
får vi derfor summen av alle divisorene, hver én gang. Altså er $\sigma(n)=\prod_i\sigma(p_i^{k_i})$ , og steg 1 gir formelen. $\blacksquare$

Formelen utledes på stedet — to linjer, under et minutt. Det du må kunne, er at $\sigma(p^k)$ er den geometriske summen $1+p+\dots+p^k$ ; resten er videregåendealgebra.

Praktisk regnetips: for små eksponenter er det ofte raskest å summere direkte i stedet for å bruke brøken. $\sigma(2^3)=1+2+4+8=15$ går fortere enn $\displaystyle \frac{2^4-1}{2-1}=15$ , og det er mindre å regne feil på. Bruk brøken når eksponenten er stor.

Intuisjonen bak steg 2 er verdt å ha: å gange ut de $m$ parentesene er nøyaktig å velge ett ledd fra hver — altså å velge en divisor. «Gang ut parentesene» og «list divisorene» er samme operasjon.

σ i praksis — tre regnegrep

\sigma(n)

$p^k$	$\sigma(p^k)$
$2$ , $4$ , $8$ , $16$ , $32$	$3$ , $7$ , $15$ , $31$ , $63$
$3$ , $9$ , $27$	$4$ , $13$ , $40$
$5$ , $25$ , $125$	$6$ , $31$ , $156$
$7$ , $49$	$8$ , $57$

✏️σ(360) og σ(1000)

Regn ut $\sigma(360)$ og $\sigma(1000)$ .

Første: $\sigma(360)$ .

Faktoriseringen er $360=2^3\cdot 3^2\cdot 5$ (fra eksempel 1).

Regn faktor for faktor, med direkte summering:
$\sigma(2^3)=1+2+4+8=15,$
$\sigma(3^2)=1+3+9=13,$
$\sigma(5)=1+5=6.$

Sett sammen:
$\sigma(360)=15\cdot 13\cdot 6.$
Steg for steg: $15\cdot 13=195$ , og $195\cdot 6=1\,170$ .

$\sigma(360)=1\,170.$

Kontroll med brøkformelen på den første faktoren: $\displaystyle \frac{2^4-1}{2-1}=\frac{15}{1}=15$ ✓.

Grov rimelighetskontroll: $\sigma(360)$ skal være større enn $360$ og mindre enn $24\cdot 360=8\,640$ (siden det er $24$ divisorer, alle $\le 360$ ). Og $1\,170$ ligger godt innenfor ✓.

Andre: $\sigma(1000)$ .

Faktoriser: $1000=10^3=(2\cdot 5)^3=2^3\cdot 5^3$ .

Regn faktor for faktor:
$\sigma(2^3)=1+2+4+8=15,$
$\sigma(5^3)=1+5+25+125=156.$

Sett sammen:
$\sigma(1000)=15\cdot 156=2\,340.$

(Mellomregning: $15\cdot 156=15\cdot 150+15\cdot 6=2\,250+90=2\,340$ .)

Kontroll av $\sigma(5^3)$ med brøkformelen: $\displaystyle \frac{5^4-1}{5-1}=\frac{625-1}{4}=\frac{624}{4}=156$ ✓ — to uavhengige veier til samme tall.

Sluttsvar: $\sigma(360)=1\,170$ og $\sigma(1000)=2\,340$ .

Merk at $\tau(1000)=(3+1)(3+1)=16$ . De to funksjonene leses av fra samme faktorisering — har du faktorisert én gang, får du begge nesten gratis. På eksamen spør oppgaven ofte om begge i samme delpunkt, nettopp derfor.

📝Oppgave 2

Finn $\tau$ og $\sigma$ for $n=540$ og $n=200$ .

Løkke 3: Multiplikativitet — og vilkåret

~9 minutter.

Begge formlene er egentlig samme observasjon: funksjonene er multiplikative. Det er et begrep du kjenner fra $\phi$ i kap. 2.1 — og vilkåret er det samme, og like ufravikelig.

Multiplikativ funksjon

f

📝Oppgave 3

a) Regn ut

\tau(1000)

\sigma(1000)

ved å bruke multiplikativiteten på

1000=8\cdot 125

.
b) Vis med et konkret eksempel at

\tau(mn)=\tau(m)\tau(n)

ikke holder når

\gcd(m,n)>1

Løkke 4: Minste n med gitt antall divisorer

~13 minutter.

Den mest karakteristiske H-oppgaven, og den som ser vanskeligst ut: «finn det minste positive heltallet med nøyaktig $18$ divisorer». Den er ikke et søk — den er en faktorisering av måltallet, og oppskriften er kort.

— naturlig pausepunkt —

Oppskrift: minste n med τ(n) = m

n

✏️Minste n med 18 divisorer

Finn det minste positive heltallet $n$ med $\tau(n)=18$ .

Steg 1: faktoriser måltallet på alle måter. Vi har

18=2\cdot 3^2

, og faktoriseringene i faktorer

\ge 2

18,\qquad 9\cdot 2,\qquad 6\cdot 3,\qquad 3\cdot 3\cdot 2.

(Rekkefølgen spiller ingen rolle, så

2\cdot 9

er samme som

9\cdot 2

Steg 2–3: gjør hver om til en eksponentliste, sortert synkende, og plasser på de minste primtallene.

Faktorisering	Eksponenter $f_i-1$	Kandidat	Verdi
$18$	$17$	$2^{17}$	$131\,072$
$9\cdot 2$	$8,1$	$2^8\cdot 3$	$256\cdot 3=768$
$6\cdot 3$	$5,2$	$2^5\cdot 3^2$	$32\cdot 9=288$
$3\cdot 3\cdot 2$	$2,2,1$	$2^2\cdot 3^2\cdot 5$	$4\cdot 9\cdot 5=180$

Steg 4: velg den minste. Den minste kandidaten er

n=180.

Kontroll.

180=2^2\cdot 3^2\cdot 5

, så

\tau(180)=(2+1)(2+1)(1+1)=3\cdot 3\cdot 2=18\ \checkmark

Konklusjon i ord: det minste positive heltallet med nøyaktig

18

divisorer er

180

Sluttsvar: $n=180$ .
Tre observasjoner verdt å ta med til neste oppgave av denne typen.

Først: flest faktorer vant. Faktoriseringen med tre faktorer ( $3\cdot 3\cdot 2$ ) ga det minste tallet, og det er det vanlige mønsteret — flere primtall med lave eksponenter slår få primtall med høye. Men det er ikke en regel du kan stole blindt på, så regn ut alle kandidatene.
Dernest: den ene faktoren $18$ er alltid håpløs. $2^{m-1}$ er nesten alltid den største kandidaten, og du kan sette den nederst på listen med én gang.

Til sist: sorteringen i steg 3 er ikke valgfri. Hadde vi skrevet $2^1\cdot 3^2\cdot 5^2=450$ i stedet for $2^2\cdot 3^2\cdot 5=180$ , ville vi fått samme $\tau$ men et større tall. Store eksponenter på små primtall — hver gang.

📝Oppgave 4

Finn det minste positive heltallet med nøyaktig $10$ divisorer, og det minste med nøyaktig $12$ divisorer.

📝Oppgave 5

a) Finn det minste positive heltallet med nøyaktig

16

divisorer.
b) Finn det minste positive heltallet med nøyaktig

14

divisorer, og forklar hvorfor svaret blir så mye større enn i a).

Løkke 5: Identitetene

~11 minutter.

Til slutt fire små resultater som dukker opp som «vis at»-oppgaver. Alle utledes på stedet i to–tre linjer, og alle hviler på divisorstrukturen fra løkke 1.

τ(n) er odde nøyaktig når n er et kvadrattall

\tau(n)\ \text{odde}\quad\Longleftrightarrow\quad n\ \text{er et kvadrattall}.

σ(n)/n som en sum av brøker

\frac{\sigma(n)}{n}=\sum_{d\mid n}\frac 1d.

Perfekte tall

n

$n$	divisorer	$\sigma(n)$
$6$	$1,2,3,6$	$12=2\cdot 6$ ✓
$28$	$1,2,4,7,14,28$	$56=2\cdot 28$ ✓
$496$	$1,2,4,8,16,31,62,124,248,496$	$992=2\cdot 496$ ✓

✏️Eksamensnivå: identiteter og en optimering

a) Vis at

\tau(n)

er odde hvis og bare hvis

n

er et kvadrattall.
b) Vis at

\sigma(n)=n+1

hvis og bare hvis

n

er et primtall.
c) Finn det minste

n>1

med både

\tau(n)

odde og

\tau(n)>3

a) Skriv

n=\prod_i p_i^{k_i}

. Etter formelen er

\tau(n)=\prod_i(k_i+1).

Retning $\Rightarrow$ . Er produktet odde, må hver faktor $k_i+1$ være odde (et produkt med minst én partallsfaktor er partall). Da er hver $k_i$ partall, si $k_i=2m_i$ , og
$n=\prod_i p_i^{2m_i}=\left(\prod_i p_i^{m_i}\right)^2$
er et kvadrattall.

Retning $\Leftarrow$ . Er $n=t^2$ et kvadrattall, har $n$ alle eksponenter partall (faktoriser $t$ og doble eksponentene — entydigheten i aritmetikkens fundamentalteorem gir at det er alle eksponentene i $n$ ). Da er hver $k_i+1$ odde, og produktet er odde. $\blacksquare$

Alternativt bevis, like fullgodt: divisorene i $n$ kommer i par $(d,n/d)$ . To slike er like nøyaktig når $d^2=n$ . Er $n$ ikke et kvadrattall, er alle par ekte og antallet er partall; er $n=t^2$ , står $t$ alene og antallet er odde.

b) Retning $\Leftarrow$ . Er $n=p$ et primtall, er divisorene bare $1$ og $p$ , så $\sigma(p)=1+p=n+1$ .

Retning $\Rightarrow$ . Anta $\sigma(n)=n+1$ med $n>1$ . Både $1$ og $n$ er divisorer, og de bidrar med $1+n$ til summen. Da kan det ikke finnes flere divisorer — enhver ekstra divisor $d$ med $1<d<n$ ville gjort summen strengt større enn $n+1$ . Et tall $n>1$ med bare divisorene $1$ og $n$ er per definisjon et primtall. $\blacksquare$

(Merk at $n=1$ er unntatt: $\sigma(1)=1$ , ikke $2$ .)

c) Vi trenger $\tau(n)$ odde, altså — etter a) — at $n$ er et kvadrattall. Og vi trenger $\tau(n)>3$ .

Vi går gjennom kvadrattallene i stigende rekkefølge og regner $\tau$ :

$n$	faktorisering	$\tau(n)$
$4$	$2^2$	$3$
$9$	$3^2$	$3$
$16$	$2^4$	$5$ ✓

De to første har

\tau=3

, som ikke er

>3

. Ved

n=16=2^4

\tau(16)=4+1=5

, som er odde og større enn

3

.
Altså er $n=16$ det minste.
Kontroll: divisorene i

16

1,2,4,8,16

— fem stykker, odde antall ✓, og

16=4^2

er et kvadrattall ✓.
(Merk at $36=6^2$ også har odde $\tau$ , nemlig $9$ , men $36>16$ .)

Sluttsvar: a) og b) bevist begge veier; c) $n=16$ .

Om føringen i a) og b): begge er ekvivalenser, og da må begge retninger vises. Å bare vise én vei er den dokumenterte fellen i «hvis og bare hvis»-oppgaver, og den koster halve uttellingen. Skriv retningene som to merkede avsnitt, slik det er gjort her — da ser både du og sensor at begge er med.

📝Oppgave 6

a) Regn ut

\sigma(496)

og avgjør om

496

er et perfekt tall.
b) Bruk Euklids karakterisering til å finne det neste perfekte tallet etter

496

. (Du kan bruke at

2^7-1=127

er et primtall.)

📝Oppgave 7

a) Finn alle

n

med

\tau(n)=3

.
b) Finn alle

n

med

\tau(n)=4

.
c) Hva er den generelle betingelsen for at

\tau(n)

er et primtall

q

📝Oppgave 8

a) Vis at

\dfrac{\sigma(n)}{n}=\sum_{d\mid n}\dfrac 1d

.
b) Bruk identiteten til å avgjøre om

\displaystyle \sum_{d\mid 24}\frac 1d

er større eller mindre enn

2

.
c) Vis at

\sigma(n)\equiv\tau(n)\pmod 2

når

n

er et oddetall.

Typiske feil

De fem feilene under er dokumentert i arkivets løsningsforslag som noe fasiten advarer mot.

- Regner $\tau(n)=\prod k_i$ i stedet for $\prod(k_i+1)$ . Den best belagte feilen i sjangeren. Grunnen til « $+1$ » er at eksponenten $0$ også er et lovlig valg — divisoren $1$ tar ingen primfaktorer. Kontrollen: $\tau(12)$ skal være $6$ ( $12=2^2\cdot 3$ gir $3\cdot 2$ ), og du kan liste divisorene $1,2,3,4,6,12$ på fem sekunder for å være sikker.

- Bruker multiplikativiteten på faktorer som ikke er relativt primiske. $\tau(4)\tau(6)=12$ , men $\tau(24)=8$ . Sjekk $\gcd$ -en før du splitter, og skriv den linjen i besvarelsen.

- Fordeler eksponentene på feil primtall i minste- $n$ -oppgaven. Den største eksponenten skal på det minste primtallet. $2^2\cdot 3^2\cdot 5=180$ , men $2\cdot 3^2\cdot 5^2=450$ — samme $\tau$ , mer enn dobbelt så stort tall.

- Glemmer å prøve alle faktoriseringene av måltallet. For $\tau(n)=16$ er det fem kandidater, og vinneren ( $120$ ) er verken den mest eller minst oppdelte. Skriv opp hele listen før du regner.

- Feil $\sigma$ -formel. $\sigma(p^k)$ er $\displaystyle \frac{p^{k+1}-1}{p-1}$ , ikke $\displaystyle \frac{p^k-1}{p-1}$ — eksponenten er $k+1$ , fordi summen har $k+1$ ledd. Kontrollen er gratis: summér direkte for små eksponenter, $\sigma(2^3)=1+2+4+8=15$ , og se at brøken gir samme tall.

Og to føringsfeil som koster uten å være regnefeil:

- Faktoriseringen mangler i besvarelsen. Den er begrunnelsen i denne sjangeren — formelen er ubrukelig uten den. Et $\tau$ -tall alene er et sluttall uten metode.
- Bare én retning vist i en «hvis og bare hvis»-oppgave. « $\tau(n)$ odde $\iff$ $n$ kvadrattall» krever begge veier, eller en ekvivalenskjede som dekker begge.

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. Men merk at dette er et av de minst puggetunge kapitlene i boka: én formel må sitte kaldt ( $\tau$ ), én utledes fra videregåendealgebra ( $\sigma$ ), og én er en oppskrift du kjører (minste- $n$ ).

Slik pugges de: $\tau$ -formelen ved aktiv gjenkalling, $\sigma$ ved å utlede den et par ganger til utledningen er automatisk, og minste- $n$ -oppskriften ved å kjøres på nye måltall.

Notasjonen τ, σ og φ

\tau(n)

Funksjon	Betyr	Formel
$\tau(n)$	antall divisorer	$\prod(k_i+1)$
$\sigma(n)$	sum av divisorene	$\displaystyle \prod\frac{p_i^{k_i+1}-1}{p_i-1}$
$\phi(n)$	antall $\le n$ relativt primiske til $n$	$\prod(p_i^{k_i}-p_i^{k_i-1})$

Kort: τ-formelen

\tau(n)=\prod_i(k_i+1)\qquad\text{for } n=\prod_i p_i^{k_i}.

$n$	$\tau(n)$
primtall $p$	$2$
$p^2$	$3$
$p^3$ eller $pq$	$4$
$60=2^2\cdot 3\cdot 5$	$12$
$120=2^3\cdot 3\cdot 5$	$16$
$360=2^3\cdot 3^2\cdot 5$	$24$

Kort: σ-formelen og utledningen

\sigma(p^k)=1+p+\dots+p^k=\frac{p^{k+1}-1}{p-1},\qquad \sigma(n)=\prod_i\sigma(p_i^{k_i}).

$p^k$	$\sigma$
$2,4,8,16,32,64$	$3,7,15,31,63,127$
$3,9,27,81$	$4,13,40,121$
$5,25,125$	$6,31,156$
$7,49$	$8,57$
$11,13$	$12,14$

Kort: minste n med gitt τ

m

$m$	minste $n$	faktorisering av $n$
$6$	$12$	$2^2\cdot 3$
$8$	$24$	$2^3\cdot 3$
$10$	$48$	$2^4\cdot 3$
$12$	$60$	$2^2\cdot 3\cdot 5$
$14$	$192$	$2^6\cdot 3$
$16$	$120$	$2^3\cdot 3\cdot 5$
$18$	$180$	$2^2\cdot 3^2\cdot 5$
$24$	$360$	$2^3\cdot 3^2\cdot 5$

Kort: de fire identitetene

\tau(n)

Kort: kontrollene i sjanger H

\tau

Kort: tidsbudsjettet for en H-oppgave

\tau(n)

Oppgavetype	Tid
«Finn $\tau(n)$ »	~2 min
«Finn $\tau(n)$ og $\sigma(n)$ »	~4 min
«Minste $n$ med $\tau(n)=m$ »	~7 min
«Vis at $\tau(n)$ er odde $\iff$ kvadrattall»	~5 min
«Finn alle $n$ med $\tau(n)=4$ »	~5 min

Kort: rask faktorisering for hånd

2

Divisor	Test
$2$	siste siffer er partall
$3$	siffersummen er delelig med $3$
$4$	de to siste sifrene danner et tall delelig med $4$
$5$	siste siffer er $0$ eller $5$
$9$	siffersummen er delelig med $9$
$11$	alternerende siffersum er delelig med $11$

Kort: hvor τ og σ dukker opp ellers

\phi

Kort: selvdiagnose for τ og σ

\tau(n)

Kort: å summere over divisorene

\sum_{d\mid n}f(d)

Kort: rimelighetsgrenser for τ og σ

\tau(n)\le 2\sqrt n

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.