8.3 Øvingseksamen 2: karakterskillerne og den sammensatte fakultetsoppgaven

Forkunnskaper

- O1: kap. 1.4 (lineær kongruens, forkorting, modulær invers), med kap. 1.2 for inversen.
- O2: kap. 2.1 (Euler), kap. 2.3 (Wilson) og kap. 2.5 (splittemetoden når $\gcd(a,n)\ne 1$).
- O3: kap. 2.4 løkke 5 (moduler med felles faktor).
- O4: kap. 3.1 (nøkkelgenerering og korrekthetsbeviset).
- O5: kap. 4.2 (resiprositetsloven og supplementsreglene).
- O6: kap. 5.2 (primdivisortesten, antall primitive røtter, elementer av gitt orden).
- O7: kap. 5.3 ($\tau$, $\sigma$ og minste $n$ med gitt $\tau$).
- O8: kap. 6.1 (case-analyse) og kap. 6.2 (induksjonsmalen).

Sist du var her — de to resultatene dette settet lener seg tyngst på:

- Forkorting av en kongruens deler også modulusen. Er $d=\gcd(a,m)$ og $d\mid b$, er $ax\equiv b\pmod m$ ekvivalent med $\displaystyle \frac ad x\equiv\frac bd\ \left(\text{mod }\frac md\right)$, og den opprinnelige kongruensen har $d$ inkongruente løsninger modulo $m$, med avstand $m/d$ (kap. 1.4).
- Primdivisortesten. $a$ er en primitiv rot modulo $n$ nøyaktig når $a^{\phi(n)/q}\not\equiv 1\pmod n$ for hver primdivisor $q$ i $\phi(n)$ — én test per primdivisor, ikke per divisor (kap. 5.2).

Føringsstandarden står i kap. 8.1.

Oppgavesettet

Alle svar skal begrunnes.

Klokka starter nå.

Oppgave 1 (10 poeng)

Løs kongruensen
$$92x\equiv 68\pmod{120}.$$

Kommentér løsbarheten og antall løsninger før du løser, og oppgi alle inkongruente løsninger modulo $120$.

Oppgave 2 (20 poeng — a og b, 10 poeng hver)

a) Finn resten når $4\cdot 55!$ deles på $61$.

b) Finn resten når $18^{307}$ deles på $250$.

I b): begrunn spesielt hvorfor Eulers teorem ikke kan brukes direkte på modulus $250$.

Oppgave 3 (10 poeng)

a) Avgjør om systemet
$$x\equiv 7\pmod{18},\qquad x\equiv 13\pmod{24}$$
har løsninger. Begrunn svaret.

b) Har det løsninger, finn dem alle, og oppgi det minste positive tallet i løsningsmengden.

(Delpunktene a og b utgjør til sammen ett av settets ti likt vektede delpunkt.)

Oppgave 4 (20 poeng — a og b, 10 poeng hver)

Et RSA-system skal bygges med $p=17$, $q=41$ og krypteringseksponent $e=33$.

a) Finn $n$ og $\phi(n)$, bekreft at $e$ er et lovlig valg, og finn dekrypteringseksponenten $d$. Krypter deretter meldingen $m=20$.

b) Vis at dekrypteringen alltid gjenoppretter meldingen, altså at
$$(m^e)^d\equiv m\pmod n$$
for alle meldinger $m$ med $0\le m<n$ — også de der ett av primtallene deler $m$.

— naturlig pausepunkt —

Oppgave 5 (10 poeng)

Avgjør om kongruensen
$$x^2\equiv -22\pmod{131}$$
har løsninger, og oppgi antall løsninger.

Før hele reduksjonen med navn på regelen som brukes i hvert steg, og skriv fortegnsfaktoren ut som en paritetsberegning der resiprositetsloven brukes.

Oppgave 6 (10 poeng)

a) Vis at $2$ er en primitiv rot modulo $61$.

b) Hvor mange primitive røtter finnes modulo $61$, og hvor mange elementer har orden $20$? Oppgi ett konkret element av orden $20$, og begrunn ordenen.

(Delpunktene a og b utgjør til sammen ett av settets ti likt vektede delpunkt.)

Oppgave 7 (10 poeng)

a) Regn ut $\tau(1350)$ og $\sigma(1350)$.

b) Finn det minste positive heltallet $n$ med nøyaktig $24$ divisorer, og begrunn at ingen mindre $n$ har det.

(Delpunktene a og b utgjør til sammen ett av settets ti likt vektede delpunkt.)

Oppgave 8 (10 poeng)

a) (Lemma.) Vis at $k(k+1)$ er et partall for alle hele tall $k$.

b) Vis ved induksjon at
$$6\mid n^3+11n$$
for alle hele tall $n\ge 1$, og bruk lemmaet fra a) eksplisitt i induksjonssteget.

(Delpunktene a og b utgjør til sammen ett av settets ti likt vektede delpunkt.)

Poengoversikt og selvdiagnose

Selvdiagnose

- ☐ Jeg testet i O6 alle tre primdivisorene av $60$, og bare dem.

- ☐ Jeg listet i O7 alle eksponentmønstre, og begrunnet at ingen mindre $n$ virker.

- ☐ Jeg skrev basissteget i O8b, og merket stedet der både hypotesen og lemmaet brukes.

Kontroller:
- ☐ Jeg satte alle fire løsningene i O1 inn i den opprinnelige kongruensen.
- ☐ Jeg kontrollerte O2a ved å gange svaret tilbake med koeffisienten.
- ☐ Jeg sjekket O3-svaret i begge kongruensene, og at neste løsning ($61+72$) også passer.
- ☐ Jeg kontrollerte krypteringen i O4a ved å dekryptere tilbake.
- ☐ Jeg telte fortegnsbidragene i O5 og fikk samme svar på nytt.
- ☐ Jeg kontrollerte tellingen i O6 ved å summere $\phi(d)$ over divisorene av $60$ til $60$.
- ☐ Jeg regnet $\tau$ av svaret i O7 for å bekrefte at det er $24$.
Tid:
- ☐ Jeg tok O1, O3 og O7 tidlig — de tre billigste delpunktene i settet.

- ☐ O2 og O4 fikk ikke mer enn 45 minutter hver.

- ☐ Jeg satte av de siste 25 minuttene til kontroll.
Hvis noe skar seg:
- ☐ Fikk du bare én løsning i O1? Da forkortet du sannsynligvis uten å dele modulusen. Se kap. 1.4 løkke 4.
- ☐ Fikk du positiv koeffisient i O2a? Tell faktorene: fem er odde, så koeffisienten er negativ.
- ☐ Brukte du Euler direkte på $250$ i O2b? Da er svaret galt uansett hva regningen ga. $\gcd$-sjekken kommer først.
- ☐ Ble perioden i O3 lik $432$? Den skal være $\operatorname{lcm}=72$ — se kap. 2.4 løkke 5.
- ☐ Stoppet O4b etter tilfellet $\gcd(m,n)=1$? Da er beviset halvt: RSA-korrektheten krever to tilfeller.

- ☐ Testet du alle divisorene av $60$ i O6? Bare primdivisorene $2,3,5$ trengs — tre tester, ikke elleve.

- ☐ Glemte du basissteget i O8b? Se midtnivåbesvarelsen over: det er nøyaktig den feilen den gjør, og den koster hele delpunktet.
Neste steg: går det tungt i O2b, O4b eller O8, er det de tre stedene i settet der føringen alene bærer delpunktet. Les kap. 8.1 løkke 1 og 4 på nytt, og ta så Øvingseksamen 3 — det bredeste av de tre settene, og det eneste med spesialtema.