Tilbake
5.4

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

Den «øvre halvdelens» repertoar drillet: finn og verifiser orden, verifiser og generer primitive røtter, tell elementer av gitt orden, og regn τ/σ + minste-n-med-gitt-τ — sjangrene som skiller C fra A.

75 min
13 oppgaver
Drillordenprimitive røttertallteoretiske funksjoner
Din fremgang i kapitlet
0 / 13 oppgaver

Forkunnskaper

Hele Del 5: kap. 5.1 (orden, ordenslemmaet, potensformelen), kap. 5.2 (primitive røtter, eksistens, telling) og kap. 5.3 (τ\tau, σ\sigma, multiplikativitet, minste-nn). Du bør også ha ϕ\phi fra kap. 2.1 og kvadrer-og-multipliser i fingrene.

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

Ordenslemmaet. at1(modn)    ordn(a)ta^t\equiv 1\pmod n\iff\operatorname{ord}_n(a)\mid t, og spesielt ordn(a)ϕ(n)\operatorname{ord}_n(a)\mid\phi(n).

Potensformelen. ordn(ak)=ordn(a)gcd(k,ordn(a))\operatorname{ord}_n(a^k)=\dfrac{\operatorname{ord}_n(a)}{\gcd(k,\operatorname{ord}_n(a))}.

Primdivisortesten. aa er primitiv rot     aϕ(n)/q≢1\iff a^{\phi(n)/q}\not\equiv 1 for hver primdivisor qq av ϕ(n)\phi(n).

Antallene. ϕ(ϕ(n))\phi(\phi(n)) primitive røtter; ϕ(d)\phi(d) elementer av orden dd.

τ\tau og σ\sigma. τ(n)=(ki+1)\tau(n)=\prod(k_i+1) og σ(n)=piki+11pi1\displaystyle \sigma(n)=\prod\frac{p_i^{k_i+1}-1}{p_i-1}, begge fra faktoriseringen.

Fra videregående kreves ingenting.

Løsningsoppskriftene

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

Del 5 har tre prosedyrer, ikke én. De ser like ut, men de svarer på ulike spørsmål og krever ulikt mye arbeid. Det er verdt å holde dem skarpt fra hverandre.

Oppskrift: finn ordenen (divisortesten)

For ordn(a)\operatorname{ord}_n(a):

1. Sjekk gcd(a,n)=1\gcd(a,n)=1 og si det. Uten det finnes ingen orden.
2. Regn ϕ(n)\phi(n) fra faktoriseringen av nn.
3. List divisorene av ϕ(n)\phi(n) stigende.
4. Test dem stigende med kvadrer-og-multipliser. Første dd med ad1a^d\equiv 1 er ordenen.
5. Konkludér: «ordn(a)=d\operatorname{ord}_n(a)=d, og de mindre divisorene ga ikke 11

Antall potenser: så mange divisorer du må gjennom — typisk 3–5, siden du stopper ved første treff.

Snarveien: lander en potens på 1-1, er ordenen det dobbelte av den eksponenten. Se etter tall rett under modulusen.

Oppskriften må sitte utenat. Steg 5 er det som glemmes, og «minste»-begrunnelsen er egne poeng — instruksen på hvert eksamenssett er at alle svar skal begrunnes.

Oppskrift: verifiser en primitiv rot (primdivisortesten)

For «er aa en primitiv rot modulo nn?»:

1. Sjekk formen på nn: primitiv rot finnes bare for n=2n=2, 44, pkp^k, 2pk2p^k. Er nn ikke slik, er svaret «finnes ikke».
2. Sjekk gcd(a,n)=1\gcd(a,n)=1.
3. Regn ϕ(n)\phi(n) og faktoriser den. List de ulike primdivisorene q1,,qrq_1,\dots,q_r.
4. Regn aϕ(n)/qimodna^{\phi(n)/q_i}\bmod n for hver iién potens per primdivisor.
5. Konkludér: alle 1\ne 1 gir primitiv rot; én lik 11 gir «nei».

Antall potenser: antall ulike primfaktorer i ϕ(n)\phi(n) — nesten alltid 22 eller 33. Det er derfor denne testen er billigere enn divisortesten, og forskjellen er hele poenget med å holde de to prosedyrene fra hverandre.

Gratis utelukkelse: en kvadratisk rest kan ikke være primitiv rot. Sjekk (ap)\displaystyle \left(\frac ap\right) først — for a=2a=2 avgjør 8-regelen (kap. 4.2) det på ett sekund.

Når testen feiler, les av informasjonen: er aϕ(n)/q1a^{\phi(n)/q}\equiv 1, deler ordenen ϕ(n)/q\phi(n)/q, og du har innsnevret den gratis.

Oppskrift: τ, σ og minste n

For τ(n)\tau(n) og σ(n)\sigma(n):

1. Faktoriser nn. (Del ut 22, 33, 55, 77, 1111, 1313 i tur og orden.)
2. τ(n)=(ki+1)\tau(n)=\prod(k_i+1) — legg til 11 på hver eksponent og gang sammen.
3. σ(n)=σ(piki)\sigma(n)=\prod\sigma(p_i^{k_i}), der σ(pk)=1+p++pk\sigma(p^k)=1+p+\dots+p^k (summer direkte for små eksponenter).
4. Kontrollér: σ(n)>n\sigma(n)>n, og τ(n)2n\tau(n)\le 2\sqrt n.

For «minste nn med τ(n)=m\tau(n)=m»:

1. Faktoriser måltallet mmalle måter i faktorer 2\ge 2.
2. Eksponentene er fi1f_i-1 for hver faktorisering.
3. Sorter synkende og plasser på 2,3,5,7,2,3,5,7,\dots — store eksponenter på små primtall.
4. Regn ut alle kandidatene og velg den minste.
5. Kontrollér ved å regne τ\tau av svaret.

Begge oppskriftene må sitte utenat. Merk at τ\tau-oppgaver er blant de raskeste delpunktene i hele faget: fem minutter når faktoriseringen går greit.

De fem kontrollpunktene

Under kode D er selvkontroll den eneste kontrollen du har. Disse fem tar til sammen under ett minutt.

1. Deler ordenen ϕ(n)\phi(n)? Alltid. Får du noe annet, er det regnefeil, ikke et nytt svar.

2. Er aϕ(n)1a^{\phi(n)}\equiv 1? Eulers teorem krever det. En rask sjekk på slutten av en ordensoppgave.

3. Er alle primdivisorene testet? Tell dem: antall tester = antall ulike primfaktorer i ϕ(n)\phi(n). Én test er nesten aldri nok.

4. Summerer ϕ(d)\phi(d)-ene til ϕ(n)\phi(n)? dϕ(n)ϕ(d)=ϕ(n)\sum_{d\mid\phi(n)}\phi(d)=\phi(n) er fullstendighetskontrollen på enhver telling av elementer etter orden.

5. Gir kandidaten riktig τ\tau? I minste-nn-oppgaven: regn τ\tau av svaret ditt og se at du får måltallet.

Legg til to gratis grovkontroller:

- σ(n)>n\sigma(n)>n alltid (for n>1n>1), og σ(n)<nτ(n)\sigma(n)<n\cdot\tau(n).
- τ(n)2n\tau(n)\le 2\sqrt n — for n=720n=720 er 2720542\sqrt{720}\approx 54, og τ=30\tau=30 ✓.

Gjennomregnet eksamenscase

~15 minutter.

Her er en typisk Del 5-oppgave med fire delpunkt som bygger på hverandre — G og H kombinert, nøyaktig i den formen arkivet bruker. Underveis står margnotater som sier hva hvert steg gir uttelling for. De er destillert fra hvordan løsningsforslagene i arkivet fører sjangeren, og fra oppgaveinstruksen om at alle svar skal begrunnes.

— naturlig pausepunkt —

✏️Eksamenscase: primitiv rot, telling og divisorfunksjoner

La p=37p=37.

a) Vis at 55 er en primitiv rot modulo 3737.
b) Hvor mange primitive røtter finnes modulo 3737?
c) Hvor mange elementer har orden 99 modulo 3737?
d) Regn ut τ(36)\tau(36) og σ(36)\sigma(36), og forklar hvorfor τ(36)\tau(36) er relevant for delpunkt a).

Del a)

Steg 1: formen på modulusen. 3737 er et primtall, altså på formen pkp^k med k=1k=1 — så en primitiv rot finnes.

Steg 2: vilkåret. gcd(5,37)=1\gcd(5,37)=1, siden 3737 er primtall og 37537\nmid 5.

Steg 3: ϕ(n)\phi(n) og faktoriseringen.
ϕ(37)=36=2232.\phi(37)=36=2^2\cdot 3^2.
De ulike primdivisorene er q=2q=2 og q=3q=3, så vi skal regne to potenser:
536/2=518og536/3=512.5^{36/2}=5^{18}\qquad\text{og}\qquad 5^{36/3}=5^{12}.

Steg 4: regn dem. Vi bygger opp de suksessive kvadratene, og bruker små representanter der vi kan:

potensutregningverdi mod 3737
525^22525251225\equiv -12
545^4(12)2=144=337+33(-12)^2=144=3\cdot 37+3333433\equiv -4
585^8(4)2=16(-4)^2=161616
5125^{12}585416(4)=645^8\cdot 5^4\equiv 16\cdot(-4)=-6464+74=10-64+74=10
5165^{16}162=256=637+3416^2=256=6\cdot 37+3434334\equiv -3
5185^{18}51652(3)(12)=365^{16}\cdot 5^2\equiv(-3)(-12)=3636136\equiv -1

Test 1 (q=2q=2): 518361≢15^{18}\equiv 36\equiv -1\not\equiv 1
Test 2 (q=3q=3): 51210≢15^{12}\equiv 10\not\equiv 1
Steg 5: konklusjon. Begge testene er bestått, så ved primdivisortesten er
ord37(5)=ϕ(37)=36,\operatorname{ord}_{37}(5)=\phi(37)=36,
og 55 er en primitiv rot modulo 3737.
Sensorblikk på del a). Fire ting gir uttelling, hver for seg. (1) Faktoriseringen 36=223236=2^2\cdot 3^2 står skrevet — det er den som forklarer hvorfor nettopp 1818 og 1212 er de riktige eksponentene. (2) Begge primdivisorene er testet. Én test alene ville vært ufullstendig, og det er den best belagte feilen i sjangeren. (3) Testen er navngitt («ved primdivisortesten»). (4) Konklusjonen står som en setning med ordenen oppgitt.
Merk også at 51815^{18}\equiv -1 er nøyaktig som forventet: 5185^{18} er en kvadratrot av 53615^{36}\equiv 1, og modulo et primtall er kvadratrøttene av 11 bare ±1\pm 1. Får du noe annet i den raden, er det regnefeil.

Del b)

Antall primitive røtter er

ϕ(ϕ(37))=ϕ(36).\phi(\phi(37))=\phi(36).
Med 36=223236=2^2\cdot 3^2 og multiplikativiteten (kap. 2.1):
ϕ(36)=ϕ(4)ϕ(9)=(42)(93)=26=12.\phi(36)=\phi(4)\phi(9)=(4-2)(9-3)=2\cdot 6=12.

Det finnes 1212 primitive røtter modulo 3737, av 3636 rester i alt.

Sensorblikk på del b). Dette delpunktet er gratis når formelen sitter: to linjer, ingen potensberegning. Men «1212» alene er et sluttall uten metode — utregningen av ϕ(36)\phi(36) er begrunnelsen, og den skal stå.

Den vanlige feilen her er å svare ϕ(37)=36\phi(37)=36. Det er antall rester, ikke antall primitive røtter.

Del c)


Ordenen 99 deler ϕ(37)=36\phi(37)=36, så tellingsteoremet gjelder: antall elementer av orden dd er ϕ(d)\phi(d). Med d=9=32d=9=3^2:
ϕ(9)=93=6.\phi(9)=9-3=6.
Seks elementer har orden 99 modulo 3737.

(Vil man ha dem, er de (536/9)k=(54)k\left(5^{36/9}\right)^k=(5^4)^k med gcd(k,9)=1\gcd(k,9)=1, altså k=1,2,4,5,7,8k=1,2,4,5,7,8 — og 54335^4\equiv 33 fra tabellen i a).)

Sensorblikk på del c). To ting kreves: at dϕ(n)d\mid\phi(n) sjekkes (ellers finnes ingen slike elementer), og at formelen ϕ(d)\phi(d) brukes — ikke dd selv. Å svare «99» i stedet for «66» er den dokumenterte fellen.

Del d)

τ(36)\tau(36) og σ(36)\sigma(36) fra faktoriseringen 36=223236=2^2\cdot 3^2:

τ(36)=(2+1)(2+1)=33=9,\tau(36)=(2+1)(2+1)=3\cdot 3=9,
σ(36)=σ(22)σ(32)=(1+2+4)(1+3+9)=713=91.\sigma(36)=\sigma(2^2)\sigma(3^2)=(1+2+4)(1+3+9)=7\cdot 13=91.

Kontroll: divisorene i 3636 er 1,2,3,4,6,9,12,18,361,2,3,4,6,9,12,18,36 — ni stykker ✓ (og et oddetall, som det skal være for et kvadrattall). Summen er 9191 ✓.

Hvorfor τ(36)\tau(36) er relevant for a): tallet τ(36)=9\tau(36)=9 er nøyaktig antall divisorer av ϕ(37)\phi(37), altså antall mulige ordener modulo 3737 — og dermed antall potenser en full divisortest (kap. 5.1) ville krevd i verste fall.

Primdivisortesten trengte bare to. Forholdet 99 mot 22 er hele gevinsten ved å bruke den riktige prosedyren, og det er derfor de to skal holdes fra hverandre.

Sluttsvar: a) 55 er en primitiv rot, med orden 3636; b) 1212; c) 66; d) τ(36)=9\tau(36)=9 og σ(36)=91\sigma(36)=91, og 99 er antall mulige ordener — mot to tester i primdivisortesten.

Sensorblikk på hele oppgaven. Tidsbruk: a) ~8 min, b) ~2 min, c) ~2 min, d) ~3 min — til sammen ~15 minutter for fire delpunkt. Det er slik en drillet Del 5-oppgave skal føles: ett tungt delpunkt med potensregning, og tre nesten gratis når formlene sitter.
Legg merke til at delpunkt b), c) og d) ikke krevde en eneste ny potensberegning. Det er det typiske mønsteret i sjangeren, og det er grunnen til at tellingsformlene er verdt å pugge selv om de ser trivielle ut.

Oppgavene

~40 minutter til sammen. Tretten oppgaver, gruppert etter variant.

Regn dem med penn og lukket bok. Det er den eneste treningsformen som ligner eksamen.

Slik er de gruppert:

- Oppgave 1–3: finn ordenen (divisortesten)
- Oppgave 4–5: verifiser en primitiv rot (primdivisortesten)
- Oppgave 6–7: telling og generering
- Oppgave 8–10: τ\tau og σ\sigma
- Oppgave 11–12: minste nn med gitt τ\tau
- Oppgave 13: kjedet G+H-oppgave i eksamensform

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

— naturlig pausepunkt —

📝Oppgave 1

Finn ord19(7)\operatorname{ord}_{19}(7).

📝Oppgave 2

Finn ord29(12)\operatorname{ord}_{29}(12).

📝Oppgave 3
a) Finn ord37(10)\operatorname{ord}_{37}(10).
b) Bruk svaret til å finne resten når 1010010^{100} deles på 3737.
c) Hva er perioden i desimalutviklingen av 137\tfrac 1{37}?
📝Oppgave 4

Vis at 22 er en primitiv rot modulo 5353.

📝Oppgave 5

Vis at 33 er en primitiv rot modulo 4343.

📝Oppgave 6

Bruk at 33 er en primitiv rot modulo 4343 (oppgave 5).

a) Hvor mange primitive røtter finnes modulo 4343?
b) Hvor mange elementer har orden 66 modulo 4343?
c) Finn dem.

📝Oppgave 7

Det er oppgitt at 22 er en primitiv rot modulo 1313.

a) Hvor mange primitive røtter finnes modulo 1313?
b) Finn dem alle.

📝Oppgave 8

Finn τ(720)\tau(720) og σ(720)\sigma(720).

📝Oppgave 9

Finn τ(588)\tau(588) og σ(588)\sigma(588).

📝Oppgave 10
a) Finn τ\tau og σ\sigma for 12601\,260 og for 15001\,500.
b) Kommentér noe uventet i svarene.
📝Oppgave 11

Finn det minste positive heltallet nn med τ(n)=20\tau(n)=20.

📝Oppgave 12
a) Finn det minste positive heltallet nn med τ(n)=30\tau(n)=30.
b) Sammenlign med svaret i oppgave 11 og forklar forskjellen.
📝Oppgave 13

La p=23p=23.

a) Vis at 1111 er en primitiv rot modulo 2323.
b) Hvor mange primitive røtter finnes modulo 2323?
c) Hvor mange elementer har orden 1111 modulo 2323?
d) Regn ut τ(22)\tau(22) og σ(22)\sigma(22), og si hva τ(22)\tau(22) betyr for hvor mange mulige ordener det finnes modulo 2323.

Prosedyrekort

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

Drillkapitlene har ingen begrepsbank i vanlig forstand. I stedet er kortene her oppskriftskort: hvert av dem er en prosedyre du skal kunne kjøre, ikke et faktum du skal kunne si.

Og det er slik de skal pugges: ikke ved å lese kortet, men ved å kjøre prosedyren på nye tall. Velg selv et primtall mellom 3030 og 6060 og et tall aa, og regn. Et kort du har lest fem ganger, hjelper deg ikke 24. november.

Kort: finn ordenen (divisortesten)
1. gcd(a,n)=1\gcd(a,n)=1? Si det.
2. Regn ϕ(n)\phi(n).
3. List divisorene stigende.
4. Test dem stigende med kvadrer-og-multipliser; første 11 er ordenen.
5. Konkludér: «ordn(a)=d\operatorname{ord}_n(a)=d; de mindre divisorene ga ikke 11

Snarveier: bygg hver potens på den forrige; se etter 1-1 (da er ordenen det dobbelte); stopp ved første treff.

Kontroller: deler svaret ϕ(n)\phi(n)? Er aϕ(n)1a^{\phi(n)}\equiv 1?

Antall potenser: 3–5 typisk.

Kjør den nå, på ord31(7)\operatorname{ord}_{31}(7) og ord41(9)\operatorname{ord}_{41}(9), uten å se på oppskriften. (Svar: ϕ(31)=30\phi(31)=30 med divisorer 1,2,3,5,6,10,15,301,2,3,5,6,10,15,30. Testene gir 72187^2\equiv 18, 7327^3\equiv 2, 7557^5\equiv 5, 7647^6\equiv 4, 710257^{10}\equiv 25 og 71517^{15}\equiv 1 — ordenen er 1515. For 4141: ϕ=40\phi=40, 9=329=3^2 og ord41(3)=8\operatorname{ord}_{41}(3)=8, så ord41(9)=8/gcd(2,8)=4\operatorname{ord}_{41}(9)=8/\gcd(2,8)=4.)

Kort: verifiser en primitiv rot
1. Er nn på formen 22, 44, pkp^k eller 2pk2p^k? Ellers: «finnes ikke».
2. gcd(a,n)=1\gcd(a,n)=1?
3. Regn ϕ(n)\phi(n), faktoriser den, og list de ulike primdivisorene qq.
4. Regn aϕ(n)/qa^{\phi(n)/q} for hver qq — én potens per primdivisor.
5. Alle 1\ne 1 ⟹ primitiv rot. Én =1=1 ⟹ nei (og ordenen deler den eksponenten).

Antall potenser = antall ulike primfaktorer i ϕ(n)\phi(n). Nesten alltid 22 eller 33.

Gratis utelukkelse: er (ap)=1\displaystyle \left(\frac ap\right)=1, kan aa ikke være primitiv rot. For a=2a=2: 8-regelen.

Planlegging som halverer arbeidet: velg en mellompotens du kan gjenbruke. For ϕ(n)=42\phi(n)=42 er alle tre eksponentene (2121, 1414, 66) bygget lett på 363^6 og 373^7.

Forventet mønster ved «ja»: testen for q=2q=2 gir 1-1.

Kjør den nå, på a=2a=2, n=59n=59, uten å se. (Svar: ϕ=58=229\phi=58=2\cdot 29; test 2292^{29} og 222^2. 22=412^2=4\ne 1 ✓, og 22958112^{29}\equiv 58\equiv -1\ne 1 ✓ — altså primitiv rot.)

Kort: tellingsformlene
#{primitive røtter mod n}=ϕ(ϕ(n)),\#\{\text{primitive røtter mod } n\}=\phi(\phi(n)),
#{a:ordn(a)=d}=ϕ(d)for dϕ(n),\#\{a:\operatorname{ord}_n(a)=d\}=\phi(d)\quad\text{for } d\mid\phi(n),
#{mulige ordener mod n}=τ(ϕ(n)).\#\{\text{mulige ordener mod } n\}=\tau(\phi(n)).

Alle tre er gratis når formlene sitter — ingen potensberegning.

Fullstendighetskontrollen:
dϕ(n)ϕ(d)=ϕ(n).\sum_{d\mid\phi(n)}\phi(d)=\phi(n).

Konstruksjonene:

- ett element av orden dd: rϕ(n)/dr^{\phi(n)/d};
- alle av orden dd: potensene av det med eksponent relativt primisk til dd;
- alle primitive røtter: rkr^k med gcd(k,ϕ(n))=1\gcd(k,\phi(n))=1.

Vilkåret: tellingsformelen for orden dd krever at nn har en primitiv rot. Modulo 1515 gjelder den ikke.

De vanlige fellene: å svare ϕ(n)\phi(n) i stedet for ϕ(ϕ(n))\phi(\phi(n)), og dd i stedet for ϕ(d)\phi(d).

Kjør dem nå, for n=31n=31: (Svar: ϕ(31)=30\phi(31)=30; primitive røtter ϕ(30)=8\phi(30)=8; mulige ordener τ(30)=8\tau(30)=8; elementer av orden 55: ϕ(5)=4\phi(5)=4; kontroll d30ϕ(d)=1+1+2+4+2+4+8+8=30\sum_{d\mid 30}\phi(d)=1+1+2+4+2+4+8+8=30 ✓.)

Kort: τ og σ fra faktoriseringen
τ(n)=(ki+1),σ(n)=σ(piki),σ(pk)=1+p++pk.\tau(n)=\prod(k_i+1),\qquad \sigma(n)=\prod\sigma(p_i^{k_i}),\qquad \sigma(p^k)=1+p+\dots+p^k.

Arbeidsflyten: faktoriser → regn per primtallspotens → gang sammen → kontrollér.

σ\sigma-verdier verdt å kjenne igjen:

pkp^kσ\sigma
2,4,8,16,322,4,8,16,323,7,15,31,633,7,15,31,63
3,9,27,813,9,27,814,13,40,1214,13,40,121
5,25,1255,25,1256,31,1566,31,156
7,497,498,578,57

Kontrollene: σ(n)>n\sigma(n)>n; σ(n)<nτ(n)\sigma(n)<n\tau(n); τ(n)2n\tau(n)\le 2\sqrt n; τ(n)\tau(n) odde     \iff nn kvadrattall.
Vilkåret for multiplikativitet: gcd=1\gcd=1. Alltid.
Kjør dem nå, på n=1080n=1\,080 og n=1001n=1\,001. (Svar: 1080=233351\,080=2^3\cdot 3^3\cdot 5 gir τ=442=32\tau=4\cdot 4\cdot 2=32 og σ=15406=3600\sigma=15\cdot 40\cdot 6=3\,600. Og 1001=711131\,001=7\cdot 11\cdot 13 gir τ=222=8\tau=2\cdot 2\cdot 2=8 og σ=81214=1344\sigma=8\cdot 12\cdot 14=1\,344.)
Kort: minste n med gitt τ
1. Faktoriser måltallet mmalle måter i faktorer 2\ge 2.
2. Eksponentene er fi1f_i-1.
3. Sorter synkende; største eksponent på 22, neste på 33, så 55, 77.
4. Regn ut alle kandidatene; velg minste.
5. Kontrollér τ\tau av svaret.

Fasit for de vanlige måltallene:

mm668810101212141416161818202024243030
minste nn1212242448486060192192120120180180240240360360720720

Mønsteret: store primfaktorer i mm tvinger store eksponenter og dermed store svar (m=14m=14 gir 192192, mens m=16m=16 gir 120120). Er mm et primtall qq, er svaret entydig 2q12^{q-1}.
Vanligste feil: å glemme en faktorisering av mm, eller å plassere eksponentene feil.

Kjør oppskriften nå, på m=36m=36. (Kandidater blant andre 2833=69122^8\cdot 3^3=6\,912, 25325=14402^5\cdot 3^2\cdot 5=1\,440, 223257=12602^2\cdot 3^2\cdot 5\cdot 7=1\,260; minste er 12601\,260.)

Kort: hold de tre prosedyrene fra hverandre

Den ene tingen som skiller en effektiv besvarelse fra en treg: å velge riktig prosedyre.

SpørsmåletProsedyreAntall potenser
«Hva er ordenen til aadivisortesten (alle divisorer, stigende)3–5
«Er aa en primitiv rot?»primdivisortesten (én per primdivisor)2–3
«Hvor mange har orden ddtellingsformelen ϕ(d)\phi(d)0

Poenget: primdivisortesten svarer bare på om ordenen er maksimal — den gir deg ikke ordenen når svaret er nei (bare en innsnevring). Divisortesten gir ordenen, men koster mer.
Og tellingsspørsmålene krever ingen regning i det hele tatt. Det er verdt å merke seg under tidspress: de er gratis poeng.
Feil valg av prosedyre er den vanligste grunnen til at et Del 5-delpunkt tar femten minutter i stedet for åtte.
Sjekk deg selv: hvilken prosedyre til «vis at 33 har orden 4242 modulo 4343»? (Svar: her er 42=ϕ(43)42=\phi(43), så det er primitiv-rot-spørsmålet i forkledning — bruk primdivisortesten, tre potenser, ikke åtte.)

Kort: regn med små representanter

Den enkeltvanen som sparer mest tid i potensregningen: erstatt en rest med sin negative motpart når den er nær modulusen.

Regelen: er a>n/2a>n/2, skriv aana\equiv a-n, altså et negativt tall med liten absoluttverdi.

Eksempler fra dette kapitlet:

I stedet forSkrivKvadratet blir
36(mod43)36\pmod{43}7-749649\equiv 6 i stedet for 12961\,296
44(mod53)44\pmod{53}9-9812881\equiv 28 i stedet for 19361\,936
33(mod37)33\pmod{37}4-41616 i stedet for 10891\,089
27(mod29)27\pmod{29}2-244 i stedet for 729729

Gevinsten: tallene du kvadrerer, holder seg under n/2n/2 i absoluttverdi, så produktene blir små nok å regne i hodet. Under kode D, med bare en enkel kalkulator, er det forskjellen mellom fem og femten minutter på en primdivisortest.
Og fortegnet er gratis informasjon: ender du på 1-1, har du enten funnet ordenen (snarveien) eller bestått q=2q=2-testen. Begge er ting du vil se.
Vanen å legge til seg: skriv resten som negativ med en gang du får et tall over n/2n/2, i stedet for å bære det med deg.

Kort: tidsbudsjettet for Del 5

Eksamen er 4 timer på rundt ti likt vektede delpunkt, altså ~24 minutter per delpunkt.

OppgavetypeTid
Finn ordenen~8 min
Verifiser en primitiv rot (2–3 tester)~7 min
Tell primitive røtter / elementer av orden dd~2 min
Finn elementene av orden dd~6 min
τ\tau og σ\sigma av et firesifret tall~5 min
Minste nn med gitt τ\tau~7 min
Kjedet G+H-oppgave (4 delpunkt)~15 min

Merk hvor billige tellespørsmålene er. De er ren gjengivelse av ϕ(ϕ(n))\phi(\phi(n)) og ϕ(d)\phi(d) — to minutter hver, og ubesvarelige uten formelen. Det er den beste avkastningen på pugging i hele Del 5.
Hvor tiden går galt: i potensberegningene (bruk små representanter) og i valg av prosedyre (primdivisortesten når spørsmålet er «er ordenen maksimal?»).
Realistisk forventning: en drillet Del 5-oppgave med fire delpunkt tar ~15 minutter, der ett delpunkt er tungt og tre er nesten gratis.

Kort: selvdiagnose for Del 5

Sitter Del 5? Dekk til boka, sett fem minutter, og svar:

- ☐ Hva er definisjonen av ordn(a)\operatorname{ord}_n(a), og hvilket vilkår kreves?
- ☐ Hva sier ordenslemmaet, begge veier?
- ☐ Hvorfor deler ordenen ϕ(n)\phi(n)?
- ☐ Hva er de fem stegene i divisortesten?
- ☐ Hva er primdivisortesten, og hvor mange potenser krever den?
- ☐ For hvilke nn finnes primitive røtter?
- ☐ Hvor mange primitive røtter, og hvor mange elementer av orden dd?
- ☐ Hva er τ(n)\tau(n)-formelen, og hva er σ(pk)\sigma(p^k)?
- ☐ Hva er de fire stegene i minste-nn-oppskriften?
- ☐ Hva er fullstendighetskontrollen på en ordenstelling?

Ti spørsmål. Det er hele Del 5.

Står mer enn tre åpne: gå tilbake til teorikapitlene (kap. 5.1kap. 5.3) og les løkkene på nytt før du tar prøvene i kap. 5.P.

Står tre eller færre åpne: hopp rett til prøvene. Du lærer mer av å regne dem under tidspress enn av å lese kapitlene en tredje gang.

Og uansett: regn tre nye ordener og verifiser to nye primitive røtter med lukket bok. Prosedyrer pugges ved å kjøres.

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.