5.2 Primitive røtter: eksistens, verifikasjon og telling

Primitiv rot = element av orden ϕ(n): eksistens (2, 4, pᵏ, 2pᵏ), verifikasjon ved å sjekke aᵈ≢1 for alle ekte divisorer av ϕ(n), generering av alle primitive røtter, og telling av elementer av gitt orden.

55 min

9 oppgaver

Primitive røttereksistensverifikasjontelling

Din fremgang i kapitlet

0 / 9 oppgaver

Kapitlets plass i kurset

Bygger på

5.1Orden modulo n og «orden deler ϕ(n)»

Primitive røtter er andre halvdel av sjanger G, som forekommer i 9 av 15 sett — 60 %. Sjangerbokstavene er bokas forkortelser for oppgavetypene, forklart i kap. 0.1.

Der kap. 5.1 handlet om å finne en orden, handler dette kapitlet om de tilfellene der ordenen er så stor den kan bli — og om å telle. Det er tellingen som er karakterskilleren: å verifisere en primitiv rot er mekanisk, men «hvor mange elementer har orden $4$ ?» krever at du kjenner strukturen.

Hva oppgaven spør om	Hva du trenger
«Vis at $a$ er en primitiv rot modulo $p$ »	primdivisortesten (løkke 2)
«Hvor mange primitive røtter finnes modulo $p$ ?»	$\phi(\phi(p))$ (løkke 4)
«Finn alle primitive røtter»	$r^k$ med $\gcd(k,\phi(n))=1$ (løkke 4)
«Hvor mange elementer har orden $d$ ?»	$\phi(d)$ (løkke 5)
«Har $n$ en primitiv rot?»	eksistenskriteriet $2$ , $4$ , $p^k$ , $2p^k$ (løkke 3)

Arkivets kalibrering av karakterskillene plasserer «orden og primitive røtter med telling» blant markørene for toppsjiktet, sammen med sikker kvadratisk resiprositet og ett stramt ført bevis. Mekanikken alene (Euklid,

\phi

, CRT, RSA med gitt

d

) gir bestått.
Prioritet: høy, men under Del 1–4. Skal du over C, er dette et av de tre stedene marginen ligger.
Merk den korte veien inn: verifikasjonstesten er billigere enn en full ordensberegning. Du tester bare én potens per primdivisor av

\phi(n)

— typisk to eller tre potenser, ikke åtte.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en enkel kalkulator. Det finnes ingen tabell over primitive røtter å slå opp i 24. november, og kalkulatoren kan ikke regne $a^k\bmod n$ for deg.

Må sitte utenat:

- definisjonen: $a$ er en primitiv rot modulo $n$ når $\operatorname{ord}_n(a)=\phi(n)$
- eksistenskriteriet: primitiv rot finnes nøyaktig for $n=2$ , $n=4$ , $n=p^k$ og $n=2p^k$ med $p$ et odde primtall — og for ingen andre $n$
- primdivisortesten: $a$ er primitiv rot $\iff$ $a^{\phi(n)/q}\not\equiv 1\pmod n$ for hver primdivisor $q$ av $\phi(n)$
- antallet: det finnes $\phi(\phi(n))$ primitive røtter modulo $n$ (når de finnes)
- antall elementer av orden $d$ : $\phi(d)$ , for hver $d$ som deler $\phi(n)$ (når en primitiv rot finnes)

Utledes på stedet:

- at alle primitive røtter er $r^k$ med $\gcd(k,\phi(n))=1$ — én linje ut av potensformelen fra kap. 5.1: $\operatorname{ord}(r^k)=\phi(n)/\gcd(k,\phi(n))$ , som er $\phi(n)$ nøyaktig når $\gcd(k,\phi(n))=1$ .
- at antallet er $\phi(\phi(n))$ — det er bare å telle de $k$ -ene: definisjonen av $\phi$ anvendt på $\phi(n)$ .
- at elementene av orden $d$ er $r^{k\phi(n)/d}$ med $\gcd(k,d)=1$ — samme formel, tre linjer (løkke 5).
- at en primitiv rot aldri er en kvadratisk rest — to linjer via Eulers kriterium (kap. 4.1).
- hvorfor primdivisortesten holder — tre linjer: en ekte divisor av $\phi(n)$ deler alltid en av tallene $\phi(n)/q$ .

Selvtest, tre minutter: dekk til boka og skriv ned eksistenskriteriet (fire former), primdivisortesten, og formelen for antallet. Nøler du på om testen bruker alle divisorer eller bare primdivisorene, er det den ene tingen å drille — den forskjellen er hele tidsbesparelsen i sjangeren.

Forkunnskaper

Fra boka: kap. 5.1 (orden, ordenslemmaet, potensformelen) er hele grunnlaget, og kap. 2.1 ( $\phi$ -funksjonen) brukes i hver eneste oppgave. Koblingen til kap. 4.1 (Eulers kriterium) gir en gratis utelukkelsestest i løkke 5.

Sist du var her. De fire resultatene fra kap. 5.1 som dette kapitlet står helt på, ferdig oppfrisket:

Ordenen. $\operatorname{ord}_n(a)$ er det minste $k\ge 1$ med $a^k\equiv 1\pmod n$ , og den finnes når $\gcd(a,n)=1$ .

Ordenslemmaet.
$a^t\equiv 1\pmod n\iff \operatorname{ord}_n(a)\mid t.$

Ordenen deler $\phi(n)$ .
$\operatorname{ord}_n(a)\mid\phi(n).$

Ordenen til en potens.
$\operatorname{ord}_n(a^k)=\frac{\operatorname{ord}_n(a)}{\gcd(k,\operatorname{ord}_n(a))}.$

Den siste er nøkkelen til hele dette kapitlet — både til å generere alle primitive røtter og til å telle elementene av en gitt orden.

Fra videregående kreves ingenting.

Ett tall som treffer alle

Regn ut potensene av $3$ modulo $7$ :
$3^1=3,\quad 3^2=2,\quad 3^3=6,\quad 3^4=4,\quad 3^5=5,\quad 3^6=1.$

Se på listen: $3,2,6,4,5,1$ . Den inneholder hvert av tallene $1,2,3,4,5,6$ — nøyaktig én gang. Én enkelt potensrekke har truffet alle restene modulo $7$ .

Prøver du det samme med $2$ , får du noe annet:
$2^1=2,\quad 2^2=4,\quad 2^3=1,\quad 2^4=2,\dots$
Bare tre verdier, og så gjentar det seg. Syklusen til $2$ er kort; syklusen til $3$ er så lang den kan bli.

Et tall med maksimal syklus kalles en primitiv rot. Med språket fra kap. 5.1: $\operatorname{ord}_7(3)=6=\phi(7)$ , mens $\operatorname{ord}_7(2)=3$ .

Hvorfor det er et sentralt begrep: når en primitiv rot finnes, kan hver rest skrives som en potens av den. Da er multiplikasjon modulo $n$ i praksis addisjon av eksponenter, og alle spørsmål om orden, kvadratiske rester og løsbarhet blir spørsmål om heltall. Det er den samme forenklingen som logaritmer gir for vanlige tall — og eksponenten kalles faktisk en diskret logaritme.

Hva kapitlet svarer på, i rekkefølge: hvordan du verifiserer at et tall er en primitiv rot uten å regne hele syklusen (løkke 2), for hvilke $n$ de i det hele tatt finnes (løkke 3), hvor mange det er og hvordan du finner dem alle (løkke 4), og hvordan du teller elementer av en gitt orden (løkke 5).

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: Definisjonen

~9 minutter.

Begrepet er en setning fra kap. 5.1 med et navn festet på: maksimal orden.

Primitiv rot

a

✏️3 er en primitiv rot modulo 7

Vis at $3$ er en primitiv rot modulo $7$ , og at $2$ ikke er det.

Vilkåret.

\gcd(3,7)=\gcd(2,7)=1

, så begge har en orden.

Taket. $\phi(7)=7-1=6$ , siden $7$ er et primtall. En primitiv rot modulo $7$ må ha orden $6$ .

For $a=3$ : regn hele syklusen.

$k$	$1$	$2$	$3$	$4$	$5$	$6$
$3^k\bmod 7$	$3$	$2$	$6$	$4$	$5$	$1$

Utregningen:

3^2=9\equiv 2

3^3\equiv 2\cdot 3=6

3^4\equiv 6\cdot 3=18\equiv 4

3^5\equiv 4\cdot 3=12\equiv 5

3^6\equiv 5\cdot 3=15\equiv 1

.
Den første

k

med

3^k\equiv 1

k=6

, altså er

\operatorname{ord}_7(3)=6=\phi(7)

. Altså er $3$ en primitiv rot modulo $7$ .

Legg merke til at listen $3,2,6,4,5,1$ inneholder alle de seks ikke-null restene — presis som definisjonens andre formulering sier.

For $a=2$ : $2^1=2$ , $2^2=4$ , $2^3=8\equiv 1$ . Ordenen er $3$ , som deler $6$ men ikke er $6$ . Altså er $2$ ikke en primitiv rot modulo $7$ , og potensene av $2$ treffer bare $\{1,2,4\}$ — halvparten av restene.

Sluttsvar: $\operatorname{ord}_7(3)=6=\phi(7)$ , så $3$ er en primitiv rot; $\operatorname{ord}_7(2)=3\ne 6$ , så $2$ er ikke.

Merk at $\{1,2,4\}$ er nøyaktig de kvadratiske restene modulo $7$ (kap. 4.1). Det er ikke tilfeldig: potensene av et element med orden $\displaystyle \frac{p-1}{2}$ er nøyaktig kvadratene. Vi kommer tilbake til den koblingen i løkke 5.

Merk også arbeidsmengden: seks potenser for å verifisere én primitiv rot. For $p=29$ ville det vært 28 potenser, og det er for mye på eksamen. Primdivisortesten i neste løkke gjør samme jobb med to potenser.

📝Oppgave 1

Vis at $2$ er en primitiv rot modulo $11$ ved å regne hele syklusen, og oppgi hvilke rester potensene treffer.

Løkke 2: Primdivisortesten

~13 minutter.

Å regne hele syklusen er uaktuelt for $p$ over rundt $15$ . Heldigvis finnes en test som bruker én potens per primdivisor av $\phi(n)$ — typisk to eller tre potenser i alt.

— naturlig pausepunkt —

📜Primdivisortesten

\gcd(a,n)=1

og la

q_1,\dots,q_r

være de ulike primdivisorene av

\phi(n)

. Da er

$a\ \text{primitiv rot modulo}\ n\quad\Longleftrightarrow\quad a^{\phi(n)/q_i}\not\equiv 1\pmod n\ \text{for alle}\ i=1,\dots,r.$

Bevis.

Retning $\Rightarrow$ . Er $a$ en primitiv rot, er ordenen $\phi(n)$ , og da kan ingen mindre eksponent gi $1$ . Tallene $\phi(n)/q_i$ er alle mindre enn $\phi(n)$ , så ingen av dem kan gi $1$ .

Retning $\Leftarrow$ (den som gjør arbeidet). Sett $d=\operatorname{ord}_n(a)$ . Vi vet at $d\mid\phi(n)$ . Anta $d<\phi(n)$ — altså at $d$ er en ekte divisor. Da er $\phi(n)/d>1$ , så tallet $\phi(n)/d$ har minst én primdivisor; kall den $q$ . Nå deler $d$ tallet $\phi(n)/q$ :
$\frac{\phi(n)}{q}=d\cdot\frac{\phi(n)}{dq},$
og brøken $\displaystyle \frac{\phi(n)}{dq}$ er et helt tall nettopp fordi $q$ deler $\phi(n)/d$ . Ved ordenslemmaet gir $d\mid\phi(n)/q$ da
$a^{\phi(n)/q}\equiv 1\pmod n,$
i strid med antagelsen. Altså er $d=\phi(n)$ , og $a$ er en primitiv rot. $\blacksquare$

Intuisjonen bak beviset: en ekte divisor av $\phi(n)$ må «mangle» minst én primfaktor, og da ligger den under $\phi(n)/q$ for den primfaktoren. Derfor er det nok å sjekke de $r$ «nesten-maksimale» eksponentene $\phi(n)/q_i$ — de fanger alle mulige ekte divisorer på én gang.

Testen må sitte utenat, og den er hele tidsbesparelsen i sjangeren: for $\phi(n)=28=2^2\cdot 7$ er primdivisorene $2$ og $7$ , så du regner to potenser i stedet for å teste seks divisorer.

Merk hva som ikke virker: å teste bare én primdivisor, eller å teste $\phi(n)/d$ for en sammensatt $d$ . Testen krever alle primdivisorene, og bare dem. Å konkludere «primitiv rot» etter én test er den mest belagte feilen i sjangeren.

Oppskrift: verifiser en primitiv rot

\gcd(a,n)=1

$\phi(n)$	faktorisering	primdivisorer	antall tester
$28$	$2^2\cdot 7$	$2$ , $7$	$2$
$30$	$2\cdot 3\cdot 5$	$2$ , $3$ , $5$	$3$
$36$	$2^2\cdot 3^2$	$2$ , $3$	$2$
$40$	$2^3\cdot 5$	$2$ , $5$	$2$

✏️2 er en primitiv rot modulo 29

Vis at $2$ er en primitiv rot modulo $29$ .

Steg 1: vilkåret.

\gcd(2,29)=1

, siden

29

er primtall.

Steg 2: $\phi(n)$ og faktoriseringen. $\phi(29)=28$ , og
$28=2^2\cdot 7.$

Steg 3: primdivisorene av $28$ er $q=2$ og $q=7$ . Vi skal derfor regne to potenser:
$2^{28/2}=2^{14}\qquad\text{og}\qquad 2^{28/7}=2^{4}.$

Steg 4: regn dem.

Første test, $2^{14}\bmod 29$ . Binærutviklingen er $14=8+4+2$ :

potens	utregning	verdi mod $29$
$2^2$	$4$	$4$
$2^4$	$16$	$16$
$2^8$	$16^2=256=8\cdot 29+24$	$24$

2^{14}=2^8\cdot 2^4\cdot 2^2\equiv 24\cdot 16\cdot 4\pmod{29}.

Steg for steg:

24\cdot 16=384=13\cdot 29+7\equiv 7

, og

7\cdot 4=28\equiv -1\pmod{29}

.
Altså

2^{14}\equiv 28\not\equiv 1

✓ — første test bestått.
Andre test, $2^4\bmod 29$ . Direkte:

2^4=16\not\equiv 1

✓ — andre test bestått.

Steg 5: konklusjon. Begge testverdiene er ulik $1$ , så ved primdivisortesten er
$\operatorname{ord}_{29}(2)=\phi(29)=28,$

og $2$ er en primitiv rot modulo $29$ .

Kontroll. Merk at $2^{14}\equiv -1$ . Det er som forventet: $2^{14}$ er en kvadratrot av $2^{28}\equiv 1$ , og modulo et primtall er kvadratrøttene av $1$ bare $\pm 1$ (kap. 4.1). Siden den ikke er $1$ , må den være $-1$ ✓.

Sluttsvar: $2$ er en primitiv rot modulo $29$ , med orden $28$ .
Tell arbeidet: to potensberegninger, den ene triviell. En full ordensberegning ville krevd seks tester (divisorene $1,2,4,7,14,28$ ), og en full syklus 28 potenser. Det er derfor primdivisortesten er den ene tingen å kunne i denne sjangeren.
Om føringen: at faktoriseringen av $\phi(n)$ står skrevet, er en del av besvarelsen — det er den som forklarer hvorfor nettopp $14$ og $4$ er de riktige eksponentene. Instruksen på hvert eksamenssett er at alle svar skal begrunnes, og her er faktoriseringen begrunnelsen for testens form.

📝Oppgave 2

a) Vis med primdivisortesten at

2

er en primitiv rot modulo

13

.
b) Vis at

3

ikke er en primitiv rot modulo

13

, og finn ordenen til

3

📝Oppgave 3

Avgjør om $5$ er en primitiv rot modulo $23$ .

Løkke 3: For hvilke n finnes de?

~10 minutter.

Primitive røtter finnes ikke modulo alle $n$ — og det er en del av pensum å vite for hvilke. Kriteriet er kort, og det skal sitte utenat.

Eksistenskriteriet

n

Hvordan kriteriet brukes

n

$n$	faktorisering	primitiv rot?	grunn
$13$	primtall	ja	$n=p$
$14$	$2\cdot 7$	ja	$n=2p$
$15$	$3\cdot 5$	nei	to ulike odde primtall
$16$	$2^4$	nei	toerpotens $>4$
$18$	$2\cdot 3^2$	ja	$n=2p^2$
$20$	$2^2\cdot 5$	nei	$4\mid n$ og odde primfaktor
$25$	$5^2$	ja	$n=p^2$
$27$	$3^3$	ja	$n=p^3$
$2$ , $4$	—	ja	egne tilfeller

📝Oppgave 4

Avgjør for hver av modulusene $n=14$ , $15$ , $16$ , $18$ og $27$ om det finnes en primitiv rot. Begrunn med eksistenskriteriet.

Løkke 4: Hvor mange, og hvordan finne dem alle

~12 minutter.

Har du én primitiv rot, har du dem alle — og du kan telle dem uten å regne en eneste potens til. Begge resultatene følger av potensformelen fra kap. 5.1.

— naturlig pausepunkt —

📜Alle primitive røtter, og hvor mange

r

være en primitiv rot modulo

n

. Da gjelder:

(i) Elementet $r^k$ er en primitiv rot modulo $n$ nøyaktig når $\gcd(k,\phi(n))=1$ .

(ii) Antallet primitive røtter modulo $n$ er $\phi(\phi(n))$ .

Bevis av (i) — én linje, ut av potensformelen. Fra kap. 5.1 er
$\operatorname{ord}_n(r^k)=\frac{\operatorname{ord}_n(r)}{\gcd(k,\operatorname{ord}_n(r))}=\frac{\phi(n)}{\gcd(k,\phi(n))},$
og dette er $\phi(n)$ nøyaktig når $\gcd(k,\phi(n))=1$ . $\blacksquare$

Bevis av (ii) — også kort. Siden $r$ er en primitiv rot, løper $r^1,r^2,\dots,r^{\phi(n)}$ gjennom alle restene som er relativt primiske til $n$ , hver nøyaktig én gang. Etter (i) er de primitive røttene blant dem nøyaktig de med $\gcd(k,\phi(n))=1$ , og antallet slike $k$ i $\{1,\dots,\phi(n)\}$ er per definisjon
$\phi(\phi(n)).\qquad\blacksquare$

Begge resultatene må sitte utenat — særlig antallet $\phi(\phi(n))$ , som er et vanlig delspørsmål. Men merk at utledningen er så kort at du kan gjenskape dem om de glipper: potensformelen pluss definisjonen av $\phi$ .

Praktisk bruk, i tre steg:

1. Finn én primitiv rot $r$ (primdivisortesten, med prøving fra $2$ oppover).
2. Antallet er $\phi(\phi(n))$ — og det svaret krever ingen videre regning.
3. Vil oppgaven ha dem alle, regn $r^k\bmod n$ for hver $k$ med $\gcd(k,\phi(n))=1$ .

Merk asymmetrien: å telle dem er gratis; å liste dem koster én potensberegning per rot. På eksamen er $n$ da lite, eller oppgaven ber bare om noen få.

Antallet primitive røtter

\#\{\text{primitive røtter modulo } n\}=\phi(\phi(n)),

$p$	$\phi(p)=p-1$	$\phi(p-1)$	antall primitive røtter
$11$	$10=2\cdot 5$	$4$	$4$
$13$	$12=2^2\cdot 3$	$4$	$4$
$23$	$22=2\cdot 11$	$10$	$10$
$29$	$28=2^2\cdot 7$	$12$	$12$
$31$	$30=2\cdot 3\cdot 5$	$8$	$8$
$41$	$40=2^3\cdot 5$	$16$	$16$

✏️Alle primitive røtter modulo 11

a) Hvor mange primitive røtter finnes modulo

11

?
b) Finn dem alle, gitt at

2

er en primitiv rot (vist i oppgave 1).

a) Antallet er

\phi(\phi(11))=\phi(10)

. Og

10=2\cdot 5

, så

\phi(10)=\phi(2)\phi(5)=1\cdot 4=4

ved multiplikativiteten (kap. 2.1).

Det finnes altså $4$ primitive røtter modulo $11$ . Merk at det er $4$ av $10$ rester — en betydelig andel.

b) Etter teoremet er de primitive røttene nøyaktig $2^k$ med $\gcd(k,\phi(11))=\gcd(k,10)=1$ .

De $k$ -ene i $\{1,\dots,10\}$ med $\gcd(k,10)=1$ er
$k=1,\ 3,\ 7,\ 9$
— fire stykker ✓, som stemmer med a).

Regn potensene (verdiene er hentet fra syklustabellen i oppgave 1):
$2^1=2,\qquad 2^3=8,\qquad 2^7\equiv 7,\qquad 2^9\equiv 6\pmod{11}.$

De primitive røttene modulo $11$ er derfor
$\{2,\ 6,\ 7,\ 8\}.$

Kontroll av én av dem, $a=6$ : $\phi(11)=10=2\cdot 5$ , primdivisorene er $2$ og $5$ . Første test: $6^5\bmod 11$ . Vi har $6^2=36\equiv 3$ , $6^4\equiv 9$ , så $6^5\equiv 9\cdot 6=54=4\cdot 11+10\equiv 10\equiv -1\ne 1$ ✓. Andre test: $6^2\equiv 3\ne 1$ ✓. Altså er $6$ en primitiv rot ✓.

Kontroll av at de andre restene ikke er det: de seks resterende restene $3,4,5,9,10$ og $1$ må da ha orden mindre enn $10$ . Rask sjekk på $3$ : $3^5=243=22\cdot 11+1\equiv 1$ , så $\operatorname{ord}_{11}(3)=5\ne 10$ ✓ — ikke primitiv rot, som forventet.

Sluttsvar: a) $4$ primitive røtter; b) de er $2$ , $6$ , $7$ og $8$ .

Legg merke til hvor lite arbeid b) krevde når a) var på plass: fire eksponenter å plukke ut og fire potenser å lese av. Hele jobben er å finne den første primitive roten — resten er bokføring.

📝Oppgave 5

Det er oppgitt at $6$ er en primitiv rot modulo $41$ .

a) Verifiser det med primdivisortesten.
b) Hvor mange primitive røtter finnes modulo $41$ ?
c) Er $6^{10}$ en primitiv rot modulo $41$ ? Begrunn uten å regne potensen.

Løkke 5: Elementer av gitt orden

~11 minutter.

Den siste — og den som oftest er delpunkt b) på eksamen: «finn de to elementene av orden $4$ », «hvor mange har orden $5$ ?». Alt følger av samme potensformel.

📜Antall elementer av gitt orden

n

være en modulus som har en primitiv rot

r

, og la

d

være en divisor av

\phi(n)

. Da finnes det nøyaktig

$\phi(d)$

elementer av orden $d$ modulo $n$ , og de er
$r^{k\cdot\phi(n)/d}\quad\text{for de } k \text{ med } 1\le k\le d\ \text{og}\ \gcd(k,d)=1.$

Bevis. Hvert element som er relativt primisk til $n$ , kan skrives $r^m$ for en entydig $m$ med $1\le m\le\phi(n)$ (siden $r$ er en primitiv rot). Ved potensformelen fra kap. 5.1 er
$\operatorname{ord}_n(r^m)=\frac{\phi(n)}{\gcd(m,\phi(n))},$
og dette er lik $d$ nøyaktig når $\gcd(m,\phi(n))=\phi(n)/d$ . Skriv $\displaystyle m=\frac{\phi(n)}{d}\cdot k$ ; betingelsen blir da $\gcd(k,d)=1$ med $1\le k\le d$ . Antallet slike $k$ er $\phi(d)$ . $\blacksquare$

Kontrollen som alltid gjelder — og som er en fin identitet i seg selv: summerer du over alle divisorer av $\phi(n)$ , skal du få alle elementene:
$\sum_{d\mid\phi(n)}\phi(d)=\phi(n).$

Eksempel på hele fordelingen, $p=19$ med $\phi(19)=18$ :

$d$	$1$	$2$	$3$	$6$	$9$	$18$
antall $=\phi(d)$	$1$	$1$	$2$	$2$	$6$	$6$

Summen er

1+1+2+2+6+6=18=\phi(19)

✓. De seks elementene av orden

18

er de primitive røttene, og

\phi(18)=6

✓ stemmer med formelen fra løkke 4.
Formelen må sitte utenat (

\phi(d)

stykker), og konstruksjonen utledes på stedet fra potensformelen når du trenger den.

Merk vilkåret: resultatet krever at en primitiv rot finnes. Modulo $15$ , som ikke har noen, holder det ikke — der har fire elementer orden $4$ , mens $\phi(4)=2$ .

Å lage et element av gitt orden

r

Primitive røtter er aldri kvadratiske rester

p

✏️Eksamensnivå: primitiv rot, telling og elementer av gitt orden

La $p=29$ , og bruk at $2$ er en primitiv rot modulo $29$ (eksempel 2).

a) Hvor mange primitive røtter finnes modulo $29$ ?
b) Hvor mange elementer har orden $7$ , og hvor mange har orden $4$ ?
c) Finn de to elementene av orden $4$ .
d) Kontrollér tellingen ved å summere over alle divisorer av $\phi(29)$ .

a) Antallet primitive røtter er

\phi(\phi(29))=\phi(28).

Faktoriseringen er

28=2^2\cdot 7

, så ved multiplikativiteten

\phi(28)=\phi(4)\phi(7)=2\cdot 6=12.

Det finnes $12$ primitive røtter modulo $29$ , av $28$ rester i alt.

b) Etter tellingsteoremet er antall elementer av orden $d$ lik $\phi(d)$ , for hver $d$ som deler $\phi(29)=28$ .

- Orden $7$ : $\phi(7)=6$ elementer.
- Orden $4$ : $\phi(4)=2$ elementer.

c) Vi lager et element av orden $4$ som $r^{\phi(n)/d}$ med $r=2$ og $d=4$ :
$2^{28/4}=2^7.$
Regningen: $2^7=128=4\cdot 29+12$ , altså $2^7\equiv 12\pmod{29}$ .

Kontroll av ordenen: $12^2=144=5\cdot 29-1$ , så $12^2\equiv -1\pmod{29}$ , og dermed $12^4\equiv(-1)^2=1$ . Ordenen er $4$ (ikke $1$ eller $2$ , siden $12\not\equiv 1$ og $12^2\equiv -1\not\equiv 1$ ) ✓.

Det andre elementet er $12^k$ med $\gcd(k,4)=1$ , altså $k=3$ :
$12^3=12^2\cdot 12\equiv(-1)\cdot 12=-12\equiv 29-12=17\pmod{29}.$

Kontroll: $17\equiv -12$ , så $17^2\equiv 144\equiv -1$ og $17^4\equiv 1$ ✓. Ordenen er $4$ .

De to elementene av orden $4$ modulo $29$ er $12$ og $17$ , og det er $\phi(4)=2$ stykker ✓.

d) Divisorene av $28$ er $1,2,4,7,14,28$ . Antall elementer av hver orden:

$d$	$1$	$2$	$4$	$7$	$14$	$28$
$\phi(d)$	$1$	$1$	$2$	$6$	$6$	$12$

Summen er

1+1+2+6+6+12=28=\phi(29)\ \checkmark

Hvert av de $28$ elementene har nøyaktig én orden, og summen bekrefter at tellingen er komplett.
Sluttsvar: a) $12$ ; b) $6$ av orden $7$ og $2$ av orden $4$ ; c) $12$ og $17$ ; d) summen av $\phi(d)$ over divisorene av $28$ er $28$ ✓.

Om føringen, som er det som gir uttelling her: (1) hvert antall er begrunnet med formelen $\phi(d)$ , ikke bare oppgitt. (2) Elementene i c) er kontrollert ved å kvadrere — det er gratis og fanger regnefeil. (3) Summeringskontrollen i d) er en fullstendighetssjekk som en sensor ser etter: den viser at du forstår at ordenene partisjonerer alle restene. Instruksen på hvert eksamenssett er at alle svar skal begrunnes, og i denne sjangeren betyr det formelen bak hvert tall.

📝Oppgave 6

Det er oppgitt at $6$ er en primitiv rot modulo $41$ (se oppgave 5).

a) Hvor mange elementer har orden $5$ modulo $41$ ?
b) Finn dem alle.

📝Oppgave 7

a) Sett opp hele ordensfordelingen modulo

19

: for hver divisor

d

\phi(19)=18

, hvor mange elementer har orden

d

?
b) Kontrollér at summen er

18

.
c) Hvor mange primitive røtter finnes modulo

19

📝Oppgave 8

La $p$ være et odde primtall.

a) Vis at en primitiv rot modulo $p$ aldri er en kvadratisk rest modulo $p$ .
b) Er det motsatte sant — er hver kvadratisk ikke-rest en primitiv rot? Gi et moteksempel om ikke.
c) Hvor mange av de $p-1$ restene er kandidater til å være primitiv rot etter at kvadratiske rester er utelukket, og hvor mange primitive røtter er det faktisk for $p=13$ ?

📝Oppgave 9

a) Finn den minste primitive roten modulo

31

ved å prøve kandidater fra

2

oppover, med kvadratiske rester utelukket først.
b) Hvor mange primitive røtter finnes modulo

31

Typiske feil

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

- Konkluderer «primitiv rot» uten å teste alle primdivisorene. Dette er den best belagte feilen i sjangeren. Å vise at $a^{\phi(n)/2}\not\equiv 1$ er ikke nok — du må gjøre det for hver primdivisor av $\phi(n)$ . Motmiddelet: faktoriser $\phi(n)$ eksplisitt og skriv opp listen over eksponenter $\phi(n)/q$ før du regner. Da ser du hvor mange tester du skal ha.

- Feil eksistensbetingelse. Primitive røtter finnes bare for $n=2$ , $4$ , $p^k$ og $2p^k$ . De to fellene er toerpotenser over $4$ ( $8$ , $16$ , $32$ har ingen) og $4p$ -formen ( $20=4\cdot 5$ har ingen). Sjekk formen på $n$ først — det er bortkastet arbeid å lete etter noe som ikke finnes.

- Svarer $\phi(n)$ i stedet for $\phi(\phi(n))$ . Antall primitive røtter modulo $29$ er $\phi(28)=12$ , ikke $28$ . Tallet $\phi(n)$ er antall rester, ikke antall primitive røtter.

- Teller elementer av gitt orden feil. Antallet er $\phi(d)$ , ikke $d$ . Modulo $29$ har $\phi(7)=6$ elementer orden $7$ — ikke $7$ . Kontrollen: summér $\phi(d)$ over alle divisorer av $\phi(n)$ ; du skal få $\phi(n)$ eksakt.

- Bruker tellingsformelen uten at en primitiv rot finnes. Formelen « $\phi(d)$ elementer av orden $d$ » krever at $n$ har en primitiv rot. Modulo $15$ har fire elementer orden $4$ , mens $\phi(4)=2$ — formelen gjelder ikke der.

Og en regnefeil-felle som er lett å gå i: i primdivisortesten er eksponentene $\phi(n)/q$ , ikke $\phi(n)-q$ eller $q$ selv. For $\phi(n)=28$ og $q=7$ er eksponenten $4$ , ikke $7$ og ikke $21$ . Skriv brøken opp før du regner.

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 tabell over primitive røtter å slå opp i, og eksistenskriteriet er nettopp den typen liste man ellers ville sett opp.

Merk hvordan kortene fordeler seg: to av dem må pugges kaldt (eksistenskriteriet og primdivisortesten), og resten utledes fra potensformelen i kap. 5.1. Det er en billig del av pensum å beherske — hvis du kjenner den ene formelen.

Slik pugges de: faktakortene ved aktiv gjenkalling, testen ved å kjøres på nye tall. Verifiser tre nye primitive røtter med lukket bok, og du er ferdig med sjangeren.

«Generator» og diskret logaritme

n

Å finne en primitiv rot

n

Kort: antall elementer av gitt orden

\#\{a: \operatorname{ord}_n(a)=d\}=\phi(d),\qquad\text{for hver } d\mid\phi(n),

Kort: verifikasjonstesten på 30 sekunder

\phi(n)

$n$	$\phi(n)$	eksponenter å teste
$13$	$12=2^2\cdot 3$	$6$ , $4$
$23$	$22=2\cdot 11$	$11$ , $2$
$29$	$28=2^2\cdot 7$	$14$ , $4$
$31$	$30=2\cdot 3\cdot 5$	$15$ , $10$ , $6$
$41$	$40=2^3\cdot 5$	$20$ , $8$

Kort: eksistenskriteriet

n=2,\quad n=4,\quad n=p^k,\quad n=2p^k\qquad (p\ \text{odde primtall}).

Kort: generer alle primitive røtter

r

Kort: gratis utelukkelse via Legendre

p

$p\bmod 8$	$\displaystyle \left(\frac 2p\right)$	kan $2$ være primitiv rot?
$1$ eller $7$	$1$	nei
$3$ eller $5$	$-1$	ja, må testes

Kort: strukturen i restene

n

Kort: tidsbudsjettet

a

Oppgavetype	Tid
«Vis at $a$ er primitiv rot» (2–3 tester)	~6 min
«Hvor mange primitive røtter?»	~2 min
«Finn alle primitive røtter» (liten $n$ )	~8 min
«Hvor mange har orden $d$ ?»	~2 min
«Finn elementene av orden $d$ »	~6 min
«Finn den minste primitive roten»	~10 min

Kort: innpakningene i arkivet

a

Kort: selvdiagnose for primitive røtter

n

Kort: hvorfor ALLE primdivisorene må testes

13

Primitive røtter modulo en primtallspotens

n=p^k

$p$	$r$	$\operatorname{ord}_p(r)$	$\operatorname{ord}_{p^2}(r)$	$\phi(p^2)$
$3$	$2$	$2$	$6$	$6$ ✓
$5$	$2$	$4$	$20$	$20$ ✓
$7$	$3$	$6$	$42$	$42$ ✓
$11$	$2$	$10$	$110$	$110$ ✓

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.