2.4 Det kinesiske restteoremet (CRT)

System av lineære kongruenser løst med CRT: sjekk parvis primiskhet, forenkle hver kongruens, og løs med enten CRT-formelen (Nₖ = M/mₖ) ELLER suksessiv innsetting — begge fullgode, pluss ikke-primisk-modul-ryddingen.

60 min

6 oppgaver

Det kinesiske restteoremet (CRT)

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

1.4Lineære kongruenser (ax ≡ b mod m)

Det kinesiske restteoremet forekommer i 12 av 15 sett — 80 %, vanligvis som oppgave 2 eller 3.

Det er den fjerde av de fire store teoremene, og det har sin egen sjangerbokstav i boka: sjanger C — system av kongruenser (sjangerbokstavene er bokas egne forkortelser, forklart i kap. 0.1).

Formen oppgaven har	Frekvens
System av 2–3 kongruenser, «finn det minste positive $x$ »	12 av 15 sett
Moduler som ikke er parvis relativt primiske (rydding eller «ingen løsning»)	forekommer regelmessig
CRT brukt til å splitte en restberegning med sammensatt modulus	vanlig, se kap. 2.5
CRT i korrekthetsbeviset for RSA	kap. 3.1

Fasitens grep: sjekk at modulene er parvis relativt primiske (det påpekes eksplisitt i fasitene), forenkle hver kongruens først, og løs — enten med CRT-formelen eller med suksessiv innsetting.
Begge metodene er fullgode, og løsningsforslagene i arkivet bruker dem om hverandre. Boka fører derfor begge komplett, og sier hvilken som er raskest når. Under kode D er suksessiv innsetting sikkerhetsnettet: den krever ikke at formelen sitter.
Prioritet: høyeste. 80 % frekvens, kjent oppskrift, og et delpunkt du kan hente i under et kvarter når metoden sitter.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater — bare en enkel kalkulator.

Må sitte utenat:

- CRT-formelen: $M=m_1m_2\cdots m_k$ , $N_j=M/m_j$ , løs $N_jx_j\equiv 1\pmod{m_j}$ , og sett $x\equiv\sum_j b_jN_jx_j\pmod M$
- vilkåret: modulene må være parvis relativt primiske
- at løsningen er entydig modulo $M$ — én restklasse, ikke ett tall
- splittingsregelen $a\equiv b\pmod{mn}\iff a\equiv b\pmod m$ og $a\equiv b\pmod n$ (når $\gcd(m,n)=1$ )

Utledes på stedet:

- Suksessiv innsetting. Skriv den ene kongruensen som $x=b+mt$ , sett inn i den neste, løs for $t$ , og gjenta. Ingen formel å huske — bare kongruensregning du alt kan fra kap. 1.4. Metoden står ferdig ført i løkke 4, og den er sikkerhetsnettet ditt under kode D: glipper formelen i eksamensrommet, kommer du like langt med innsetting, og det gir full uttelling.
- Kriteriet for løsbarhet når modulene ikke er primiske: systemet er løsbart nøyaktig når $\gcd(m_i,m_j)$ deler $b_i-b_j$ for alle par. Utledningen er to linjer og står i løkke 5.

Selvtest, tre minutter: dekk til siden og skriv ned (1) CRT-formelen med alle symbolene forklart, og (2) løs systemet $x\equiv 2\pmod 3$ , $x\equiv 3\pmod 5$ ved suksessiv innsetting. Får du begge, sitter kjernen.

Prosedyrer pugges ved å kjøres. Regn tre systemer med begge metoder.

Forkunnskaper

Fra boka: kap. 1.4 (kongruens, lineær kongruens, modulær invers, splittingsregelen) og kap. 1.2 (Euklids algoritme — du trenger den til inversene).

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

Modulær invers. Er $\gcd(a,m)=1$ , finnes $u$ med $au\equiv 1\pmod m$ , funnet med Euklids algoritme baklengs. Dette er den ene regneoperasjonen CRT-formelen krever.

Lineær kongruens. $ax\equiv b\pmod m$ er løsbar nøyaktig når $d=\gcd(a,m)$ deler $b$ , og har da $d$ inkongruente løsninger modulo $m$ .

Å splitte modulusen. Når $\gcd(m,n)=1$ :
$a\equiv b\pmod{mn}\iff a\equiv b\pmod m\ \text{ og }\ a\equiv b\pmod n.$
Dette er halvparten av CRT allerede — retningen fra høyre til venstre er nettopp «to kongruenser bestemmer én modulo produktet».

Fra videregående er ingenting påkrevd.

Tre kalendere som møtes

En bussrute går hver 4. dag, en søppelbil hver 6. dag og et marked arrangeres hver 7. dag. I dag er det buss. Søppelbilen kom i går, og markedet var for to dager siden. Hvor mange dager er det til alle tre faller på samme dag?

Det er et system av kongruenser. Kaller vi svaret $x$ (antall dager fra i dag), skal $x$ gi bestemte rester ved divisjon med $4$ , $6$ og $7$ samtidig — én betingelse per kalender.

Spørsmålet er om et slikt system alltid har en løsning, og hvordan man finner den uten å prøve alle tall. Svaret er det kinesiske restteoremet, og det er over halvannet tusen år gammelt: den kinesiske matematikeren Sun Zi formulerte et slikt problem i det 3. århundre — «det finnes et ukjent antall ting; delt på tre blir det to til rest, delt på fem blir det tre til rest, delt på sju blir det to til rest».

To ting teoremet forteller oss, og som er verdt å skille:

- at en løsning finnes, og at den er entydig modulo produktet av modulene — forutsatt at modulene er parvis relativt primiske;
- hvordan du finner den, med to ulike metoder som gir samme svar.

Legg merke til at eksempelet over har et problem: $\gcd(4,6)=2$ , så modulene er ikke parvis relativt primiske. Da gjelder ikke teoremet direkte, og systemet kan være uløselig. Det tilfellet er løkke 5 — og det er nettopp den varianten arkivet er glad i.

Tidsanslag for kapitlet: ~60 minutter lesetid, fordelt på seks løkker à 8–12 minutter. Regner du med penn underveis, legg til omtrent halvparten.

Løkke 1: Teoremet og vilkåret

~9 minutter.

Vi starter med hva teoremet sier, og med det ene vilkåret som avgjør om det kan brukes.

System av kongruenser

x\equiv b_1\pmod{m_1},\quad x\equiv b_2\pmod{m_2},\quad\dots,\quad x\equiv b_k\pmod{m_k}.

Parvis relativt primiske moduler

m_1,\dots,m_k

📜Det kinesiske restteoremet

m_1,m_2,\dots,m_k

være parvis relativt primiske positive tall, og sett

M=m_1m_2\cdots m_k

. Da har systemet

x\equiv b_1\pmod{m_1},\quad\dots,\quad x\equiv b_k\pmod{m_k}

nøyaktig én løsning modulo $M$ — uansett hva restene

b_j

er.

Bevis av entydigheten. Anta at $x$ og $y$ begge løser systemet. Da er $x\equiv y\pmod{m_j}$ for hver $j$ , altså $m_j\mid(x-y)$ for alle $j$ . Siden modulene er parvis relativt primiske, deler produktet: $M\mid(x-y)$ , altså $x\equiv y\pmod M$ . (Det siste er splittingsregelen fra kap. 1.4, brukt gjentatt.) $\blacksquare$

Bevis av eksistensen — konstruktivt, og det gir formelen. For hver $j$ , sett
$N_j=\frac{M}{m_j}=\prod_{i\ne j}m_i.$
Da er $\gcd(N_j,m_j)=1$ : hver faktor i $N_j$ er relativt primisk til $m_j$ , og da er produktet det også. Altså finnes inversen $x_j$ med
$N_jx_j\equiv 1\pmod{m_j}$
(kap. 1.4). Sett nå
$x=b_1N_1x_1+b_2N_2x_2+\dots+b_kN_kx_k.$

Hvorfor denne $x$ virker: se på kongruensen modulo $m_1$ . Hvert ledd $b_jN_jx_j$ med $j\ne 1$ har faktoren $N_j$ , som inneholder $m_1$ — så alle de leddene er $\equiv 0\pmod{m_1}$ . Bare det første leddet står igjen, og der er $N_1x_1\equiv 1$ , så
$x\equiv b_1N_1x_1\equiv b_1\cdot 1=b_1\pmod{m_1}.$
Samme argument gjelder for hver $j$ . $\blacksquare$

Intuisjon: hvert ledd i summen er en «bryter» som er tent modulo sin egen modulus og slukket modulo alle de andre. Du bygger løsningen ved å sette hver bryter til den resten du vil ha.

Teoremet og formelen må sitte utenat, og teoremet må navngis. Fasitene skriver «ved det kinesiske restteoremet».

Entydig modulo M — hva svaret er

M

✏️CRT-formelen på tre kongruenser

Finn det minste positive heltallet

x

som oppfyller

$x\equiv 2\pmod 5,\qquad x\equiv 3\pmod 7,\qquad x\equiv 4\pmod 9.$

Parvis primiskhet, kommentert først.

\gcd(5,7)=1

\gcd(5,9)=1

\gcd(7,9)=1

— modulene er parvis relativt primiske. Da har systemet, ved det kinesiske restteoremet, nøyaktig én løsning modulo

M=5\cdot 7\cdot 9=315

Sett opp $N_k$ og løs $N_kx_k\equiv 1\pmod{m_k}$ :

$k$	$m_k$	$b_k$	$N_k=M/m_k$	$N_k\bmod m_k$	$x_k$ med $N_kx_k\equiv 1$
$1$	$5$	$2$	$63$	$3$	$2$
$2$	$7$	$3$	$45$	$3$	$5$
$3$	$9$	$4$	$35$	$8$	$8$

Sett sammen:

x\equiv 2\cdot 63\cdot 2 + 3\cdot 45\cdot 5 + 4\cdot 35\cdot 8 = 2\,047\pmod{315}.

Reduksjon:

2\,047 = 315\cdot 6 + 157

, så

x\equiv 157\pmod{315}

.
Kontroll — sett inn i ALLE kongruensene:

157 = 5\cdot 31 + 2

✓;

157 = 7\cdot 22 + 3

✓;

157 = 9\cdot 17 + 4

✓.

Svar på spørsmålet som ble stilt: det minste positive tallet er $\boxed{157}$ , og hele løsningsmengden er $x\equiv 157\pmod{315}$ , altså $x=157+315t$ for $t\in\mathbb{Z}$ .

Legg merke til at inversene var det eneste virkelige arbeidet: tre små kongruenser $N_jx_j\equiv 1\pmod{m_j}$ , hver løst ved å prøve små tall. Med tosifrede moduler er det raskere enn Euklids algoritme — men Euklid virker alltid, og begge er fullgode.

Og legg merke til kontrollen: den er obligatorisk her. Setter du inn i alle kongruensene, oppdager du hver eneste regnefeil du kan ha gjort — og under kode D er det den eneste kontrollen du har.

📝Oppgave 1

a) Er modulene

4

9

25

parvis relativt primiske?
b) Er modulene

6

10

15

parvis relativt primiske?
c) Hvor mange løsninger modulo

M

har et system med parvis relativt primiske moduler?

Løkke 2: Formelen som prosedyre

~10 minutter.

Beviset ga oss formelen. Nå gjør vi den til en oppskrift du kan kjøre under tidspress, med en fast bokføring.

— naturlig pausepunkt —

CRT-formelen — oppskriften i fem steg

x\equiv b_j\pmod{m_j}

Hva

N_j

x_j

er — og hvorfor de virker

N_j=\frac{M}{m_j}=\text{produktet av ALLE de andre modulene}.

📝Oppgave 2

Løs systemet

$x\equiv 1\pmod 4,\qquad x\equiv 2\pmod 5,\qquad x\equiv 3\pmod 7$

med CRT-formelen, og oppgi det minste positive tallet.

Løkke 3: Forenkle først

~8 minutter.

Eksamensoppgavene gir sjelden systemet på formen $x\equiv b\pmod m$ . Det står oftere $4x\equiv 3\pmod 7$ , og da må hver kongruens løses for seg før systemet settes sammen.

Forenkle hver kongruens før du bruker CRT

a_jx\equiv c_j\pmod{m_j}

✏️System med koeffisienter foran x

Løs systemet

$3x\equiv 2\pmod 5,\qquad 4x\equiv 3\pmod 7,$

og oppgi det minste positive tallet.

Steg 1: forenkle hver kongruens.

Første kongruens, $3x\equiv 2\pmod 5$ . Her er $\gcd(3,5)=1$ , som deler $2$ , så kongruensen er løsbar med nøyaktig én inkongruent løsning modulo $5$ (kap. 1.4). Inversen til $3$ modulo $5$ er $2$ , siden $3\cdot 2=6\equiv 1$ . Vi ganger begge sider med $2$ :
$x\equiv 2\cdot 2=4\pmod 5.$

Andre kongruens, $4x\equiv 3\pmod 7$ . Her er $\gcd(4,7)=1$ , som deler $3$ , så én løsning modulo $7$ . Inversen til $4$ modulo $7$ er $2$ , siden $4\cdot 2=8\equiv 1$ . Vi ganger med $2$ :
$x\equiv 2\cdot 3=6\pmod 7.$

Steg 2: nå har vi et rent CRT-system.
$x\equiv 4\pmod 5,\qquad x\equiv 6\pmod 7.$

Parvis primiskhet, kommentert først. $\gcd(5,7)=1$ — modulene er parvis relativt primiske. Da har systemet, ved det kinesiske restteoremet, nøyaktig én løsning modulo $M=5\cdot 7=35$ .

Sett opp $N_k$ og løs $N_kx_k\equiv 1\pmod{m_k}$ :

$k$	$m_k$	$b_k$	$N_k=M/m_k$	$N_k\bmod m_k$	$x_k$ med $N_kx_k\equiv 1$
$1$	$5$	$4$	$7$	$2$	$3$
$2$	$7$	$6$	$5$	$5$	$3$

Sett sammen:

x\equiv 4\cdot 7\cdot 3 + 6\cdot 5\cdot 3 = 174\pmod{35}.

Reduksjon:

174 = 35\cdot 4 + 34

, så

x\equiv 34\pmod{35}

Kontroll — sett inn i ALLE kongruensene: $34 = 5\cdot 6 + 4$ ✓; $34 = 7\cdot 4 + 6$ ✓.

Det minste positive tallet er $\boxed{34}$ , og løsningsmengden er $x\equiv 34\pmod{35}$ .

Kontroll mot de opprinnelige kongruensene — det er dem oppgaven stilte, så det er dem vi må sjekke: $3\cdot 34=102=5\cdot 20+2$ ✓, og $4\cdot 34=136=7\cdot 19+3$ ✓.

Merk at $34\equiv -1\pmod{35}$ . Det er en pen kontroll: $3\cdot(-1)=-3\equiv 2\pmod 5$ ✓ og $4\cdot(-1)=-4\equiv 3\pmod 7$ ✓. Ligger løsningen nær $M$ , er det ofte lettere å regne med den negative representanten.

📝Oppgave 3

Løs systemet

$2x\equiv 1\pmod 5,\qquad 3x\equiv 2\pmod 7,\qquad x\equiv 5\pmod 9,$

og oppgi det minste positive tallet.

Løkke 4: Suksessiv innsetting — den andre veien

~11 minutter.

Nå den metoden som ikke krever at formelen sitter. Den bruker bare kongruensregning fra kap. 1.4, og fasitene i arkivet regner den som fullt likeverdig med formelen.

Under kode D er dette sikkerhetsnettet ditt: glipper formelen, kommer du like langt her.

Suksessiv innsetting — oppskriften

x=b_1+m_1t

Hvilken metode når?

k

CRT-formelen	Suksessiv innsetting
Krever	at formelen sitter	bare kongruensregning
Arbeid ved 2 kongruenser	2 inverser	1 invers
Arbeid ved 3–4 kongruenser	$k$ inverser, alle små	$k-1$ runder
Alle ledd uavhengige?	ja — en feil rammer ett ledd	nei — feil forplanter seg
Passer når restene endres	ja, $N_jx_j$ kan gjenbrukes	nei, alt må gjøres på nytt
Trygg under kode D	krever pugging	krever ingenting

✏️Samme system, andre metode: suksessiv innsetting

Løs systemet fra eksempel 1 på nytt, med suksessiv innsetting:

$x\equiv 2\pmod 5,\qquad x\equiv 3\pmod 7,\qquad x\equiv 4\pmod 9.$

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 4\pmod{9}$ skriver vi

$x = 4 + 9t,\qquad t\in\mathbb{Z}.$

Setter vi dette inn i $x\equiv 3\pmod{7}$ , får vi

$4 + 9t\equiv 3\pmod{7}\quad\Longleftrightarrow\quad 2t\equiv 6\pmod{7}.$

Inversen til $2$ modulo $7$ er $4$ (kontroll: $2\cdot 4 = 8 = 7\cdot 1+1$ ), så $t\equiv 4\cdot 6 = 24\equiv 3\pmod{7}$ .

Da er $t = 3 + 7s$ , og

$x = 4 + 9(3 + 7s) = 31 + 63s,$

altså $x\equiv 31\pmod{63}$ .

Setter vi dette inn i $x\equiv 2\pmod{5}$ , får vi

$31 + 63s\equiv 2\pmod{5}\quad\Longleftrightarrow\quad 3s\equiv 1\pmod{5}.$

Inversen til $3$ modulo $5$ er $2$ (kontroll: $3\cdot 2 = 6 = 5\cdot 1+1$ ), så $s\equiv 2\cdot 1 = 2\equiv 2\pmod{5}$ .

Da er $s = 2 + 5u$ , og

$x = 31 + 63(2 + 5u) = 157 + 315u,$

altså $x\equiv 157\pmod{315}$ .

Kontroll — sett inn i ALLE kongruensene: $157 = 5\cdot 31 + 2$ ✓; $157 = 7\cdot 22 + 3$ ✓; $157 = 9\cdot 17 + 4$ ✓. Samme svar som formelen gir.

Sluttsvar: $x\equiv 157\pmod{315}$ — nøyaktig samme svar som CRT-formelen ga i eksempel 1, som det skal være.

Sammenligning av de to veiene på samme oppgave:

- Formelen krevde tre inverser (én per modulus) og én stor sum. Alle tre leddene var uavhengige, så en regnefeil rammer bare ett ledd — det er lett å finne.
- Innsetting krevde to inverser og to runder. Tallene ble aldri store, men en feil i første runde forplanter seg til andre.

Begge er fullgode, og de gir samme svar. Å kjøre den ene som kontroll på den andre koster tre minutter og er den sikreste kontrollen som finnes i denne sjangeren.

📝Oppgave 4

Løs systemet

$x\equiv 3\pmod 8,\qquad x\equiv 4\pmod{11}$

a) med suksessiv innsetting;
b) med CRT-formelen, som kontroll.

Løkke 5: Når modulene ikke er parvis relativt primiske

~12 minutter.

Her er varianten arkivet er glad i. Vilkåret i teoremet svikter, og da er det tre muligheter: systemet er uløselig, det kan ryddes til et lovlig system, eller det har løsninger med en annen periode.

— naturlig pausepunkt —

Løsbarhetskriteriet når modulene deler en faktor

x\equiv b_1\pmod{m_1},\qquad x\equiv b_2\pmod{m_2}

Rydding: å splitte en modulus i primtallspotenser

\gcd(m,n)=1

✏️Rydding: moduler med felles faktor

Løs systemet

$x\equiv 5\pmod 8,\qquad x\equiv 13\pmod{20}.$

Steg 1: sjekk vilkåret — og det svikter.

\gcd(8,20)=4\ne 1

, så modulene er ikke relativt primiske, og CRT-formelen kan ikke brukes direkte.

Steg 2: er systemet i det hele tatt løsbart? Kriteriet er at $\gcd(8,20)=4$ deler differansen $13-5=8$ . Og $4\mid 8$ ✓, så systemet har løsninger.

Steg 3: rydd ved å splitte i primtallspotenser. Vi faktoriserer modulene: $8=2^3$ og $20=2^2\cdot 5$ . Andre kongruens splittes etter splittingsregelen (lovlig, siden $\gcd(4,5)=1$ ):
$x\equiv 13\pmod{20}\iff x\equiv 13\equiv 1\pmod 4\ \text{ og }\ x\equiv 13\equiv 3\pmod 5.$

Nå har vi tre kongruenser:
$x\equiv 5\pmod 8,\qquad x\equiv 1\pmod 4,\qquad x\equiv 3\pmod 5.$

Steg 4: rydd bort den overflødige. De to første handler om samme primtall ( $2$ ). Er de forenlige? Fra $x\equiv 5\pmod 8$ følger $x\equiv 5\equiv 1\pmod 4$ — som er nøyaktig den andre kongruensen. De er forenlige, og den svakere ( $\bmod 4$ ) er overflødig; vi beholder den sterkere ( $\bmod 8$ ).

Steg 5: nå er systemet lovlig.
$x\equiv 5\pmod 8,\qquad x\equiv 3\pmod 5.$

Parvis primiskhet, kommentert først. $\gcd(8,5)=1$ — modulene er parvis relativt primiske. Da har systemet, ved det kinesiske restteoremet, nøyaktig én løsning modulo $M=8\cdot 5=40$ .

Sett opp $N_k$ og løs $N_kx_k\equiv 1\pmod{m_k}$ :

$k$	$m_k$	$b_k$	$N_k=M/m_k$	$N_k\bmod m_k$	$x_k$ med $N_kx_k\equiv 1$
$1$	$8$	$5$	$5$	$5$	$5$
$2$	$5$	$3$	$8$	$3$	$2$

Sett sammen:

x\equiv 5\cdot 5\cdot 5 + 3\cdot 8\cdot 2 = 173\pmod{40}.

Reduksjon:

173 = 40\cdot 4 + 13

, så

x\equiv 13\pmod{40}

Kontroll — sett inn i ALLE kongruensene: $13 = 8\cdot 1 + 5$ ✓; $13 = 5\cdot 2 + 3$ ✓.

Kontroll mot de OPPRINNELIGE kongruensene: $13=8+5$ , så $13\equiv 5\pmod 8$ ✓. Og $13=20\cdot 0+13$ , så $13\equiv 13\pmod{20}$ ✓.

Sluttsvar: $x\equiv 13\pmod{40}$ . Det minste positive tallet er $\boxed{13}$ .

Merk perioden: $40=\operatorname{lcm}(8,20)$ , ikke $8\cdot 20=160$ . Det er alltid slik når modulene har en felles faktor — og det er en kontroll verdt å gjøre: er perioden din $160$ , har du brukt formelen der den ikke gjelder.

✏️Et system uten løsning

Vis at systemet

$x\equiv 3\pmod{12},\qquad x\equiv 7\pmod{18}$

ikke har noen løsning.

Steg 1: sjekk vilkåret.

12=2^2\cdot 3

18=2\cdot 3^2

, så

\gcd(12,18)=2\cdot 3=6\ne 1.

Modulene er ikke relativt primiske, så CRT-formelen gjelder ikke, og vi må undersøke løsbarheten.

Steg 2: bruk løsbarhetskriteriet. Systemet er løsbart nøyaktig når $\gcd(12,18)=6$ deler differansen $3-7=-4$ . Men $6\nmid 4$ , så systemet har ingen løsning.

Steg 3: samme konklusjon som en direkte motsigelse — den formen fasitene ofte fører, og den som er lettest å lese:

Anta at $x$ løser systemet. Fra $x\equiv 3\pmod{12}$ følger, siden $6\mid 12$ , at
$x\equiv 3\pmod 6.$
Fra $x\equiv 7\pmod{18}$ følger, siden $6\mid 18$ , at
$x\equiv 7\equiv 1\pmod 6.$
Men da er $3\equiv x\equiv 1\pmod 6$ , altså $6\mid 2$ — og det er umulig. Antagelsen kan derfor ikke holde, og systemet har ingen løsning. $\blacksquare$

Kontroll ved å prøve: tallene $\equiv 3\pmod{12}$ er $3,15,27,39,51,63,\dots$ , og restene deres modulo $18$ er $3,15,9,3,15,9,\dots$ — bare $3$ , $9$ og $15$ opptrer, aldri $7$ ✓.

Sluttsvar: systemet har ingen løsning, fordi $\gcd(12,18)=6$ ikke deler $3-7$ .

Legg merke til hvordan motsigelsen ble ført: antagelsen skrevet ut, konsekvensene trukket, og en klar umulighetssetning til slutt. Det er bevisstandarden i dette faget, og den gjelder også i en regneoppgave.

Og legg merke til at «ingen løsning» er et fullgodt svar. Det er en av variantene arkivet bruker, og den prøver om du sjekker vilkåret i stedet for å regne mekanisk.

📝Oppgave 5

For hvert av systemene: avgjør om det har løsninger, og finn i så fall alle.

a) $x\equiv 4\pmod 6$ og $x\equiv 7\pmod {15}$
b) $x\equiv 2\pmod 9$ og $x\equiv 5\pmod{12}$

Løkke 6: CRT som regneverktøy — splitt beregningen

~10 minutter.

Til slutt den bruken som binder Del 2 sammen: CRT er ikke bare en oppgavetype, det er verktøyet som gjør en beregning modulo et sammensatt tall til to enklere beregninger.

Å splitte en restberegning med CRT

a^{N}\bmod n

✏️Eksamensnivå: 3^100 modulo 91, splittet med CRT

Finn resten når $3^{100}$ deles på $91$ .

Steg 1: faktoriser modulusen.

91=7\cdot 13

— merk at

91

ikke er et primtall, selv om det ser slik ut. (Prøvedivisjon:

91/7=13

Steg 2: velg strategi. To veier er mulige, og begge er fullgode:

- Direkte med Euler: $\phi(91)=6\cdot 12=72$ , og $\gcd(3,91)=1$ , så $3^{100}\equiv 3^{28}\pmod{91}$ — en eksponent på $28$ krever fem kvadrater.
- Splittet med CRT: modulo $7$ og modulo $13$ blir eksponentene mye mindre, fordi $p-1$ er $6$ og $12$ .

Vi tar den splittede veien, som er den fasitene bruker når modulusen er et produkt av to primtall.

Steg 3: modulo $7$ . $7$ er et primtall og $7\nmid 3$ ✓, så fra Fermats lille teorem er $3^{6}\equiv 1\pmod 7$ , og eksponenten reduseres modulo $6$ :
$100=6\cdot 16+4,\qquad\text{så}\qquad 3^{100}\equiv 3^{4}=81\equiv 4\pmod 7,$
siden $81=7\cdot 11+4$ .

Steg 4: modulo $13$ . $13$ er et primtall og $13\nmid 3$ ✓, så fra Fermats lille teorem er $3^{12}\equiv 1\pmod{13}$ , og eksponenten reduseres modulo $12$ :
$100=12\cdot 8+4,\qquad\text{så}\qquad 3^{100}\equiv 3^{4}=81\equiv 3\pmod{13},$
siden $81=13\cdot 6+3$ .

Steg 5: sett sammen med CRT. Vi skal finne $x$ med
$x\equiv 4\pmod 7,\qquad x\equiv 3\pmod{13}.$
Modulene er parvis relativt primiske ( $\gcd(7,13)=1$ ), så ved det kinesiske restteoremet finnes nøyaktig én løsning modulo $91$ .

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 3\pmod{13}$ skriver vi

$x = 3 + 13t,\qquad t\in\mathbb{Z}.$

Setter vi dette inn i $x\equiv 4\pmod{7}$ , får vi

$3 + 13t\equiv 4\pmod{7}\quad\Longleftrightarrow\quad 6t\equiv 1\pmod{7}.$

Inversen til $6$ modulo $7$ er $6$ (kontroll: $6\cdot 6 = 36 = 7\cdot 5+1$ ), så $t\equiv 6\cdot 1 = 6\equiv 6\pmod{7}$ .

Da er $t = 6 + 7s$ , og

$x = 3 + 13(6 + 7s) = 81 + 91s,$

altså $x\equiv 81\pmod{91}$ .

Kontroll — sett inn i ALLE kongruensene: $81 = 7\cdot 11 + 4$ ✓; $81 = 13\cdot 6 + 3$ ✓. Samme svar som formelen gir.

Konklusjon. Resten når $3^{100}$ deles på $91$ , er $\boxed{81}$ .

Kontroll på den andre veien. Vi lovet at Euler-veien gir samme svar: $3^{100}\equiv 3^{28}\pmod{91}$ . Kvadrer-og-multipliser med $28=16+8+4$ : $3^2=9$ , $3^4=81$ , $3^8\equiv 81^2=6\,561$ og $6561=91\cdot 72+9$ , altså $3^8\equiv 9$ ; $3^{16}\equiv 9^2=81$ . Da er
$3^{28}=3^{16}\cdot 3^{8}\cdot 3^{4}\equiv 81\cdot 9\cdot 81\pmod{91}.$
Vi regner: $81\cdot 9=729=91\cdot 8+1$ , så $\equiv 1$ ; og $1\cdot 81=81$ . Samme svar ✓.

To uavhengige veier til $81$ er så sikker kontroll som du får under kode D. Merk også at $81=3^4$ — det er ikke tilfeldig: $3^{100}$ og $3^4$ er kongruente modulo $91$ , fordi $\operatorname{lcm}(6,12)=12$ deler $96=100-4$ .

📝Oppgave 6

a) Finn resten når

2^{1\,000}

deles på

77

, ved å splitte modulusen.
b) Kontroller svaret ved å regne direkte modulo

77

med Eulers teorem.

Typiske feil

Fem feil står for nesten alt som går galt i sjanger C, og den første er den mest belagte.

- CRT-formelen brukt uten å sjekke parvis primiskhet. Har modulene en felles faktor, gjelder ikke formelen, og svaret blir galt — ofte med en periode som er for stor. Kontrollen: står setningen «modulene er parvis relativt primiske» i besvarelsen din? Og er perioden din $\operatorname{lcm}$ eller produktet? De skal være like, ellers har du brukt formelen der den ikke gjelder.

- Glemt å forenkle først. Står det $4x\equiv 3\pmod 7$ , må det bli $x\equiv 6\pmod 7$ før systemet settes sammen. Kontrollen: har alle kongruensene formen $x\equiv b_j$ når du starter formelen?

- Regnefeil i inversene $N_jx_j\equiv 1$ . Dette er der de fleste tallfeilene oppstår. Kontrollen: gang $N_j$ med $x_j$ og se at du får rest $1$ ved divisjon med $m_j$ . Fem sekunder per rad.

- Glemt «minste positive». Spør oppgaven om det minste positive tallet, er svaret et tall i $1,\dots,M$ — ikke restklassen alene, og ikke et negativt tall. Kontrollen: les oppgaveteksten en gang til til slutt.

- Blandet sammen $b_j$ -ene i formelen. Å gange $b_1$ med $N_2x_2$ . Kontrollen: bruk tabellen med én rad per kongruens, og hold $b_j$ , $N_j$ og $x_j$ på samme rad.

- Forkortet uten å dele modulusen. I suksessiv innsetting blir $3t\equiv 3\pmod 6$ til $t\equiv 1\pmod 2$ , ikke $t\equiv 1\pmod 6$ . Kontrollen: er $\gcd(\text{koeffisient},\text{modulus})>1$ , skal modulusen deles også.

Begrepsbank

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

Kortene dekker begge metodene, vilkåret, ikke-primisk-varianten og kontrollrutinene. Under kode D er de eksamensverktøy: det finnes ingen formelsamling å slå opp CRT-formelen i.

Notasjonen i CRT — hold symbolene fra hverandre

m_j

Symbol	Hva det er	Typisk størrelse
$m_j$	modulene i systemet	ensifret til tosifret
$b_j$	restene, høyresidene	mindre enn $m_j$
$M$	produktet $m_1m_2\cdots m_k$	to- til firesifret
$N_j$	$M/m_j$ , produktet av de andre modulene	to- til tresifret
$x_j$	inversen til $N_j$ modulo $m_j$	mindre enn $m_j$
$c$	løsningen, i $0\le c<M$	to- til firesifret

Hverdagsankeret: kalendere og syklusar

7

CRT med flere enn tre kongruenser

k

Hvor CRT møter RSA

(m^{e})^{d}\equiv m

Hvorfor svaret er én restklasse, ikke ett tall

M

Oppgavetype	Svaret er
diofantisk likning $ax+by=c$	en parametrisert familie, $x=x_0+(b/d)t$
lineær kongruens $ax\equiv b\pmod m$	$d=\gcd(a,m)$ restklasser modulo $m$
CRT-system, parvis primiske moduler	én restklasse modulo $M$
CRT-system, moduler med felles faktor	én restklasse modulo $\operatorname{lcm}$ , eller ingen

Kontrollrutinen i sjanger C

x\equiv b_j

Etter	Kontroll	Fanger
oppsettet	er modulene parvis relativt primiske?	formelen brukt ulovlig
forenklingen	har alle kongruenser formen $x\equiv b_j$ ?	glemt invers-ganging
hver rad i tabellen	er $N_jx_j\equiv 1\pmod{m_j}$ ?	gal invers
sluttsvaret	sett inn i ALLE kongruensene	alle regnefeil
helt til slutt	er perioden $M$ (eller $\operatorname{lcm}$ )? og er svaret det minste positive, om det spørres?	glemt periode, glemt spørsmålet

Kode D-realisme: hva tallene ser ut som

m_j

Størrelse	Typisk verdi på eksamen
antall kongruenser	2 eller 3
modulene $m_j$	ensifret til tosifret ( $3$ – $25$ )
$M$	to- til firesifret (under ~ $1\,000$ )
inversene $x_j$	ensifret, funnet ved å prøve små tall
koeffisienter foran $x$	ensifret, ofte $2$ – $6$

Tidsbudsjettet for en CRT-oppgave

M

Steg	Innhold	Tid
oppsett	primiskhetssjekk, $M$	~2 min
forenkling	hver kongruens til $x\equiv b_j$	~3 min
$N_j$ og inversene	én rad per kongruens	~5 min
sammensetting	summen, redusert modulo $M$	~2 min
kontroll	innsetting i alle kongruensene	~1 min

Skriveraden: hva som SKAL stå i besvarelsen

\gcd(m_i,m_j)=1

Hvorfor teoremet heter det det heter

23

Sjanger C i én oversikt

x\equiv b_j\pmod{m_j}

Det du ser	Det du gjør	Svaret er
$x\equiv b_j\pmod{m_j}$ , parvis primiske	formelen eller innsetting	én restklasse modulo $M$
koeffisient foran $x$	forenkle først (gang med invers)	som over
moduler med felles faktor $d$ , $d\mid(b_1-b_2)$	rydd, eller sett inn suksessivt	én restklasse modulo $\operatorname{lcm}$
moduler med felles faktor $d$ , $d\nmid(b_1-b_2)$	vis motsigelsen	ingen løsning
$a^{N}\bmod n$ med sammensatt $n$	splitt, regn hver del, sett sammen	én rest modulo $n$
«minste positive»	representanten i $1,\dots,M$	ett tall, pluss perioden

Å slå sammen to kongruenser med samme rest

x\equiv b\pmod m\ \text{ og }\ x\equiv b\pmod n\iff x\equiv b\pmod{mn}\qquad(\gcd(m,n)=1).

De fire måtene CRT spørres om på eksamen

x

Bevisidéen i CRT, i én setning

b_jN_jx_j

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.