Tilbake
2.3
Alle fag for Høyskole

2.3 Wilsons teorem og fakultets-triksene

Wilsons teorem (p−1)!≡−1 (mod p) og signaturtrikset: rest av k·(n!) mod p ved å skrive de manglende faktorene p−1, p−2, … som −1, −2, … og forkorte — nesten alltid koblet til fakultetsoppgaven.

55 min
8 oppgaver
Wilsons teoremfakultets-triksene
Din fremgang i kapitlet
0 / 8 oppgaver
Kapitlets plass i kurset

Forkunnskaper

Fra boka: kap. 1.4 (kongruens, modulær invers, forkorting) og kap. 2.1 (Eulers teorem — brukes ikke direkte her, men ϕ\phi og gcd-vanen gjør). Kap. 2.2 er nyttig for trikset med negative rester.

Sist du var her. De to resultatene dette kapitlet står helt på:

Modulær invers. Er gcd⁡(a,m)=1\gcd(a,m)=1, finnes det et tall uu med au≡1(modm)au\equiv 1\pmod m, og det er entydig modulo mm. Med primtallsmodulus pp har hvert av tallene 1,…,p−11,\dots,p-1 en invers.

Forkortingsregelen. Er ca≡cb(modm)ca\equiv cb\pmod m og gcd⁡(c,m)=1\gcd(c,m)=1, så er a≡b(modm)a\equiv b\pmod m. Med primtallsmodulus kan du altså forkorte med alt som ikke er delelig med pp.

De to sammen er hele beviset for Wilsons teorem, og de er også grunnen til at trikset i løkke 4 er lovlig.

Fra videregående er ingenting påkrevd.

Et tall med 119 siffer

Oppgaven er: finn resten når 7⋅80!7\cdot 80! deles på 8383.

80!80! er produktet av alle tallene fra 11 til 8080. Det har 119 siffer. Kalkulatoren din viser «error» eller «inf», og du har ingen datamaskin. Likevel skal du kunne svare på dette i løpet av fem minutter med penn og papir — og oppgaver av denne typen står i 11 av 15 eksamenssett.

Grepet er å ikke regne fakultetet, men å gjenkjenne det. Wilsons teorem sier at 82!≡−1(mod83)82!\equiv -1\pmod{83}. Og 82!82! er nesten 80!80!: den har bare to faktorer til, nemlig 8181 og 8282. Så
82!=80!⋅81⋅82.82!=80!\cdot 81\cdot 82.
Nå kommer trikset. Modulo 8383 er 82≡−182\equiv -1 og 81≡−281\equiv -2 — de to store faktorene er små negative tall. Da er
−1≡82!≡80!⋅(−2)(−1)=2⋅80!(mod83),-1\equiv 82!\equiv 80!\cdot(-2)(-1)=2\cdot 80!\pmod{83},
og du står med en enkel kongruens i én ukjent, nemlig 80!80!. Resten er regning du alt kan.

Hvorfor det virker: fakultet er et produkt, og modulo pp kan hver faktor byttes med sin rest. Faktorene nær pp har små negative rester, og små tall kan du gange i hodet. Hele metoden er å bytte «8181» med «−2-2».

Vi bygger det i fire trinn: teoremet og hvorfor det er sant, hvorfor det krever et primtall, trikset med negative rester, og til slutt kombinasjonen med invers — det siste steget der du deler modulo pp.

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: Wilsons teorem, og hvorfor det er sant

~12 minutter.

Teoremet er kort å si og litt overraskende: produktet av alle de p−1p-1 nullforskjellige restene modulo pp er alltid −1-1.

📜Wilsons teorem
For hvert primtall pp:
(p−1)!≡−1(modp).(p-1)!\equiv -1\pmod p.

Ekvivalent: pp deler (p−1)!+1(p-1)!+1.

Kontroll med små primtall, verdt å gjøre én gang:

pp(p−1)!(p-1)!modulo pp
55242424=5⋅4+424=5\cdot 4+4, og 4≡−14\equiv -1 ✓
77720720720=7⋅102+6720=7\cdot 102+6, og 6≡−16\equiv -1 ✓
11113 628 8003\,628\,800rest 10≡−110\equiv -1 ✓

Bevis — invers-parringen. For p=2p=2 er 1!=1≡−1(mod2)1!=1\equiv -1\pmod 2, så la pp være et odde primtall.
Steg 1: hver faktor har en invers. Hvert tall aa i 1,…,p−11,\dots,p-1 er relativt primisk til pp, så det har en invers a−1a^{-1} modulo pp (kap. 1.4), og inversen ligger også i 1,…,p−11,\dots,p-1.
Steg 2: hvilke tall er sine egne inverser? Vi løser a≡a−1(modp)a\equiv a^{-1}\pmod p, altså a2≡1(modp)a^2\equiv 1\pmod p. Da er
p∣(a2−1)=(a−1)(a+1),p\mid(a^2-1)=(a-1)(a+1),

og etter Euklids lemma (kap. 1.1) deler pp enten a−1a-1 eller a+1a+1. Altså er a≡1a\equiv 1 eller a≡−1≡p−1(modp)a\equiv -1\equiv p-1\pmod p. Bare 11 og p−1p-1 er sine egne inverser.

Steg 3: par opp resten. De øvrige p−3p-3 tallene 2,3,…,p−22,3,\dots,p-2 deler seg dermed i par {a,a−1}\{a,a^{-1}\} med a≠a−1a\ne a^{-1}, og produktet av hvert par er ≡1(modp)\equiv 1\pmod p. (Antallet p−3p-3 er et partall, så parringen går opp.)

Steg 4: sett sammen. I produktet (p−1)!=1⋅2⋯(p−1)(p-1)!=1\cdot 2\cdots(p-1) kollapser alle parene til 11, og bare de to selvinverse faktorene står igjen:
(p−1)!≡1⋅(p−1)≡1⋅(−1)=−1(modp).■(p-1)!\equiv 1\cdot(p-1)\equiv 1\cdot(-1)=-1\pmod p.\qquad\blacksquare
Intuisjon: produktet av alle restene er som et rom fullt av par som nøytraliserer hverandre. Bare to elementer står alene — 11 og −1-1 — og svaret er produktet av dem.

Teoremet må sitte utenat, og det må navngis. Fasitene skriver «ved Wilsons teorem» der det brukes.

Invers-parringen — minnekroken
Kortet som gir deg teoremet tilbake om formuleringen glipper. Utledes på stedet, to linjer:

- Hvert tall i 1,…,p−11,\dots,p-1 har en invers modulo pp, og parer seg med den. Hvert par ganger til 11.
- Bare 11 og p−1p-1 er sine egne inverser (fordi a2≡1a^2\equiv 1 gir p∣(a−1)(a+1)p\mid(a-1)(a+1)). Så produktet av alt er 1⋅(p−1)≡−11\cdot(p-1)\equiv -1.

Se det med tall, p=13p=13. Parene er
{2,7}, {3,9}, {4,10}, {5,8}, {6,11},\{2,7\},\ \{3,9\},\ \{4,10\},\ \{5,8\},\ \{6,11\},
og hvert produkt er ≡1(mod13)\equiv 1\pmod{13}: 2⋅7=142\cdot 7=14, 3⋅9=273\cdot 9=27, 4⋅10=404\cdot 10=40, 5⋅8=405\cdot 8=40, 6⋅11=666\cdot 11=66 — alle gir rest 11.

Igjen står 11 og 1212, og 12!≡1⋅12≡−1(mod13)12!\equiv 1\cdot 12\equiv -1\pmod{13} ✓.

Hvorfor det er verdt de to minuttene: en oppgave kan be deg «forklare hvorfor Wilsons teorem gjelder». Da er dette svaret. Og parringen er samme idé som i beviset for Eulers teorem (kap. 2.1) — der stokket vi om et redusert restsystem, her parer vi det.

Hvilke tall er sine egne inverser?
Modulo et primtall pp er a≡a−1a\equiv a^{-1} nøyaktig når
a≡1ellera≡−1≡p−1(modp).a\equiv 1\quad\text{eller}\quad a\equiv -1\equiv p-1\pmod p.

Utledes på stedet: a≡a−1a\equiv a^{-1} betyr a2≡1a^2\equiv 1, altså p∣(a−1)(a+1)p\mid(a-1)(a+1). Etter Euklids lemma deler primtallet pp en av de to faktorene, så a≡±1a\equiv\pm 1. ■\blacksquare

Merk at primtallsegenskapen er nødvendig. Modulo 88 er 32=9≡13^2=9\equiv 1 og 52=25≡15^2=25\equiv 1 — fire selvinverse elementer (1,3,5,71,3,5,7), ikke to. Det er nettopp derfor Wilsons teorem bryter sammen for sammensatte moduler.

Der resultatet dukker opp igjen: i Del 4, der «x2≡1x^2\equiv 1 har nøyaktig to løsninger modulo pp» er utgangspunktet for at en kvadratisk kongruens x2≡ax^2\equiv a har nøyaktig to eller ingen løsninger.

✏️Wilsons teorem sett med tall, og parringen skrevet ut
a) Verifiser Wilsons teorem for p=7p=7 ved direkte regning.
b) Skriv ut invers-parringen for p=11p=11, og bruk den til å regne 10!10! modulo 1111 uten å regne ut 10!10!.
a) (7−1)!=6!=720(7-1)!=6!=720. Vi deler: 720=7⋅102+6720=7\cdot 102+6, så
6!≡6≡−1(mod7) ✓.6!\equiv 6\equiv -1\pmod 7\ \checkmark.

b) Vi finner inversen til hvert tall i 2,…,92,\dots,9 modulo 1111:

ParProduktModulo 1111
{2,6}\{2,6\}121212=11+1≡112=11+1\equiv 1
{3,4}\{3,4\}1212≡1\equiv 1
{5,9}\{5,9\}454545=44+1≡145=44+1\equiv 1
{7,8}\{7,8\}565656=55+1≡156=55+1\equiv 1

De fire parene dekker tallene 2,3,4,5,6,7,8,92,3,4,5,6,7,8,9 — altså alle unntatt 11 og 1010, som er sine egne inverser (1⋅1=11\cdot 1=1 og 10⋅10=100=99+1≡110\cdot 10=100=99+1\equiv 1).
Da er
10!=1⏟alene⋅(2⋅6)(3⋅4)(5⋅9)(7⋅8)⏟≡1 hver⋅10⏟alene≡1⋅1⋅1⋅1⋅1⋅10≡10≡−1(mod11).10!=\underbrace{1}_{\text{alene}}\cdot\underbrace{(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)}_{\equiv 1\text{ hver}}\cdot\underbrace{10}_{\text{alene}}\equiv 1\cdot 1\cdot 1\cdot 1\cdot 1\cdot 10\equiv 10\equiv -1\pmod{11}.
Kontroll: 10!=3 628 80010!=3\,628\,800, og 3 628 800=11⋅329 890+103\,628\,800=11\cdot 329\,890+10 — rest 10≡−110\equiv -1 ✓.
Sluttsvar: 6!≡−1(mod7)6!\equiv -1\pmod 7 og 10!≡−1(mod11)10!\equiv -1\pmod{11}, i tråd med Wilsons teorem.

Legg merke til at vi i b) regnet et sjusifret fakultet modulo 1111 uten å gange ett eneste stort tall. Det er hele idéen i kapitlet: fakultet modulo pp håndteres ved å gjenkjenne struktur, ikke ved å regne.

📝Oppgave 1
a) Hva er resten når 12!12! deles på 1313?
b) Hva er resten når 30!30! deles på 3131?
c) Hva er resten når 4⋅12!4\cdot 12! deles på 1313?

Løkke 2: Hvorfor teoremet krever et primtall

~9 minutter.

Wilsons teorem er en av få setninger i faget der den omvendte påstanden også er sann. Det gjør den til en ekte primtallskarakterisering — og det forklarer hvorfor den bryter så totalt sammen for sammensatte tall.

— naturlig pausepunkt —

(n−1)! for sammensatt n
For sammensatt n>4n>4 er
(n−1)!≡0(modn).(n-1)!\equiv 0\pmod n.

Altså det motsatte ytterpunktet av −1-1: ikke bare feil svar, men det svaret som er lengst mulig unna.

Utledes på stedet. Er n=abn=ab med 1<a<b<n1<a<b<n, står både aa og bb blant faktorene i (n−1)!(n-1)!, så produktet ab=nab=n deler (n−1)!(n-1)!. Er n=a2n=a^2 med a>2a>2, står både aa og 2a2a blant faktorene (siden 2a<a2=n2a<a^2=n), og a⋅2a=2na\cdot 2a=2n er delelig med nn. ■\blacksquare

Kontroll: 7!=5040=8⋅6307!=5040=8\cdot 630, så 7!≡0(mod8)7!\equiv 0\pmod 8 ✓. Og 8!=40 320=9⋅44808!=40\,320=9\cdot 4480, så 8!≡0(mod9)8!\equiv 0\pmod 9 ✓.

Det ene unntaket er n=4n=4: 3!=6≡2(mod4)3!=6\equiv 2\pmod 4. Her er n=22n=2^2 med a=2a=2, og 2a=4=n2a=4=n er ikke blant faktorene i 3!3! — derfor faller argumentet.

Praktisk konsekvens: før du bruker Wilsons teorem, sjekk at modulusen er et primtall. Er den sammensatt, er svaret på «(n−1)! mod n(n-1)!\bmod n» 00 (for n>4n>4) — og det er en helt annen oppgave.

Den omvendte påstanden — Wilson som primtallstest
Wilsons teorem gjelder begge veier:
(n−1)!≡−1(modn)⟺n er et primtall(n-1)!\equiv -1\pmod n\quad\Longleftrightarrow\quad n\text{ er et primtall}
(for n>1n>1).

Retningen «⇐\Leftarrow» er teoremet. Retningen «⇒\Rightarrow» følger av forrige kort: er nn sammensatt og n>4n>4, er (n−1)!≡0(n-1)!\equiv 0, og 0≢−10\not\equiv -1 siden n>1n>1. Og n=4n=4 gir 3!≡2≢−1(mod4)3!\equiv 2\not\equiv -1\pmod 4. ■\blacksquare

Dette er verdt å merke seg, for Fermat kan IKKE det. 2340≡1(mod341)2^{340}\equiv 1\pmod{341} selv om 341=11⋅31341=11\cdot 31 (kap. 2.2). Wilson har ingen slike pseudoprimtall — kriteriet er skarpt.

Men den er ubrukelig som praktisk test. Å regne (n−1)! mod n(n-1)!\bmod n krever n−2n-2 multiplikasjoner; prøvedivisjon opp til n\sqrt n er uendelig mye raskere. Wilsons teorem er et teoretisk kriterium, ikke en algoritme.

Der det likevel dukker opp i oppgaver: «vis at nn er sammensatt ved hjelp av Wilsons teorem», eller «forklar hvorfor Wilsons teorem karakteriserer primtallene mens Fermats lille teorem ikke gjør det».

📝Oppgave 2
a) Regn ut resten når 9!9! deles på 1010, og forklar svaret.
b) Vis at (n−1)!≡0(modn)(n-1)!\equiv 0\pmod n for alle sammensatte n>4n>4.
c) Hva er 3!3! modulo 44? Hvorfor er n=4n=4 et unntak?

Løkke 3: Når én faktor mangler — (p−2)!(p-2)!

~10 minutter.

Nå til den formen oppgavene faktisk har. Fakultetet er sjelden nøyaktig (p−1)!(p-1)!; det er litt mindre, og da mangler noen faktorer. Vi starter med tilfellet der bare én mangler.

(p−2)! ≡ 1 (mod p)
For hvert primtall pp:
(p−2)!≡1(modp).(p-2)!\equiv 1\pmod p.

Utledes på stedet, én linje. Skriv (p−1)!=(p−2)!⋅(p−1)(p-1)!=(p-2)!\cdot(p-1) og bruk at p−1≡−1(modp)p-1\equiv -1\pmod p:
−1≡(p−1)!≡(p−2)!⋅(−1)(modp).-1\equiv(p-1)!\equiv(p-2)!\cdot(-1)\pmod p.
Gang begge sider med −1-1 (lovlig — gcd⁡(−1,p)=1\gcd(-1,p)=1):
(p−2)!≡1(modp).■(p-2)!\equiv 1\pmod p.\qquad\blacksquare

Kontroll: p=7p=7 gir 5!=120=7⋅17+15!=120=7\cdot 17+1, altså ≡1\equiv 1 ✓. Og p=13p=13 gir 11!≡1(mod13)11!\equiv 1\pmod{13}.

Hvorfor kortet er verdt plass: dette er det enkleste tilfellet av trikset, og det er hyppig nok å møte direkte. Men merk at du ikke skal pugge en tabell over (p−2)!(p-2)!, (p−3)!(p-3)! og så videre — du skal kunne prosedyren i neste kort, som gir alle tilfellene.

Til sammenligning: (p−3)!≡?(p-3)!\equiv ? Fra (p−1)!=(p−3)!⋅(p−2)(p−1)≡(p−3)!⋅(−2)(−1)=2(p−3)!(p-1)!=(p-3)!\cdot(p-2)(p-1)\equiv(p-3)!\cdot(-2)(-1)=2(p-3)! får du 2(p−3)!≡−12(p-3)!\equiv -1, altså (p−3)!≡−12(p-3)!\equiv -\tfrac12 modulo pp — som betyr «gang med inversen til 22». Det er trikset i full form.

Negative rester — kjernen i trikset
De faktorene som mangler i n!n! sammenlignet med (p−1)!(p-1)!, er de store tallene n+1,n+2,…,p−1n+1,n+2,\dots,p-1. Modulo pp er de små negative tall:
p−1≡−1,p−2≡−2,p−3≡−3,…p-1\equiv -1,\qquad p-2\equiv -2,\qquad p-3\equiv -3,\qquad\dots

Regelen som gjør regningen overkommelig: faktoren p−jp-j erstattes med −j-j. Da er produktet av de manglende faktorene et lite tall med et fortegn du kan holde orden på, i stedet for et produkt av tresifrede tall.

Eksempel, p=23p=23: mangler faktorene 19,20,21,2219,20,21,22, så skriver du
19≡−4,20≡−3,21≡−2,22≡−1(mod23),19\equiv -4,\quad 20\equiv -3,\quad 21\equiv -2,\quad 22\equiv -1\pmod{23},
og produktet blir (−4)(−3)(−2)(−1)=24≡1(mod23)(-4)(-3)(-2)(-1)=24\equiv 1\pmod{23}. Fire tresifrede multiplikasjoner er blitt én liten.

Fortegnsregelen: et produkt av jj negative tall har fortegn (−1)j(-1)^j. Er antallet manglende faktorer et partall, er produktet positivt; er det odde, negativt. Det er her feilene skjer — tell antallet.

Trikset må sitte utenat. Det er den ene teknikken som gjør 73 % av eksamenssettene håndterbare på dette punktet.

Fakultets-trikset — malen i fem steg

Slik føres hver oppgave av typen «finn resten når k⋅m!k\cdot m! deles på primtallet pp». Malen er identisk i kap. 2.5, kap. 2.6 og prøvene.

(1) Skriv Wilson. «(p−1)!≡−1(modp)(p-1)!\equiv -1\pmod p, ved Wilsons teorem.» Sjekk samtidig at pp er et primtall.

(2) Uttrykk (p−1)!(p-1)! ved m!m!. (p−1)!=m!⋅(m+1)(m+2)⋯(p−1)(p-1)!=m!\cdot(m+1)(m+2)\cdots(p-1) — skriv de manglende faktorene ut.

(3) Bytt de manglende faktorene med negative rester. p−j≡−jp-j\equiv -j, og regn ut det lille produktet, med fortegn.

(4) Løs for m!m!. Du står med c⋅m!≡−1(modp)c\cdot m!\equiv -1\pmod p. Gang begge sider med inversen til cc modulo pp — lovlig, siden cc er et produkt av tall som ikke er delelige med pp.

(5) Gang med kk, og konkluder. Svaret oppgis som en rest mellom 00 og p−1p-1.

Malen må sitte utenat, og hvert steg bærer uttelling for seg selv — instruksen på hvert sett er at alle svar må begrunnes.

Steg (4) er stedet det går galt når man glemmer at man ikke kan «dele» modulo pp; man må gange med inversen. Er c=2c=2 og p=83p=83, er inversen 4242, ikke 12\tfrac12.

✏️Én manglende faktor: 3·15! modulo 17

Finn resten når 3⋅15!3\cdot 15! deles på 1717.

1717 er et primtall, så Wilsons teorem kan brukes.

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

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

16!=15!⋅16.16! = 15!\cdot 16.

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

16≡−1(mod17).16\equiv -1\pmod{17}.

Altså er

−1≡16!≡15!⋅(−1)=−1⋅15!(mod17).-1\equiv 16!\equiv 15!\cdot (-1) = -1\cdot 15!\pmod{17}.

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

15!≡−1⋅16=−16≡1(mod17).15!\equiv -1\cdot 16 = -16\equiv 1\pmod{17}.

Til slutt ganger vi med 33:

3⋅15!≡3⋅1=3≡3(mod17).3\cdot 15!\equiv 3\cdot 1 = 3\equiv 3\pmod{17}.

Konklusjon. Resten når 3⋅15!3\cdot 15! deles på 1717, er 3\boxed{3}.

Legg merke til at koeffisienten ble −1-1, altså at 16!≡−15!16!\equiv -15!. Da falt fortegnene sammen og 15!≡115!\equiv 1. Det er (p−2)!≡1(p-2)!\equiv 1-tilfellet, og det er verdt å kjenne igjen: mangler nøyaktig én faktor, er fakultetet ≡1\equiv 1.

📝Oppgave 3
a) Finn resten når 27!27! deles på 2929.
b) Finn resten når 10⋅27!10\cdot 27! deles på 2929.

Løkke 4: Flere manglende faktorer — hele trikset

~13 minutter.

Nå er vi ved eksamensformen. Fakultetet er et par hakk mindre enn (p−1)!(p-1)!, flere faktorer mangler, og du må både holde fortegnene i orden og gange med en invers til slutt.

✏️To manglende faktorer: 7·80! modulo 83

Finn resten når 7⋅80!7\cdot 80! deles på 8383.

Er 8383 et primtall? Vi prøvedividerer: ikke like, siffersum 1111 (ikke delelig med 33), ender ikke på 00 eller 55; 83/7≈11,983/7\approx 11{,}9 og 7⋅11=777\cdot 11=77, 7⋅12=847\cdot 12=84 — går ikke opp. 83≈9,1\sqrt{83}\approx 9{,}1, så vi er ferdige: 8383 er et primtall, og Wilsons teorem kan brukes.

Ved Wilsons teorem er (83−1)!=82!≡−1(mod83)(83-1)! = 82!\equiv -1\pmod{83}.

Vi skriver 82!82! ved hjelp av 80!80! og de faktorene som mangler:

82!=80!⋅81⋅82.82! = 80!\cdot 81\cdot 82.

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

81≡−2(mod83),82≡−1(mod83).81\equiv -2\pmod{83},\qquad 82\equiv -1\pmod{83}.

Altså er

−1≡82!≡80!⋅(−2)⋅(−1)=2⋅80!(mod83).-1\equiv 82!\equiv 80!\cdot (-2)\cdot (-1) = 2\cdot 80!\pmod{83}.

Vi løser for 80!80!. Koeffisienten er 2≡2(mod83)2\equiv 2\pmod{83}, og inversen til 22 modulo 8383 er 4242 (kontroll: 2⋅42=84=83⋅1+12\cdot 42 = 84 = 83\cdot 1 + 1). Ganger vi begge sider med 4242:

80!≡−1⋅42=−42≡41(mod83).80!\equiv -1\cdot 42 = -42\equiv 41\pmod{83}.

Til slutt ganger vi med 77:

7⋅80!≡7⋅41=287≡38(mod83).7\cdot 80!\equiv 7\cdot 41 = 287\equiv 38\pmod{83}.

Konklusjon. Resten når 7⋅80!7\cdot 80! deles på 8383, er 38\boxed{38}.

Hvor føringspoengene sitter i denne besvarelsen:

- at 8383 er et primtall er sjekket — uten det er teoremet ikke anvendelig;
- teoremet er navngitt («ved Wilsons teorem»);
- de manglende faktorene er skrevet som negative rester, med utregningen synlig — dette er selve trikset;
- inversen er regnet ut og kontrollert, ikke bare postulert;
- sluttsvaret er en rest mellom 00 og 8282, med en konklusjonssetning.

Merk hva vi aldri gjorde: vi regnet ikke ut 80!80!. Tallet har 119 siffer. All regningen foregikk med tall under 100100.

📝Oppgave 4

Finn resten når 6⋅17!6\cdot 17! deles på 2323.

📝Oppgave 5

Finn resten når 3⋅66!3\cdot 66! deles på 7171.

Steget der du må gange med en invers
Etter steg (3) i malen står du med en kongruens
c⋅m!≡−1(modp),c\cdot m!\equiv -1\pmod p,
der cc er produktet av de negative restene. Du skal finne m!m!, og da må du gange med inversen til cc — ikke «dele på cc».

Hvorfor det er lovlig: cc er et produkt av tall mellom 11 og p−1p-1, så p∤cp\nmid c, altså gcd⁡(c,p)=1\gcd(c,p)=1 og inversen finnes (kap. 1.4).

Tre måter å finne inversen, alle fullgode:

1. Prøv små multipler. Er c⋅j=1+multiplum av pc\cdot j=1+\text{multiplum av }p for en liten jj, er jj inversen. 24⋅3=72=71+124\cdot 3=72=71+1, så 24−1≡3(mod71)24^{-1}\equiv 3\pmod{71}.
2. Euklids algoritme (kap. 1.2) — den som alltid virker, i 2–4 divisjonslinjer.
3. cp−2c^{p-2} (kap. 2.2) — sjelden raskest for hånd.

Kontrollen tar fem sekunder: gang cc med inversen din og se at du får 11 modulo pp. Gjør det hver gang — en gal invers gir et svar som ser helt rimelig ut.

Merk et vanlig lykketreff: er c≡±1c\equiv\pm 1, trenger du ingen invers. Da er m!≡∓1m!\equiv\mp 1 direkte.

✏️Eksamensnivå: 5·60! modulo 67, med invers-steget skrevet ut

Finn resten når 5⋅60!5\cdot 60! deles på 6767.

Er 6767 et primtall? 67≈8,2\sqrt{67}\approx 8{,}2; verken 22, 33, 55 eller 77 går opp. Ja, og Wilsons teorem kan brukes.

Ved Wilsons teorem er (67−1)!=66!≡−1(mod67)(67-1)! = 66!\equiv -1\pmod{67}.

Vi skriver 66!66! ved hjelp av 60!60! og de faktorene som mangler:

66!=60!⋅61⋅62⋅63⋅64⋅65⋅66.66! = 60!\cdot 61\cdot 62\cdot 63\cdot 64\cdot 65\cdot 66.

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

61≡−6(mod67),62≡−5(mod67),63≡−4(mod67),64≡−3(mod67),65≡−2(mod67),66≡−1(mod67).61\equiv -6\pmod{67},\qquad 62\equiv -5\pmod{67},\qquad 63\equiv -4\pmod{67},\qquad 64\equiv -3\pmod{67},\qquad 65\equiv -2\pmod{67},\qquad 66\equiv -1\pmod{67}.

Altså er

−1≡66!≡60!⋅(−6)⋅(−5)⋅(−4)⋅(−3)⋅(−2)⋅(−1)=720⋅60!(mod67).-1\equiv 66!\equiv 60!\cdot (-6)\cdot (-5)\cdot (-4)\cdot (-3)\cdot (-2)\cdot (-1) = 720\cdot 60!\pmod{67}.

Vi løser for 60!60!. Koeffisienten er 720≡50(mod67)720\equiv 50\pmod{67}, og inversen til 5050 modulo 6767 er 6363 (kontroll: 50⋅63=3150=67⋅47+150\cdot 63 = 3150 = 67\cdot 47 + 1). Ganger vi begge sider med 6363:

60!≡−1⋅63=−63≡4(mod67).60!\equiv -1\cdot 63 = -63\equiv 4\pmod{67}.

Til slutt ganger vi med 55:

5⋅60!≡5⋅4=20≡20(mod67).5\cdot 60!\equiv 5\cdot 4 = 20\equiv 20\pmod{67}.

Konklusjon. Resten når 5⋅60!5\cdot 60! deles på 6767, er 20\boxed{20}.

Kontroll av inverssteget, som er det kritiske: vi brukte at inversen til koeffisienten er riktig. Ganger vi koeffisienten med inversen, skal vi få 11 modulo 6767 — og det gjør vi, som utregningen over viser.

Tidsbudsjett for denne oppgaven: primtallssjekk ~1 min, oppsettet med Wilson ~1 min, de negative restene ~2 min, inversen ~2 min, sammensetting ~1 min. Til sammen ~7 minutter — under en tredel av budsjettet for ett delpunkt (~24 min).

Legg merke til at seks faktorer manglet, altså et partall, så produktet av de negative restene ble positivt. Fortegnstellingen er den ene kontrollen som skiller riktig fra galt i denne sjangeren.

📝Oppgave 6

Finn resten når 2⋅18!2\cdot 18! deles på 2323, og kontroller svaret mot resultatet i oppgave 4.

Løkke 5: Varianter — divisjon, og fakultet i et større uttrykk

~11 minutter.

To varianter til, som begge forekommer: oppgaven ber deg dele på et tall modulo pp, eller fakultetet står i et sammensatt uttrykk sammen med en potens.

— naturlig pausepunkt —

Å «dele» modulo p
Det finnes ingen divisjon i kongruensregning. Å dele på aa betyr å gange med inversen til aa.

ba modulo pbetyrb⋅a−1(modp),na˚r p∤a.\frac{b}{a}\ \text{modulo } p\quad\text{betyr}\quad b\cdot a^{-1}\pmod p,\qquad\text{når }p\nmid a.

Notasjonsråd: skriv aldri en brøk i en kongruens på eksamen. Skriv b⋅a−1b\cdot a^{-1}, eller gang gjennom med a−1a^{-1} på begge sider. En brøk modulo pp er ikke gal, men den er lett å misforstå — og den skjuler vilkåret p∤ap\nmid a.

Eksempel: «finn xx med 3x≡5(mod17)3x\equiv 5\pmod{17}». Inversen til 33 modulo 1717 er 66 (siden 3⋅6=18≡13\cdot 6=18\equiv 1), så
x≡6⋅5=30≡13(mod17).x\equiv 6\cdot 5=30\equiv 13\pmod{17}.
Kontroll: 3⋅13=39=34+5≡53\cdot 13=39=34+5\equiv 5 ✓.

Hvor det møter Wilson: i steg (4) av malen, og i oppgaver som spør etter resten av noe som «(p−1)!k\displaystyle \frac{(p-1)!}{k}» — som skal leses som (p−1)!⋅k−1(p-1)!\cdot k^{-1}.

Fakultet i et sammensatt uttrykk

Står fakultetet sammen med noe annet — typisk en potens — behandles hver del for seg, og så settes de sammen med vanlige kongruensregneregler.

Formen oppgaven har: «finn resten når k⋅m!+aNk\cdot m!+a^{N} deles på pp».

Oppskriften:

1. Regn k⋅m! mod pk\cdot m!\bmod p med Wilsons teorem og fakultets-trikset.
2. Regn aN mod pa^{N}\bmod p med Fermats lille teorem og kvadrer-og-multipliser (kap. 2.2).
3. Legg sammen restene og reduser modulo pp.

Steg 3 er lovlig fordi kongruenser kan adderes (kap. 1.4).

Dette er signaturoppgaven i faget, og den har sitt eget kapittel: kap. 2.5. Her er poenget bare å se at de to teknikkene ikke blandes — de kjøres parallelt og møtes til slutt.

Den vanligste feilen: å redusere eksponenten i potensdelen med noe fra fakultetsdelen. De to delene har ingenting med hverandre å gjøre før steg 3.

📝Oppgave 7

La p=17p=17.

a) Finn resten når 15!15! deles på 1717.
b) Finn resten når 4504^{50} deles på 1717.
c) Finn resten når 3⋅15!+4503\cdot 15!+4^{50} deles på 1717.

📝Oppgave 8

La p=13p=13.

a) Finn resten når 9!9! deles på 1313.
b) Bruk svaret til å finne det tallet xx i 0≤x<130\le x<13 som tilfredsstiller 9!⋅x≡5(mod13)9!\cdot x\equiv 5\pmod{13}.
c) Kontroller svaret i b).

Begrepsbank

Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 55 minutter gjelder kjernestoffet over.

Merk at det viktigste kortet her er prosedyren, ikke teoremet. Teoremet er én linje; det er malen i fem steg og fortegnsregelen som avgjør om du får svaret riktig under tidspress.

Fakultet — notasjon og størrelse
n!=1⋅2⋅3⋯n,0!=1.n!=1\cdot 2\cdot 3\cdots n,\qquad 0!=1.

Hvor fort det vokser: 10!≈3,610!\approx 3{,}6 millioner, 20!20! har 19 siffer, 80!80! har 119 siffer, 100!100! har 158 siffer. En vanlig kalkulator gir opp rundt 69!69!.

Praktisk konsekvens for eksamen: står det et fakultet i en oppgave med en modulus, er teoremet den ENESTE veien. Det er ikke en snarvei du kan velge bort — det er ikke noe alternativ.

Konvensjonen 0!=10!=1 er det tomme produktet, og den brukes i binomialkoeffisienter: (n0)=n!0! n!=1\displaystyle \binom n0=\frac{n!}{0!\,n!}=1.

Merk skrivemåten i kongruenser: n! mod pn!\bmod p er en verdi (et tall mellom 00 og p−1p-1), mens n!≡c(modp)n!\equiv c\pmod p er en påstand. Boka holder de to atskilt, som i kap. 1.4.

Fortegnsregelen — tell de manglende faktorene
Mangler jj faktorer i m!m! sammenlignet med (p−1)!(p-1)!, er produktet av de negative restene
(−1)(−2)⋯(−j)=(−1)j⋅j!.(-1)(-2)\cdots(-j)=(-1)^{j}\cdot j!.

Altså:

jj (antall manglende)FortegnKoeffisienten blir
11−-−1!=−1-1!=-1
22+++2!=2+2!=2
33−-−3!=−6-3!=-6
44+++4!=24+4!=24
55−-−5!=−120-5!=-120

Dette er tabellen bak hele sjangeren, og den er verdt å kunne gjenskape — ikke pugge. Regelen er: antall manglende faktorer bestemmer fortegnet, og faktorialet av antallet bestemmer tallet.
Sammenhengen med Wilson blir da:
(−1)j⋅j!⋅m!≡−1(modp),der m=p−1−j.(-1)^{j}\cdot j!\cdot m!\equiv -1\pmod p,\qquad\text{der } m=p-1-j.
Bruk den som kontroll, ikke som snarvei. Skriv alltid ut de negative restene i besvarelsen — det er der føringspoengene ligger. Men når du har regnet, sjekk at koeffisienten stemmer med tabellen: mangler tre faktorer, SKAL koeffisienten være −6-6.
De tre første tilfellene, ferdig utledet
Ikke som tabell å pugge, men som gjenkjenning — og hver av dem utledes på stedet i to linjer.

(p−1)!≡−1(p-1)!\equiv -1 — Wilsons teorem selv.

(p−2)!≡1(p-2)!\equiv 1: én faktor mangler, koeffisienten er −1-1, så −(p−2)!≡−1-(p-2)!\equiv -1.

(p−3)!(p-3)!: to faktorer mangler, koeffisienten er 22, så 2 (p−3)!≡−12\,(p-3)!\equiv -1, altså
(p−3)!≡−1⋅2−1(modp).(p-3)!\equiv -1\cdot 2^{-1}\pmod p.
For p=83p=83 er 2−1=422^{-1}=42 (siden 2⋅42=84≡12\cdot 42=84\equiv 1), så (p−3)!=80!≡−42≡41(mod83)(p-3)!=80!\equiv -42\equiv 41\pmod{83} — nøyaktig det eksempel 3 fant.

(p−4)!(p-4)!: tre faktorer mangler, koeffisienten er −6-6, så −6 (p−4)!≡−1-6\,(p-4)!\equiv -1 og (p−4)!≡6−1(modp)(p-4)!\equiv 6^{-1}\pmod p.

Mønsteret: (p−1−j)!≡(−1)j+1⋅(j!)−1(modp)(p-1-j)!\equiv(-1)^{j+1}\cdot(j!)^{-1}\pmod p. Ikke pugg den formelen — den er lettere å gjøre feil enn å utlede. Kjør malen.

Kontrollrutinen i fakultetsoppgaver

Fem kontroller, til sammen under ett minutt. Under kode D er dette hele kvalitetssikringen din.

EtterKontrollFanger
valg av teoremer modulusen et primtall?Wilson brukt på 9191, 119119, 143143
de negative resteneer antallet manglende faktorer telt?fortegnsfeil
koeffisientenstemmer den med (−1)j⋅j!(-1)^j\cdot j!?regnefeil i det lille produktet
inversener c⋅c−1≡1(modp)c\cdot c^{-1}\equiv 1\pmod p?gal invers
sluttsvaretligger det mellom 00 og p−1p-1?glemt siste reduksjon

Og en sjette, som er gratis når den er mulig: finn samme rest på en annen vei. Har du 17!≡14(mod23)17!\equiv 14\pmod{23}, kan du sjekke 18!≡14⋅1818!\equiv 14\cdot 18 mot en direkte utregning — se oppgave 6.
Merk at du IKKE kan kontrollere ved å regne fakultetet. 80!80! har 119 siffer. Alle kontroller må ligge underveis.

Kode D-realisme: hva tallene ser ut som
StørrelseTypisk verdi på eksamen
primtallsmodulusen ppto- til tresifret, oftest 1111–150150
fakultetet m!m!mm er 22–66 mindre enn p−1p-1
antall manglende faktorer11–55
koeffisienten cc±1\pm 1, ±2\pm 2, ±6\pm 6, ±24\pm 24, ±120\pm 120
forfaktoren kkensifret

Bruk det som kontroll. Mangler det tolv faktorer, har du sannsynligvis lest oppgaven feil — koeffisienten ville blitt 12!12!, som ingen regner for hånd. Eksamensoppgavene legger fakultetet nær p−1p-1, nettopp fordi det er det som er regnbart.
Og bruk det når du lager egne øvingsoppgaver: velg et tosifret primtall pp, sett m=p−3m=p-3 eller m=p−4m=p-4, og velg en ensifret kk. Da vet du at oppgaven tar under fem minutter.
Wilson og Fermat — to helt ulike verktøy
Wilsons teoremFermats lille teorem
Handler omproduktet 1⋅2⋯(p−1)1\cdot 2\cdots(p-1)potenser ap−1a^{p-1}
Sier(p−1)!≡−1(modp)(p-1)!\equiv -1\pmod pap−1≡1(modp)a^{p-1}\equiv 1\pmod p
Vilkårpp primtallpp primtall og p∤ap\nmid a
Karakteriserer primtall?ja, begge veiernei — pseudoprimtall finnes
Brukes tilfakultet i en modulusstore eksponenter

Det de har til felles: begge krever primtallsmodulus, begge bevises ved å se på hva multiplikasjon gjør med restsystemet, og begge trenger invers-begrepet fra kap. 1.4.
Hvorfor de så ofte står i samme oppgave: signaturoppgaven i faget er «finn resten når k⋅m!+aNk\cdot m!+a^{N} deles på pp» — ett fakultet og én potens, altså ett Wilson og ett Fermat. Se kap. 2.5.
Den vanligste sammenblandingen: å tro at Wilson gir noe om potenser, eller at Fermat gir noe om fakultet. De rører ikke hverandres oppgaver.
Wilson i bevisoppgaver
To standardbruk der Wilsons teorem er byggeklossen, og begge kan komme som «vis at»-oppgaver (sjanger I).

1. p∣(p−1)!+1p\mid(p-1)!+1. Dette er teoremet skrevet som en delelighetspåstand, og det er ofte den formen oppgaven bruker. Beviset er å sitere teoremet og navngi det.

2. Kvadratet av (p−12)!\displaystyle \left(\frac{p-1}{2}\right)!. For et odde primtall pp er
((p−12)!)2≡(−1)(p+1)/2(modp).\left(\left(\tfrac{p-1}{2}\right)!\right)^{2}\equiv(-1)^{(p+1)/2}\pmod p.
Utledningen parer jj med p−jp-j i (p−1)!(p-1)!: da er
(p−1)!=∏j=1(p−1)/2j (p−j)≡∏j=1(p−1)/2(−j2)=(−1)(p−1)/2((p−12)!)2,(p-1)!=\prod_{j=1}^{(p-1)/2}j\,(p-j)\equiv\prod_{j=1}^{(p-1)/2}\left(-j^{2}\right)=(-1)^{(p-1)/2}\left(\left(\tfrac{p-1}{2}\right)!\right)^{2},
og Wilson gir at dette er ≡−1\equiv -1.

Kontroll for p=13p=13: 6!=720≡5(mod13)6!=720\equiv 5\pmod{13}, og 52=25≡12≡−15^2=25\equiv 12\equiv -1. Formelen gir (−1)7=−1(-1)^{7}=-1 ✓.

Hvor det leder: for p≡1(mod4)p\equiv 1\pmod 4 gir dette et tall hvis kvadrat er −1-1 modulo pp — altså at −1-1 er en kvadratisk rest. Det er supplementsregelen i Del 4, og Wilson er én av veiene dit.

Tidsbudsjettet for en fakultetsoppgave

Eksamen er 4 timer på omtrent 10 likt vektede delpunkt — ~24 minutter per delpunkt.

StegInnholdTid
primtallssjekkprøvedivisjon opp til p\sqrt p~1 min
(1)–(2)Wilson skrevet, manglende faktorer identifisert~1 min
(3)negative rester og det lille produktet~2 min
(4)inversen funnet og kontrollert~2 min
(5)ganging med kk, konklusjon~1 min

Til sammen ~7 minutter — under en tredel av budsjettet for ett delpunkt. Fakultetsoppgaver er billige poeng når trikset sitter.
Er du over 15 minutter, ligger det nesten alltid i inverssteget. Øv på å finne inverser til 2,3,6,242,3,6,24 og 120120 modulo tosifrede primtall — det er de fem koeffisientene som faktisk forekommer.

Skriveraden: hva som SKAL stå i besvarelsen

En fullgod besvarelse av «finn resten når k⋅m!k\cdot m! deles på pp» inneholder alle disse setningene:

1. at pp er et primtall (med prøvedivisjonen, om det ikke er åpenbart);
2. teoremnavnet: «ved Wilsons teorem er (p−1)!≡−1(modp)(p-1)!\equiv -1\pmod p»;
3. hvordan (p−1)!(p-1)! uttrykkes ved m!m! — de manglende faktorene skrevet ut;
4. hver manglende faktor omskrevet til en negativ rest;
5. kongruensen c⋅m!≡−1c\cdot m!\equiv -1, og inversen til cc med kontroll;
6. ganging med kk;
7. en konklusjonssetning med resten som et tall i 0,…,p−10,\dots,p-1.

Punkt 4 er selve trikset, og punkt 5 er der uttellingen oftest går tapt.

Selvtesten: kan noen som leser besvarelsen din, følge hvert steg fra (p−1)!(p-1)! til resten uten å regne selv? Da er føringen god nok.

Det som ikke holder: «7⋅80!≡38(mod83)7\cdot 80!\equiv 38\pmod{83}» alene. Riktig svar, ingen metode — og instruksen på hvert sett er at alle svar må begrunnes.

Hvorfor svaret er −1 og ikke +1
Et forståelseskort, fordi fortegnet er hele teoremet.

I produktet (p−1)!(p-1)! kollapser alle inversparene til 11. Igjen står de to selvinverse elementene: 11 og p−1p-1. Produktet av dem er
1⋅(p−1)≡1⋅(−1)=−1(modp).1\cdot(p-1)\equiv 1\cdot(-1)=-1\pmod p.

Altså kommer minustegnet fra det ene elementet p−1≡−1p-1\equiv -1. Hadde −1-1 ikke vært et eget element i restsystemet, ville produktet vært 11.

Sjekk mot p=2p=2: her er 1!=11!=1, og 1≡−1(mod2)1\equiv -1\pmod 2 — begge beskrivelser stemmer, fordi 11 og −1-1 er samme restklasse modulo 22. Teoremet holder, men er innholdsløst.

Hvorfor det er verdt å vite: husker du parringen, husker du fortegnet. Og fortegnet er den ene tingen studenter bytter om på i denne sjangeren.

Wilsons teorem i én oversikt
Det du serDet du gjørDet du får
(p−1)! mod p(p-1)!\bmod p, pp primtallWilsons teorem direkte−1≡p−1-1\equiv p-1
(p−2)! mod p(p-2)!\bmod pén faktor mangler11
k⋅m! mod pk\cdot m!\bmod p, m<p−1m<p-1malen i fem stegrest i 0,…,p−10,\dots,p-1
(n−1)! mod n(n-1)!\bmod n, nn sammensatt >4>4ikke Wilson00
3! mod 43!\bmod 4unntaket22
fakultet og potens i samme uttrykkWilson + Fermat paralleltsum av restene (kap. 2.5)

Første spørsmål er alltid: er modulusen et primtall? Er den ikke det, er du i den fjerde raden, og hele oppgaven er en annen.
Andre spørsmål: hvor mange faktorer mangler? Antallet bestemmer koeffisienten, og koeffisienten bestemmer hvilken invers du trenger.
Neste kapittel (kap. 2.4) tar det fjerde og siste av de fire store teoremene: det kinesiske restteoremet, som håndterer flere kongruenser samtidig.
De tre måtene Wilson spørres om på eksamen

1. Rest av k⋅m!k\cdot m! modulo pp. Malen i fem steg. Dette er den helt dominerende formen — 11 av 15 sett.
2. Som del av et sammensatt uttrykk, sammen med en potens. Samme mal, pluss en Fermat-reduksjon i parallell. Se kap. 2.5.
3. Teoretisk: «formuler Wilsons teorem», «forklar hvorfor det gjelder», eller «vis at det ikke gjelder for sammensatte tall». Da er det invers-parringen og kortet om sammensatte moduler som er svaret.

Merk hva som IKKE forekommer: oppgaver som ber deg bruke Wilsons teorem som primtallstest i praksis. Det er teoretisk mulig og praktisk ubrukelig, og arkivet spør ikke om det — bortsett fra som del av form 3, der poenget er å forstå forskjellen fra Fermat.

Og merk hva du bør gjøre først i alle tre: sjekke at modulusen er et primtall. Det er ett minutts arbeid som avgjør om resten er lovlig.

Hvorfor forkortingen i steg 4 er lovlig

Et hjemmelskort. I steg (4) av malen ganger du kongruensen c⋅m!≡−1(modp)c\cdot m!\equiv -1\pmod p med c−1c^{-1}. Hjemmelen er forkortingsregelen fra kap. 1.4: er gcd⁡(c,p)=1\gcd(c,p)=1, kan man forkorte med cc.

Og gcd⁡(c,p)=1\gcd(c,p)=1 holder alltid her. Koeffisienten cc er (opp til fortegn) et produkt 1⋅2⋯j1\cdot 2\cdots j av tall mellom 11 og p−1p-1. Primtallet pp deler ingen av dem, og etter Euklids lemma (kap. 1.1) deler det da ikke produktet.

Hvorfor det er verdt en setning i besvarelsen: det viser at du vet at forkorting modulo pp har en betingelse. I kap. 1.4 så du at forkorting uten betingelsen gir gale svar — 6⋅3≡6⋅8(mod10)6\cdot 3\equiv 6\cdot 8\pmod{10} mens 3≢83\not\equiv 8.

Med sammensatt modulus ville dette vært et reelt problem. Det er en grunn mer til at Wilson-sjangeren alltid har primtallsmodulus.

De små primtallene — kontroller mot dem

Når du er usikker på om du har brukt trikset riktig, prøv det på p=5p=5 eller p=7p=7. Der kan du regne alt eksakt, og du oppdager feilen med en gang.

pp(p−1)!(p-1)!(p−2)!(p-2)!(p−3)!(p-3)!
5524≡4≡−124\equiv 4\equiv -16≡16\equiv 12≡22\equiv 2
77720≡6≡−1720\equiv 6\equiv -1120≡1120\equiv 124≡324\equiv 3
1111≡−1\equiv -1≡1\equiv 140 320≡540\,320\equiv 5

Sjekk mønsteret fra kortet «De tre første tilfellene»: (p−3)!≡−2−1(modp)(p-3)!\equiv -2^{-1}\pmod p.
- p=5p=5: 2−1=32^{-1}=3 (siden 2⋅3=6≡12\cdot 3=6\equiv 1), og −3≡2(mod5)-3\equiv 2\pmod 5 ✓ — stemmer med tabellen.
- p=7p=7: 2−1=42^{-1}=4, og −4≡3(mod7)-4\equiv 3\pmod 7 ✓.
- p=11p=11: 2−1=62^{-1}=6, og −6≡5(mod11)-6\equiv 5\pmod{11} ✓ (og 8!=40 320=11⋅3 665+58!=40\,320=11\cdot 3\,665+5).

Det er slik du bruker små primtall: ikke som pensum, men som prøvestein. Under kode D finnes ingen fasit i rommet, og en formel du kan teste på p=7p=7 i hodet, er en formel du kan stole på.

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.