8.4 Øvingseksamen 3: bredt sett med roterende spesialtema

Forkunnskaper

- O1: kap. 1.2 og kap. 1.3 (Euklid, Bézout, løsninger i et intervall).
- O2: kap. 2.2 (Fermat), kap. 2.3 (Wilson) og kap. 2.5 (uttrykk med to ledd).
- O3: kap. 2.4 (CRT-formelen og suksessiv innsetting).
- O4: kap. 3.1 (RSA).
- O5: kap. 4.1–kap. 4.2 (Legendre og resiprositet).
- O6: kap. 6.3 (arketype 4: uendelig mange primtall av en gitt form), med kap. 6.1 (motsigelse og case-analyse).
- O7: kap. 6.2 løkke 4 (ulikheter og riktig startverdi).
- O8: kap. 7.1 (kjedebrøk, konvergenter og Pells likning). Vil du trene den andre spesialtema-varianten, står den som alternativ O8 i fasiten, med kap. 7.2 som grunnlag.

Sist du var her — de tre resultatene spesialtemaet hviler på, ferdig oppfrisket:

- Kjedebrøkutviklingen av $\sqrt D$ finnes med hjelpetabellen for $m$, $d$ og $a$: $m_{k+1}=d_ka_k-m_k$, $d_{k+1}=\dfrac{D-m_{k+1}^2}{d_k}$, $a_{k+1}=\left\lfloor\dfrac{a_0+m_{k+1}}{d_{k+1}}\right\rfloor$, og perioden lukkes når $a_k=2a_0$ (kap. 7.1).
- Konvergentene følger $p_n=a_np_{n-1}+p_{n-2}$ og $q_n=a_nq_{n-1}+q_{n-2}$, med $p_{-1}=1$, $p_{-2}=0$, $q_{-1}=0$, $q_{-2}=1$.
- Pells likning $x^2-Dy^2=1$: den minste ikke-trivielle løsningen er en konvergent — regn $p_n^2-Dq_n^2$ rad for rad til du treffer $1$.

Oppgavesettet

Alle svar skal begrunnes.

Klokka starter nå.

Oppgave 1 (10 poeng)

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

Avgjør deretter om likningen
$$1235x+437y=152$$
har heltallsløsninger. Har den det, finn samtlige heltallsløsninger, og oppgi alle løsninger der $0\le x\le 100$.

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

La $p=43$.

a) Finn resten når $3\cdot 40!$ deles på $43$.

b) Finn resten når $5^{200}$ deles på $43$, og bruk svarene til å finne resten når
$$3\cdot 40!+5^{200}$$
deles på $43$.

Oppgave 3 (10 poeng)

Finn samtlige hele tall $x$ som oppfyller
$$x\equiv 5\pmod 9,\qquad 4x\equiv 3\pmod{13},\qquad x\equiv 6\pmod{16},$$
og oppgi det minste positive slike tallet.

Oppgave 4 (10 poeng)

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

Finn dekrypteringseksponenten $d$, og dekrypter meldingen.

Oppgave 5 (10 poeng)

Avgjør om kongruensen
$$x^2\equiv 55\pmod{139}$$
har løsninger, og oppgi antall løsninger. Før reduksjonen med regelnavn ved hvert steg.

Oppgave 6 (10 poeng)

Vis at det finnes uendelig mange primtall $p$ med
$$p\equiv 5\pmod 6.$$

(Hint: anta at det bare finnes endelig mange, og se på et tall av formen $6p_1p_2\cdots p_r-1$.)

Oppgave 7 (10 poeng)

a) Finn den minste $n_0$ slik at
$$2^n>n^3$$
for alle $n\ge n_0$.

b) Bevis påstanden ved induksjon.

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

Oppgave 8 (20 poeng — a og b, 10 poeng hver) · roterende spesialtema

a) Finn kjedebrøkutviklingen til $\sqrt{18}$, og regn ut konvergentene $C_0$ til $C_3$. Vis hjelpetabellen, og si hvor perioden lukker seg.

b) Finn den minste ikke-trivielle løsningen av Pells likning
$$x^2-18y^2=1,$$
kontrollér den ved innsetting, og finn den neste løsningen.

— naturlig pausepunkt —

Poengoversikt og selvdiagnose

Selvdiagnose

- ☐ Jeg gjorde utelukkelsen av restene modulo $6$ uttømmende i O6, og avsluttet med en klar umulighet ($q\mid 1$).

- ☐ Jeg fant $n_0$ i O7a med en tabell, i stedet for å anta den — og jeg beviste restulikheten i O7b.

- ☐ Jeg viste hjelpetabellen i O8a og kontrollerte at siste ledd i perioden er $2a_0$.

- ☐ Jeg kontrollerte begge Pell-løsningene i O8b ved innsetting.
Kontroller:
- ☐ Jeg satte Bézout-koeffisientene inn i O1 og fikk $19$ tilbake.
- ☐ Jeg kontrollerte O2a ved å gange svaret tilbake med koeffisienten $2$.
- ☐ Jeg satte O3-svaret inn i alle tre kongruensene, i deres opprinnelige form.
- ☐ Jeg krypterte tilbake i O4 (gjerne via $p$ og $q$).
- ☐ Jeg telte fortegnsbyttene i O5 og fikk samme svar på nytt.
- ☐ Jeg sjekket i O6 at konstruksjonen virker på en kort testliste (f.eks. $5$ og $11$).
- ☐ Jeg sjekket i O7 at $n=9$ bryter ulikheten, altså at $n_0$ er minst.
- ☐ Jeg sammenlignet konvergentene i O8 med desimalverdien av $\sqrt{18}\approx 4{,}2426$.
Tid:

- ☐ Jeg leste hele settet først, og skrev sjangeren i margen.

- ☐ Jeg tok O5, O4 og O3 tidlig — de tre raskeste delpunktene.
- ☐ Jeg lot ikke O8 (spesialtemaet) spise tid fra kjernesjangrene.
- ☐ Jeg satte av de siste 25 minuttene til kontroll.
Hvis noe skar seg:
- ☐ Fant du bare tre løsninger i O1-intervallet? Skrittlengden i $x$ er $b/d=23$, og intervallet har lengde $100$ — det er plass til fire.
- ☐ Brukte du Wilson på potensleddet eller Fermat på fakultetet i O2? Del arket i to kolonner.
- ☐ Ble O3-svaret feil i én kongruens? Sjekk at du reduserte hver $N_k$ modulo sin egen $m_k$ før du fant inversen.
- ☐ Falt dekrypteringen i O4? Kontroller $d$ før du starter kvadrattabellen.

- ☐ Ble O6 stående uten umulighetssetning? Se hva midtnivåbesvarelsen over gjør, og hva den mangler.

- ☐ Satte du $n_0=1$ i O7? Ulikheten holder for $n=1$, men brytes for $n=2$ — og spørsmålet var om alle $n\ge n_0$.
- ☐ Lukket ikke perioden i O8a? Kontrollen er $a_k=2a_0=8$; kommer du ikke dit, er det en regnefeil i $d_k$-kolonnen.
Neste steg — og dette er bokas siste side med oppgaver:
Har du tatt alle tre øvingseksamenene, har du møtt samtlige sjangre A–K, de fem søylene tre ganger hver, og bevisoppgaven tre ganger. Det som gjenstår før eksamen, er ikke mer nytt stoff:

1. Gå gjennom de åpne punktene i de tre selvdiagnosene. Er de samme punktene åpne i flere sett, er det ett fagkapittel du skal lese om igjen — ikke tre.

2. Ta den kalde banken i kap. 8.1 på nytt, og igjen tre dager senere. Under kode D er det gjenkallingen som avgjør.
3. Regn på nytt de delpunktene du mistet, med boka lukket. Prosedyrer pugges ved å kjøres.
4. Les kap. 0.1 en siste gang kvelden før: eksamensformen, de fem søylene, og tidsbudsjettet på ~24 minutter per delpunkt.
Lykke til. Du har apparatet — dette handler bare om å få det ned på papiret.