2.5 Restberegning: eksponentreduksjon møter Wilson (fakultetsoppgaven)

Steg 2: del uttrykket i ledd. Vi har to ledd:

- $5\cdot 15!$ — et fakultet $\Rightarrow$ Wilson;
- $4^{221}$ — en potens $\Rightarrow$ Fermat.

De regnes hver for seg.

---

Ledd 1: $5\cdot 15!$ modulo $17$.

Ved Wilsons teorem er $(17-1)! = 16!\equiv -1\pmod{17}$.

Vi skriver $16!$ ved hjelp av $15!$ og de faktorene som mangler:

$$16! = 15!\cdot 16.$$

Nå skrives hver av de manglende faktorene som en negativ rest modulo $17$ — det er hele trikset, og det er her fortegnene avgjør:

$$16\equiv -1\pmod{17}.$$

Altså er

$$-1\equiv 16!\equiv 15!\cdot (-1) = -1\cdot 15!\pmod{17}.$$

Vi løser for $15!$. Koeffisienten er $-1\equiv 16\pmod{17}$, og inversen til $16$ modulo $17$ er $16$ (kontroll: $16\cdot 16 = 256 = 17\cdot 15 + 1$). Ganger vi begge sider med $16$:

$$15!\equiv -1\cdot 16 = -16\equiv 1\pmod{17}.$$

Til slutt ganger vi med $5$:

$$5\cdot 15!\equiv 5\cdot 1 = 5\equiv 5\pmod{17}.$$

Konklusjon. Resten når $5\cdot 15!$ deles på $17$, er $\boxed{5}$.

---

Ledd 2: $4^{221}$ modulo $17$.

(i) Faktoriser modulusen. $17$ er et primtall.

(ii) $\gcd$-sjekken. $\gcd(4,17)=1$, siden primtallet $17$ ikke deler $4$. Vilkåret er oppfylt, så teoremet kan brukes.

(iii) Regn ut $\phi(n)$. Modulusen er primtallet $17$, så $\phi(17)=17-1=16$.

(iv) Reduser eksponenten. Fra Fermats lille teorem er $4^{16}\equiv 1\pmod{17}$, så vi kan redusere eksponenten modulo $p-1=16$:

$$221 = 16\cdot 13 + 13,\qquad\text{så}\qquad 4^{221} = \left(4^{16}\right)^{13}\cdot 4^{13}\equiv 1^{13}\cdot 4^{13} = 4^{13}\pmod{17}.$$

(v) Binærutviklingen av eksponenten og de suksessive kvadratene. Vi skriver eksponenten som en sum av toerpotenser: $13 = 8 + 4 + 1$, altså $13$ i binær er $1101$. Deretter kvadrerer vi oss oppover, og reduserer modulo $17$ etter hvert kvadrat:

Steg 5: kombiner restene. Kongruenser kan adderes, så

$$5\cdot 15!+4^{221}\equiv 5+4=9\pmod{17}.$$

Steg 6: konklusjon. Resten når $5\cdot 15!+4^{221}$ deles på $17$, er $\boxed{9}$.

Hvor føringspoengene sitter i denne besvarelsen:

- at $17$ er et primtall er sagt — det er premisset for begge teoremene;

- de to leddene er behandlet hver for seg, med hvert sitt navngitte teorem;
- $p\nmid 4$ er sjekket før eksponenten ble redusert;

- de manglende faktorene i fakultetet er skrevet som negative rester, med utregningen synlig;

- kvadrattabellen står der, ikke bare sluttallet;

- konklusjonen er en setning med resten som et tall mellom $0$ og $16$.
Legg merke til at vi aldri regnet ut $15!$ (13 siffer) eller $4^{221}$ (134 siffer). All regning foregikk med tall under $300$.

Steg 2: to ledd — fakultetet $4\cdot 10!$ (Wilson) og potensen $6^{202}$ (Fermat).

---

Ledd 1: $4\cdot 10!$ modulo $13$.

Ved Wilsons teorem er $(13-1)! = 12!\equiv -1\pmod{13}$.

Vi skriver $12!$ ved hjelp av $10!$ og de faktorene som mangler:

$$12! = 10!\cdot 11\cdot 12.$$

Nå skrives hver av de manglende faktorene som en negativ rest modulo $13$ — det er hele trikset, og det er her fortegnene avgjør:

$$11\equiv -2\pmod{13},\qquad 12\equiv -1\pmod{13}.$$

Altså er

$$-1\equiv 12!\equiv 10!\cdot (-2)\cdot (-1) = 2\cdot 10!\pmod{13}.$$

Vi løser for $10!$. Koeffisienten er $2\equiv 2\pmod{13}$, og inversen til $2$ modulo $13$ er $7$ (kontroll: $2\cdot 7 = 14 = 13\cdot 1 + 1$). Ganger vi begge sider med $7$:

$$10!\equiv -1\cdot 7 = -7\equiv 6\pmod{13}.$$

Til slutt ganger vi med $4$:

$$4\cdot 10!\equiv 4\cdot 6 = 24\equiv 11\pmod{13}.$$

Konklusjon. Resten når $4\cdot 10!$ deles på $13$, er $\boxed{11}$.

---

Ledd 2: $6^{202}$ modulo $13$.

(i) Faktoriser modulusen. $13$ er et primtall.

(ii) $\gcd$-sjekken. $\gcd(6,13)=1$, siden primtallet $13$ ikke deler $6$. Vilkåret er oppfylt, så teoremet kan brukes.

(iii) Regn ut $\phi(n)$. Modulusen er primtallet $13$, så $\phi(13)=13-1=12$.

(iv) Reduser eksponenten. Fra Fermats lille teorem er $6^{12}\equiv 1\pmod{13}$, så vi kan redusere eksponenten modulo $p-1=12$:

$$202 = 12\cdot 16 + 10,\qquad\text{så}\qquad 6^{202} = \left(6^{12}\right)^{16}\cdot 6^{10}\equiv 1^{16}\cdot 6^{10} = 6^{10}\pmod{13}.$$

(v) Binærutviklingen av eksponenten og de suksessive kvadratene. Vi skriver eksponenten som en sum av toerpotenser: $10 = 8 + 2$, altså $10$ i binær er $1010$. Deretter kvadrerer vi oss oppover, og reduserer modulo $13$ etter hvert kvadrat:

Steg 5: kombiner.

$$4\cdot 10!+6^{202}\equiv 11+4=15\equiv 2\pmod{13},$$

siden $15=13+2$.

Steg 6: konklusjon. Resten når $4\cdot 10!+6^{202}$ deles på $13$, er $\boxed{2}$.

Merk det siste steget: summen $11+4=15$ måtte reduseres én gang til. Det er en klassisk slurvefeil å stoppe ved $15$ — en rest modulo $13$ er et tall mellom $0$ og $12$.

Og merk at de to leddene brukte ulike deler av det samme primtallet: Wilson brukte at $12!\equiv -1$, Fermat at eksponenten kan reduseres modulo $12$. Tallet $12$ opptrer i begge, men av to helt ulike grunner — det er $p-1$ i Fermat og den siste faktoren i fakultetet hos Wilson.

Steg 2: faktoriser og splitt. $100=4\cdot 25$ med $\gcd(4,25)=1$, så det er nok å finne resten modulo $4$ og modulo $25$ (kap. 2.4).

Modulo $4$: $12=4\cdot 3$, så $12\equiv 0\pmod 4$, og
$$12^{75}\equiv 0\pmod 4.$$

Modulo $25$: her er $\gcd(12,25)=1$ ✓, så Eulers teorem gjelder. $\phi(25)=25-5=20$, og vi reduserer eksponenten modulo $20$:
$$75=20\cdot 3+15,\qquad\text{så}\qquad 12^{75}\equiv 12^{15}\pmod{25}.$$

(v) Binærutviklingen av eksponenten og de suksessive kvadratene. Vi skriver eksponenten som en sum av toerpotenser: $15 = 8 + 4 + 2 + 1$, altså $15$ i binær er $1111$. Deretter kvadrerer vi oss oppover, og reduserer modulo $25$ etter hvert kvadrat:

$$x\equiv 0\pmod 4,\qquad x\equiv 18\pmod{25}.$$

Modulene er relativt primiske, så ved det kinesiske restteoremet finnes nøyaktig én løsning modulo $100$.

Suksessiv innsetting. Vi starter i kongruensen med størst modulus, fordi den gir færrest tall å prøve, og arbeider oss nedover.

Fra $x\equiv 18\pmod{25}$ skriver vi

$$x = 18 + 25t,\qquad t\in\mathbb{Z}.$$
Setter vi dette inn i $x\equiv 0\pmod{4}$, får vi
$$18 + 25t\equiv 0\pmod{4}\quad\Longleftrightarrow\quad 1t\equiv 2\pmod{4}.$$

Altså er $t\equiv 2\pmod{4}$.

Da er $t = 2 + 4s$, og

$$x = 18 + 25(2 + 4s) = 68 + 100s,$$

altså $x\equiv 68\pmod{100}$.

Kontroll — sett inn i ALLE kongruensene: $68 = 4\cdot 17 + 0$ ✓; $68 = 25\cdot 2 + 18$ ✓. Samme svar som formelen gir.

Steg 4: konklusjon. Resten når $12^{75}$ deles på $100$, er $\boxed{68}$.

Kontroll: $68=4\cdot 17$ ✓ (delelig med $4$), og $68=25\cdot 2+18$ ✓.

Merk hvorfor dette ikke kunne gjøres direkte: $\phi(100)=40$, og hadde vi redusert $75$ modulo $40$ til $12^{35}$, ville vi brukt et teorem som ikke gjelder. At svaret tilfeldigvis kunne blitt riktig, hjelper ikke — metoden er det som vurderes, og en ubegrunnet reduksjon er en byggefeil i besvarelsen.

Og merk at resten $68$ er de to siste sifrene i $12^{75}$. Splittingen i $4$ og $25$ er standardgrepet for «finn de to siste sifrene», fordi $100=4\cdot 25$.

---

a) $28!$ modulo $31$.

Ved Wilsons teorem er $(31-1)! = 30!\equiv -1\pmod{31}$.

Vi skriver $30!$ ved hjelp av $28!$ og de faktorene som mangler:

$$30! = 28!\cdot 29\cdot 30.$$

Nå skrives hver av de manglende faktorene som en negativ rest modulo $31$ — det er hele trikset, og det er her fortegnene avgjør:

$$29\equiv -2\pmod{31},\qquad 30\equiv -1\pmod{31}.$$

Altså er

$$-1\equiv 30!\equiv 28!\cdot (-2)\cdot (-1) = 2\cdot 28!\pmod{31}.$$

Vi løser for $28!$. Koeffisienten er $2\equiv 2\pmod{31}$, og inversen til $2$ modulo $31$ er $16$ (kontroll: $2\cdot 16 = 32 = 31\cdot 1 + 1$). Ganger vi begge sider med $16$:

$$28!\equiv -1\cdot 16 = -16\equiv 15\pmod{31}.$$

Til slutt ganger vi med $1$:

$$1\cdot 28!\equiv 1\cdot 15 = 15\equiv 15\pmod{31}.$$

Konklusjon. Resten når $1\cdot 28!$ deles på $31$, er $\boxed{15}$.

---

b) $5^{400}$ modulo $31$.

(i) Faktoriser modulusen. $31$ er et primtall.

(ii) $\gcd$-sjekken. $\gcd(5,31)=1$, siden primtallet $31$ ikke deler $5$. Vilkåret er oppfylt, så teoremet kan brukes.

(iii) Regn ut $\phi(n)$. Modulusen er primtallet $31$, så $\phi(31)=31-1=30$.

(iv) Reduser eksponenten. Fra Fermats lille teorem er $5^{30}\equiv 1\pmod{31}$, så vi kan redusere eksponenten modulo $p-1=30$:

$$400 = 30\cdot 13 + 10,\qquad\text{så}\qquad 5^{400} = \left(5^{30}\right)^{13}\cdot 5^{10}\equiv 1^{13}\cdot 5^{10} = 5^{10}\pmod{31}.$$

(v) Binærutviklingen av eksponenten og de suksessive kvadratene. Vi skriver eksponenten som en sum av toerpotenser: $10 = 8 + 2$, altså $10$ i binær er $1010$. Deretter kvadrerer vi oss oppover, og reduserer modulo $31$ etter hvert kvadrat:

c) $7\cdot 28!+5^{400}$ modulo $31$.

Nå er begge delene ferdig regnet, og vi setter dem sammen. Fra a) er $28!\equiv 15\pmod{31}$, så

$$7\cdot 28!\equiv 7\cdot 15=105\equiv 12\pmod{31},$$

siden $105=31\cdot 3+12$. Og fra b) er $5^{400}\equiv 5\pmod{31}$.

Kongruenser kan adderes, så

$$7\cdot 28!+5^{400}\equiv 12+5=17\pmod{31}.$$

Konklusjon. Resten er $\boxed{17}$.
Hvor føringspoengene sitter, delpunkt for delpunkt:
- a) at $31$ er et primtall; teoremnavnet; de manglende faktorene som negative rester; inversen kontrollert.

- b) at $31\nmid 5$; teoremnavnet; divisjonen $400=30\cdot 13+10$; kvadrattabellen.
- c) at leddene kan adderes; begge delresultatene hentet fra a) og b) med referanse; summen redusert til et tall i $0,\dots,30$.

Tidsbudsjett: a) ~5 min, b) ~5 min, c) ~2 min. Til sammen ~12 minutter for tre delpunkt som til sammen er verdt ~72 minutter av budsjettet (~24 min per delpunkt). Det er derfor denne oppgavetypen er kjernen i et godt eksamensresultat: den er rask når apparatet sitter.

Merk hvordan c) gjenbrukte a) og b). Det er den vanlige strukturen i arkivet — delpunktene er trapper, ikke uavhengige oppgaver. Regner du a) feil, faller c) også, så kontrollen i a) er verdt tid.