8.2 Øvingseksamen 1: de fem søylene (bred kjerne)

Forkunnskaper

Settet dekker de fem søylene i faget, og forutsetter Del 1–6:

- O1: kap. 1.2 (Euklids algoritme og Bézout) og kap. 1.3 (diofantiske likninger).
- O2: kap. 2.1 (Eulers $\phi$ og Eulers teorem), kap. 2.3 (Wilsons teorem) og kap. 2.5 (den sammensatte restberegningen).
- O3: kap. 2.4 (det kinesiske restteoremet), med kap. 1.4 for forenklingen av hver kongruens.
- O4: kap. 3.1 (RSA fra ende til ende).
- O5: kap. 4.1 (Legendre-symbolet) og kap. 4.2 (resiprositet og supplementsreglene).
- O6: kap. 5.1 (orden og ordenslemmaet).
- O7: kap. 6.2 (induksjon), med kap. 6.1 for paritetsargumentet i steget.

Føringsstandarden som fasitene under er skrevet etter, står i kap. 8.1. Har du ikke lest den, les den først: den er forskjellen mellom å regne riktig og å få uttelling for det.

Er du usikker på om du er klar? Ta temaprøvene i Del 1–Del 6 først. Øvingseksamenene er ment som siste trening, ikke som første møte med sjangrene.

Oppgavesettet

Alle svar skal begrunnes. Det er instruksen på hvert eksamenssett i arkivet, og den gjelder her: et riktig sluttall uten metode teller lite.

Klokka starter nå.

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

a) Bruk Euklids algoritme til å finne $\gcd(2613,767)$, og skriv gcd-en på formen $2613x+767y$.

Avgjør deretter om likningen
$$2613x+767y=91$$
har heltallsløsninger. Har den det, finn samtlige heltallsløsninger, og oppgi den løsningen der $x$ er det minste positive tallet.

b) La $n$ være et helt tall.

Vis at $\gcd(6n+5,\,4n+3)=1$ for alle hele tall $n$, og finn samtlige heltallsløsninger av
$$(6n+5)x+(4n+3)y=1,$$
uttrykt ved $n$.

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

a) Finn resten når $7\cdot 84!$ deles på $89$.

b) Finn resten når $19^{505}$ deles på $132$.

Oppgave 3 (10 poeng)

Finn samtlige hele tall $x$ som oppfyller alle tre kongruensene
$$3x\equiv 5\pmod 8,\qquad x\equiv 4\pmod{11},\qquad 2x\equiv 3\pmod{15},$$
og oppgi det minste positive slike tallet.

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

Den offentlige nøkkelen i et RSA-system er $(n,e)=(451,29)$, og du har fanget opp den krypterte meldingen $c=15$.

a) Faktoriser $n$, regn ut $\phi(n)$, og finn dekrypteringseksponenten $d$.

b) Dekrypter meldingen. Før potensen med kvadrer-og-multipliser, og kontrollér svaret på en uavhengig måte.

— naturlig pausepunkt —

Oppgave 5 (10 poeng)

Avgjør om kongruensen
$$x^2\equiv 42\pmod{109}$$
har løsninger, og oppgi antall løsninger. Før reduksjonen med navn på regelen som brukes i hvert steg.

Oppgave 6 (10 poeng)

a) Finn $\operatorname{ord}_{47}(2)$, og begrunn at svaret er den minste eksponenten.

b) Bruk svaret til å finne resten når $2^{500}$ deles på $47$.

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

Oppgave 7 (10 poeng)

Vis ved induksjon at
$$6\mid n^3+5n$$
for alle hele tall $n\ge 1$.

Skriv basissteg, induksjonshypotese og induksjonssteg som tre merkede deler, og marker stedet der hypotesen brukes.

Poengoversikt og selvdiagnose

Selvdiagnose

- ☐ Jeg skrev binærutviklingen og kvadrattabellen i O2b og O4b, ikke bare sluttallet.

- ☐ Jeg oppgav antall løsninger i O5, ikke bare symbolets verdi.

- ☐ Jeg begrunnet i O6 at ordenen er den minste eksponenten.

- ☐ Jeg merket alle tre induksjonsstegene i O7 og skrev «her bruker vi induksjonshypotesen».

Kontroller:
- ☐ Jeg satte Bézout-koeffisientene inn og fikk $\gcd$-en tilbake.
- ☐ Jeg satte CRT-svaret inn i alle tre kongruensene i O3.
- ☐ Jeg kontrollerte $d$ i O4a ved å regne $ed\bmod\phi(n)$.
- ☐ Jeg kontrollerte $m$ i O4b ved å kryptere tilbake (eller via $p$ og $q$).
- ☐ Jeg sjekket at hvert sluttsvar ligger mellom $0$ og modulusen minus én.
Tid:
- ☐ Jeg brukte de første fem minuttene på å lese hele settet og skrive sjangeren i margen.
- ☐ Jeg tok de delpunktene jeg var sikrest på, først.

- ☐ Jeg satte av de siste tjue minuttene til kontroll, ikke til et nytt delpunkt.

- ☐ Ingen enkeltoppgave spiste mer enn 35 minutter.
Hvis noe skar seg:
- ☐ Ble O1b vanskelig? Grepet er å gange opp til samme koeffisient foran $n$ og ta differansen — ikke å kjøre Euklids algoritme på uttrykk. Se kap. 1.3 løkke 5.
- ☐ Kom O2a ut med feil fortegn? Tell de manglende faktorene: fire er et partall, så koeffisienten er positiv. Se kap. 2.3.
- ☐ Ble kvadrattabellen i O2b lengre enn fem rader? Da har du sannsynligvis glemt eksponentreduksjonen, eller regnet den modulo $132$ i stedet for modulo $\phi(132)=40$.

- ☐ Fikk du bare én løsning i O3? Svaret er en restklasse med periode $1320$ — ett tall er ikke hele svaret.

- ☐ Falt O4b sammen med O4a? Feil $d$ gir feil melding. Kontroller $d$ før du starter dekrypteringen — det tar femten sekunder og sparer tjue minutter.
- ☐ Ble O5 gjettet? Skriv fortegnsfaktoren ut som en paritetsberegning. Er du usikker, kjør Eulers kriterium som kontroll.
- ☐ Manglet O7 basissteget? Da er beviset tomt, ikke bare mangelfullt — se kontrastparet i kap. 8.1 løkke 4.
Neste steg: står mer enn tre punkt åpne under «Føring», er det kap. 8.1 du skal lese om igjen — ikke fagkapitlene. Står de under «Kontroller», ta Øvingseksamen 2 med sjekklisten liggende ved siden av deg (denne ene gangen), og så Øvingseksamen 3 uten.