1.5 Drill: Euklid, diofant og lineær kongruens

Hele oppgave-1-repertoaret drillet til automatikk: Euklid frem+baklengs uten regnefeil, full diofant-løsningsmengde, parameter-i-koeffisient, og lineær kongruens med alle inkongruente løsninger — teknikken som må sitte før alt annet.

85 min

13 oppgaver

DrillEukliddiofantlineær kongruens

Din fremgang i kapitlet

0 / 13 oppgaver

Kapitlets plass i kurset

Bygger på

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

Brukes videre i

1.PPrøver til del 1: Delelighet, Euklids algoritme og diofantiske likninger

Dette kapitlet driller hele oppgave-1-repertoaret: sjanger A og B samlet.

Sjangerbokstavene er bokas egne forkortelser, forklart i kap. 0.1. Her er frekvensene du driller mot:

Ferdighet	Sjanger	Frekvens i arkivet
Euklids algoritme frem og baklengs	motoren i A, B og D	15 av 15 sett (100 %)
Lineær diofantisk likning, full løsningsmengde	A	10 av 15 sett (67 %)
Lineær kongruens, alle inkongruente løsninger	B	inngår i ~10 av 15 sett

Variantkatalogen du skal beherske etter dette kapitlet:
1. Euklid + Bézout på et firesifret tallpar
2. Diofantisk likning med full løsningsmengde
3. Parameter i koeffisientene (uttrykk i en ukjent

n

)

4. Løsninger i et gitt intervall

5. Lineær kongruens med forkorting
6. Modulær invers
7. «Minste positive» besvart eksplisitt
Hvorfor dette kapitlet er langt (85 minutter). Fordi dette er den ene ferdigheten som må være automatisk før eksamen. Sjanger A åpner nesten alltid settet, og Euklids algoritme bærer i tillegg RSA-oppgaven (kap. 3.1) og halve restberegningene i Del 2. Slurv her forplanter seg til flere delpunkt.
Prioritet: høyeste. Kapitlet kan trygt deles over flere økter — se tidsanslagene under.

Eksamen er hjelpemiddelkode D: ingen bok, ingen formelsamling, ingen tabeller, ingen egne notater. Alt du regner i dette kapitlet, regner du med penn og en enkel kalkulator som ikke kan mer enn aritmetikk.

Må sitte utenat — hele oppskriften i seks steg:

1. Euklid frem til $\gcd$
2. Euklid baklengs til Bézout
3. Løsbarhet kommentert: $d\mid c$ (likning) eller $d\mid b$ (kongruens)
4. Skalér til partikulærløsning ( $\times c/d$ )
5. Hele løsningsmengden / alle $d$ restklasser
6. «Minste positive» eksplisitt om spurt

Utledes på stedet: Bézout-koeffisientene og den modulære inversen. Ingen av dem finnes utenat for noe tallpar — de leses ut av substitusjonskjeden, hver gang. Det er derfor prosedyren er puggematerialet her, ikke tallene.

Selvtest, femten minutter: velg tre nye firesifrede tallpar. Kjør hele oppskriften på hvert, med boka lukket, og kontroller ved innsetting. Klarer du tre på rad uten å slå opp, er ferdigheten på plass.

Og det er nettopp slik du skal repetere dette kapitlet. Prosedyrer pugges ved å kjøres, ikke ved å leses. Tre nye tallpar er mer verdt enn tre gjennomlesninger av oppskriften under.

Forkunnskaper

Fra boka: kap. 1.1 (delelighet, $\gcd$ ), kap. 1.2 (Euklid og Bézout), kap. 1.3 (diofantiske likninger), kap. 1.4 (kongruenser og invers).

Sist du var her. De tre nøkkelresultatene fra Del 1, ferdig oppfrisket — dette er alt du trenger å ha i hodet for å begynne:

1. Bézouts identitet (kap. 1.2). Det finnes hele tall $x,y$ med
$\gcd(a,b)=ax+by,$
og koeffisientene leses ut av substitusjonskjeden baklengs.

2. Løsningsmengden for en diofantisk likning (kap. 1.3). Er $d=\gcd(a,b)$ og $d\mid c$ , og $(x_0,y_0)$ én løsning, er samtlige løsninger
$x=x_0+\frac bd t,\qquad y=y_0-\frac ad t,\qquad t\in\mathbb{Z}.$
Merk kryssingen: $x$ får $+b/d$ , $y$ får $-a/d$ .

3. Antall løsninger av en kongruens (kap. 1.4). Kongruensen $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$ , med avstand $m/d$ :
$x\equiv x_0+k\cdot\frac md\pmod m,\qquad k=0,1,\dots,d-1.$

Fra videregående: ingenting påkrevd.

Løsningsoppskriften

~10 minutter. Les den, og bruk den som referanse mens du regner oppgavene.

Dette er den samme oppskriften i seks steg for både sjanger A og sjanger B. Forskjellen mellom dem ligger bare i steg 3 og 5 — hva løsbarhetskriteriet ser på, og hva «hele svaret» betyr.

Oppskrift: diofantisk likning i seks steg

For $ax+by=c$ :

1. Euklid frem. Regn $d=\gcd(a,b)$ med divisjonskjeden, linje for linje til rest $0$ . Identifiser siste ikke-null rest som $\gcd$ .
2. Euklid baklengs. Substitusjonskjeden fra nest siste linje og oppover, til $d=ax'+by'$ . Kontrollér ved innsetting.
3. Løsbarhet, kommentert. Deler $d$ tallet $c$ ? Skriv setningen: «Fordi $d=\dots$ deler $c=\dots$ , har likningen løsninger.» Er $d\nmid c$ : konkludér «ingen heltallsløsninger» og stopp.
4. Skalér. Gang Bézout-likningen med $k=c/d$ . Da er $x_0=kx'$ , $y_0=ky'$ . Kontrollér ved innsetting — nå skal du få $c$ , ikke $d$ .
5. Hele løsningsmengden.
$x=x_0+\frac bd t,\qquad y=y_0-\frac ad t,\qquad t\in\mathbb{Z}.$
Kontrollér at $t$ -leddene kansellerer.
6. «Minste positive», om spurt. Løs $x\ge 1$ for $t$ , rund oppover, regn ut både $x$ og $y$ , kontrollér.

Oppskriften må sitte utenat. Steg 3 og steg 6 er de som glemmes, og begge er egne føringspoeng — instruksen på hvert eksamenssett er at alle svar skal begrunnes.

Oppskrift: lineær kongruens i seks steg

For $ax\equiv b\pmod m$ :

1. Euklid frem. Regn $d=\gcd(a,m)$ med divisjonskjeden.
2. Løsbarhet og antall, kommentert. Deler $d$ tallet $b$ ? Skriv setningen: «Siden $d=\dots$ deler $b=\dots$ , er kongruensen løsbar, og den har $d=\dots$ inkongruente løsninger modulo $m$ .» Er $d\nmid b$ : konkludér «ingen løsninger» og stopp.
3. Forkort med $d$ — modulusen inkludert.
$\frac ad x\equiv\frac bd\ \left(\!\!\!\mod\frac md\right).$
Kontrollér at $\gcd$ av de nye $a$ og $m$ er $1$ .
4. Finn inversen. Euklid baklengs på den nye modulusen og $a/d$ , les Bézout-likningen modulo $m/d$ , juster inn i $0\le u<m/d$ . Kontrollér at $au$ gir rest $1$ .
5. Gang opp og reduser: $\displaystyle x\equiv u\cdot\frac bd\pmod{m/d}$ .
6. List alle $d$ løsningene modulo $m$ , med avstand $m/d$ :
$x\equiv x_0+k\cdot\frac md\pmod m,\qquad k=0,1,\dots,d-1.$
Kontrollér alle ved innsetting.

Oppskriften må sitte utenat. Steg 3 (dele modulusen) og steg 6 (alle $d$ ) er de to best belagte feilene i arkivet for denne sjangeren.

De fire kontrollpunktene

Under kode D er selvkontroll den eneste kontrollen du har — det finnes ingen fasit i rommet og ingenting å slå opp i. Disse fire tar til sammen under ett minutt og fanger nesten alle feilene.

1. Etter Euklid frem: deler $\gcd$ -en din begge de opprinnelige tallene? Hvis ikke, er alt nedenfor bortkastet.

2. Etter Euklid baklengs: gir $ax'+by'$ nøyaktig $d$ ? Fanger mistede fortegn i substitusjonskjeden.

3. Etter skalering (eller etter inversen): gir $ax_0+by_0$ nøyaktig $c$ — ikke $d$ ? Fanger glemt skalering, den mest belagte feilen i sjanger A. For kongruenser: gir $au$ rest $1$ ?

4. Til slutt: kansellerer $t$ -leddene i parametriseringen? Og for kongruenser: gir alle $d$ løsningene rest $b$ , og ligger de $m/d$ fra hverandre?

Legg til to gratis tellekontroller:

- Kjedelengden: firesifrede tall gir 4–6 divisjonslinjer. Blir kjeden din på tolv, har du regnet feil.
- Fortegnsmønsteret: når $\gcd$ er lite i forhold til $a$ og $b$ , har Bézout-koeffisientene motsatt fortegn. To positive er et varsel.

Gjennomregnet eksamenscase

~15 minutter.

Her er en typisk oppgave 1, med tre delpunkt som bygger på hverandre — nøyaktig den formen arkivet bruker. Underveis står margnotater som sier hva hvert steg gir uttelling for. Les dem: de er destillert fra hvordan fasitene i arkivet fører oppgaven, og fra oppgaveinstruksen om at alle svar skal begrunnes.

— naturlig pausepunkt —

✏️Eksamenscase: gcd, Bézout, kongruens og minste positive

a) Finn

\gcd(1547,560)

og skriv den på formen

1547x+560y

.
b) Løs kongruensen

560x\equiv 42\pmod{1547}

, og oppgi alle inkongruente løsninger.
c) Angi den minste positive løsningen.

Del a)

(i) Divisjonskjeden frem. Vi deler gjentatt med rest, ved Euklids algoritme, til resten blir $0$ :

$1\,547 = 2\cdot 560 + 427$
$560 = 1\cdot 427 + 133$
$427 = 3\cdot 133 + 28$
$133 = 4\cdot 28 + 21$
$28 = 1\cdot 21 + 7$
$21 = 3\cdot 7 + 0$

Den siste resten som ikke er $0$ , er $7$ . Altså er $\gcd(1\,547,560)=7$ . Kjeden har 6 divisjonslinjer.

(ii) Substitusjonskjeden baklengs. Vi løser den nest siste linja for resten og substituerer oppover, linje for linje:

$7 = 28 - 1\cdot 21$
Sett inn $21 = 133 - 4\cdot 28$ :
$7 = -1\cdot 133 + 5\cdot 28$
Sett inn $28 = 427 - 3\cdot 133$ :
$7 = 5\cdot 427 - 16\cdot 133$
Sett inn $133 = 560 - 1\cdot 427$ :
$7 = -16\cdot 560 + 21\cdot 427$
Sett inn $427 = 1\,547 - 2\cdot 560$ :
$7 = 21\cdot 1\,547 - 58\cdot 560$

(iii) Konklusjon. Altså er

$\gcd(1\,547,560) = 7 = 1\,547\cdot(21) + 560\cdot(-58).$

Kontroll ved innsetting: $1\,547\cdot(21) + 560\cdot(-58) = 32\,487 - 32\,480 = 7$ . Stemmer.

a) Sluttsvar: $\gcd(1547,560)=7$ , og $7=1547\cdot 21+560\cdot(-58)$ .

Sensorblikk på del a). Tre ting gir uttelling her, og de gir det hver for seg. (1) Divisjonskjeden er skrevet ut linje for linje — et $\gcd$ oppgitt alene er et sluttall uten metode, og teller lite. (2) Siste ikke-null rest er identifisert som $\gcd$ , ikke bare underforstått. (3) Substitusjonskjeden er ført steg for steg. Å oppgi $\gcd=7$ uten koeffisientene ville i tillegg gjort del b) umulig — koeffisientene er det du trenger videre.
Merk også at kontrollen ved innsetting er utført. Den koster tjue sekunder, og den er den ene feilen i dette stoffet du kan oppdage helt sikkert selv.

Del b)

Steg 1: regn ut $d=\gcd(560,1\,547)$ , og kommenter løsbarhet og antall løsninger FØR vi løser.

(i) Divisjonskjeden frem. Vi deler gjentatt med rest, ved Euklids algoritme, til resten blir $0$ :

$1\,547 = 2\cdot 560 + 427$
$560 = 1\cdot 427 + 133$
$427 = 3\cdot 133 + 28$
$133 = 4\cdot 28 + 21$
$28 = 1\cdot 21 + 7$
$21 = 3\cdot 7 + 0$

Den siste resten som ikke er $0$ , er $7$ . Altså er $\gcd(1\,547,560)=7$ . Kjeden har 6 divisjonslinjer.

Løsbarhetskriteriet er $d\mid b$ : her er $d=7$ og $b=42$ , og $42=6\cdot 7$ , så $7\mid 42$ . Kongruensen er løsbar, og antall inkongruente løsninger modulo $1\,547$ er $d=7$ .

Steg 2: forkort kongruensen med $d=7$ — husk at modulusen også deles.

$80x \equiv 6 \pmod{221}$

Nå er $\gcd(80,221)=1$ , så den forkortede kongruensen har nøyaktig én løsning modulo $221$ .

Steg 3: finn inversen til $80$ modulo $221$ via Euklids algoritme baklengs.

(i) Divisjonskjeden frem. Vi deler gjentatt med rest, ved Euklids algoritme, til resten blir $0$ :

$221 = 2\cdot 80 + 61$
$80 = 1\cdot 61 + 19$
$61 = 3\cdot 19 + 4$
$19 = 4\cdot 4 + 3$
$4 = 1\cdot 3 + 1$
$3 = 3\cdot 1 + 0$

Den siste resten som ikke er $0$ , er $1$ . Altså er $\gcd(221,80)=1$ . Kjeden har 6 divisjonslinjer.

(ii) Substitusjonskjeden baklengs. Vi løser den nest siste linja for resten og substituerer oppover, linje for linje:

$1 = 4 - 1\cdot 3$
Sett inn $3 = 19 - 4\cdot 4$ :
$1 = -1\cdot 19 + 5\cdot 4$
Sett inn $4 = 61 - 3\cdot 19$ :
$1 = 5\cdot 61 - 16\cdot 19$
Sett inn $19 = 80 - 1\cdot 61$ :
$1 = -16\cdot 80 + 21\cdot 61$
Sett inn $61 = 221 - 2\cdot 80$ :
$1 = 21\cdot 221 - 58\cdot 80$

(iii) Konklusjon. Altså er

$\gcd(221,80) = 1 = 221\cdot(21) + 80\cdot(-58).$

Kontroll ved innsetting: $221\cdot(21) + 80\cdot(-58) = 4\,641 - 4\,640 = 1$ . Stemmer.

Lest modulo $221$ forsvinner leddet med $221$ , og vi står med

$80\cdot(-58) \equiv 1 \pmod{221}.$

Vi flytter koeffisienten inn i intervallet $0\le u<221$ ved å legge til $221$ : inversen er $u=163$ .

Kontroll: $80\cdot 163 = 13\,040 = 59\cdot 221 + 1$ . Resten er $1$ . Stemmer.

Steg 4: gang opp med inversen.

$x \equiv 163\cdot 6 = 978 \equiv 94 \pmod{221}$

Steg 5: list alle $7$ inkongruente løsningene modulo $1\,547$ . De ligger $m/d=221$ fra hverandre, altså $\displaystyle x_0+k\cdot\frac{m}{d}$ for $k=0,1,\dots,6$ :

$x \equiv 94,\qquad x \equiv 315,\qquad x \equiv 536,\qquad x \equiv 757,\qquad x \equiv 978,\qquad x \equiv 1199,\qquad x \equiv 1420 \pmod{1\,547}$

Kontroll ved innsetting (alle $7$ skal gi resten $42$ ):

- $x=94$ : $560\cdot 94 = 52\,640$ , og $52\,640 \bmod 1\,547 = 42$ ✓
- $x=315$ : $560\cdot 315 = 176\,400$ , og $176\,400 \bmod 1\,547 = 42$ ✓
- $x=536$ : $560\cdot 536 = 300\,160$ , og $300\,160 \bmod 1\,547 = 42$ ✓
- $x=757$ : $560\cdot 757 = 423\,920$ , og $423\,920 \bmod 1\,547 = 42$ ✓
- $x=978$ : $560\cdot 978 = 547\,680$ , og $547\,680 \bmod 1\,547 = 42$ ✓
- $x=1199$ : $560\cdot 1199 = 671\,440$ , og $671\,440 \bmod 1\,547 = 42$ ✓
- $x=1420$ : $560\cdot 1420 = 795\,200$ , og $795\,200 \bmod 1\,547 = 42$ ✓

b) Sluttsvar: $7$ inkongruente løsninger modulo $1547$ :
$x\equiv 94,\ 315,\ 536,\ 757,\ 978,\ 1199,\ 1420\pmod{1547}.$

Sensorblikk på del b). Her ligger fire føringspoeng. (1) Løsbarheten er kommentert før vi løste, som en setning med tall: $d=7$ deler $b=42$ . (2) Antallet er oppgitt eksplisitt — sju inkongruente løsninger — før vi visste hvilke. (3) Forkortingen delte modulusen: $1547$ ble $221$ . Å la modulusen stå er den best belagte feilen i denne sjangeren. (4) Alle sju løsningene er listet, ikke bare den første.
Legg merke til at $\gcd$ -en fra del a) ble gjenbrukt. Det er meningen med at oppgaven er tredelt — delpunktene er en trapp, og du skal si at du bruker forrige trinn.

Del c)

Blant de sju løsningene er alle positive, og den minste er $94$ .

Kontroll: $560\cdot 94=52\,640$ , og $52\,640=34\cdot 1547+42$ , siden $34\cdot 1547=52\,598$ . Resten er $42$ ✓.

c) Sluttsvar: den minste positive løsningen er $x=94$ .

Sensorblikk på del c). Dette er et eget delpunkt med eget svar, og det skal skrives ut som en setning. Å stoppe etter del b) med sju tall og la leseren velge selv, er å levere halve svaret på siste del. Her var det lett — alle sju var positive — men si det: «blant de sju løsningene er den minste positive $94$ ». Da har du vist at du forstod hva som ble spurt om.

Tidsbudsjett for denne oppgaven på eksamen: tre delpunkt à ~24 minutter gir ~72 minutter til rådighet, men i praksis tar den 20–30 minutter når prosedyren sitter. Del a) er 5–8 minutter, del b) 12–18, del c) under ett. Det er nettopp derfor sjanger A og B er «billige poeng» — du kjøper tid til de dyrere oppgavene senere i settet.

Oppgavene

~50 minutter til sammen. Tretten oppgaver, gruppert etter variant.

Regn dem med penn og lukket bok. Det er den eneste treningsformen som ligner eksamen, og forskjellen mellom å ha lest oppskriften og å kunne den viser seg bare her.

Slik er de gruppert:

- Oppgave 1–3: Euklid + Bézout
- Oppgave 4–6: diofantiske likninger (full løsningsmengde, intervall, parameter i koeffisientene)
- Oppgave 7–9: lineære kongruenser
- Oppgave 10–11: modulær invers
- Oppgave 12: «minste positive»
- Oppgave 13: kjedet oppgave i eksamensform

Del dem gjerne over flere økter. Oppgave 1–6 er én naturlig økt (~25 min), oppgave 7–13 en annen (~25 min).

📝Oppgave 1

Finn $\gcd(1173,456)$ og skriv den på formen $1173x+456y$ .

📝Oppgave 2

Finn $\gcd(1547,560)$ og skriv den på formen $1547x+560y$ , uten å se på eksamenscasen over.

Kontrollér svaret ved innsetting, og sjekk i tillegg at $\gcd$ -en din deler begge tallene.

📝Oppgave 3

Finn $\gcd(986,374)$ og skriv den på formen $986x+374y$ . Bruk deretter produktregelen til å finne $\operatorname{lcm}(986,374)$ .

📝Oppgave 4

Finn samtlige heltallsløsninger av $1547x+560y=42$ .

📝Oppgave 5

Betrakt likningen $986x+374y=170$ .

a) Finn samtlige heltallsløsninger.
b) Finn alle løsninger med $0\le x\le 50$ .

📝Oppgave 6

La $n$ være et helt tall.

a) Vis at $7n+3$ og $5n+2$ er relativt primiske for alle hele tall $n$ .
b) Finn den generelle heltallsløsningen av $(7n+3)x+(5n+2)y=4$ .
c) Kontrollér svaret for $n=3$ .

📝Oppgave 7

Løs $69x\equiv 51\pmod{84}$ , og oppgi alle inkongruente løsninger modulo $84$ .

📝Oppgave 8

Løs $76x\equiv 52\pmod{96}$ , og oppgi alle inkongruente løsninger modulo $96$ .

📝Oppgave 9

Løs $58x\equiv 34\pmod{72}$ , og oppgi alle inkongruente løsninger modulo $72$ .

📝Oppgave 10

a) Avgjør om

29

har en invers modulo

84

, og finn den i så fall.
b) Kontrollér svaret ved innsetting.

📝Oppgave 11

a) Finn inversen til

53

modulo

100

.
b) Bruk den til å løse

53x\equiv 31\pmod{100}

📝Oppgave 12

Finn samtlige heltallsløsninger av $1666x+646y=204$ , og angi den løsningen der $x$ er minst mulig positivt tall.

📝Oppgave 13

Denne oppgaven har eksamensform: tre delpunkt som bygger på hverandre.

a) Finn $\gcd(1173,456)$ og skriv den som en lineærkombinasjon av $1173$ og $456$ .
b) Avgjør om likningen $1173x+456y=51$ har heltallsløsninger, og finn i så fall samtlige.
c) Løs kongruensen $456x\equiv 51\pmod{1173}$ , og oppgi alle inkongruente løsninger.

Typiske feil

Under tidspress er det ikke forståelsen som svikter, men bokføringen. Disse seks er de som faktisk skjer, og alle fanges av kontrollene i kortet «De fire kontrollpunktene».

- Regnefeil under tidspress. Den vanligste av alle, og den billigste å oppdage: sjekk at $\gcd$ -en din deler begge de opprinnelige tallene, og at Bézout-koeffisientene gir $d$ ved innsetting. Til sammen tjue sekunder. Kjedelengden er også en kontroll: firesifrede tall gir 4–6 divisjonslinjer, ikke tolv.

- Ufullstendig løsningsmengde eller ufullstendige inkongruente løsninger. «Samtlige heltallsløsninger» krever $t$ -parameteren med $t\in\mathbb{Z}$ . «Alle inkongruente løsninger» krever alle $d$ av dem. Å levere én er å levere en $d$ -tedel — og for oppgave 13 del c) betyr det en tredel.

- Euklid baklengs-slurv. Et mistet fortegn, eller produkter ganget ut for tidlig slik at tallet du skulle substituere forsvant. Kontrollen: sett koeffisientene inn og se at du får $d$ . Fortegnsmønsteret er en gratis andre kontroll: når $\gcd$ er lite i forhold til $a$ og $b$ , har koeffisientene motsatt fortegn.

- Glemt løsbarhetssjekk. Både som føringspoeng (fasitene skriver setningen ut) og som tidsbesparelse (er $d\nmid c$ , er du ferdig etter tjue sekunder). Hopper du over den, oppdager du problemet først når $c/d$ blir en brøk.

- Glemt «minste positive». Det er et eget delpunkt med eget svar, og det krever at du løser en ulikhet i $t$ — ikke at du ser på partikulærløsningen. I oppgave 12 var partikulærløsningen $x_0=42$ mens svaret var $4$ .

- Forkorting uten å dele modulusen. Fra $58x\equiv 34\pmod{72}$ blir det $29x\equiv 17\pmod{36}$ , ikke $\pmod{72}$ . Kontrollen: etter forkortingen skal $\gcd$ av de nye $a$ og $m$ være $1$ .

Prosedyrekort

Dette er flashcard-stoff — hopp trygt over ved førstegangslesing; tidsanslaget på 85 minutter gjelder oppskriften, casen og oppgavene.

Drillkapitlene har ingen begrepsbank i vanlig forstand. I stedet er kortene her oppskriftskort: hvert av dem er en prosedyre du skal kunne kjøre, ikke et faktum du skal kunne si.

Og det er slik de skal pugges: ikke ved å lese kortet, men ved å kjøre prosedyren på nye tall. Et kort du har lest fem ganger, hjelper deg ikke 24. november. En prosedyre du har kjørt fem ganger, gjør det.

Kort: Euklid frem og baklengs

a

Kort: diofantisk likning i seks steg

ax+by=c

Kort: lineær kongruens i seks steg

ax\equiv b\pmod m

Kort: modulær invers

\gcd(a,m)=1

Kort: «minste positive»

x\ge 1

Kort: løsninger i et intervall

x

Kort: parameter i koeffisientene

n

Kort: kontrollene, samlet

\gcd

Etter	Kontroll	Fanger
Euklid frem	deler $\gcd$ begge tallene?	regnefeil i divisjonskjeden
Euklid baklengs	gir $ax'+by'$ nøyaktig $d$ ?	mistet fortegn i substitusjonen
Skalering	gir $ax_0+by_0$ nøyaktig $c$ (ikke $d$ )?	glemt skalering
Parametrisering	kansellerer $t$ -leddene? Er $\displaystyle a\cdot\frac bd=b\cdot\frac ad$ ?	feil fortegn, feil skrittlengde
Forkorting	er $\gcd(a/d,\ m/d)=1$ ?	glemt å dele modulusen
Invers	gir $au$ rest $1$ ?	slurv i Euklid baklengs
Alle løsninger	gir alle $d$ rest $b$ , med avstand $m/d$ ?	ufullstendig svar

Kort: kode D-realistiske tallstørrelser

a

Størrelse	Typisk verdi på eksamen
$a$ , $b$ , $m$	tre- til femsifret
Euklid-kjeden	4–6 divisjonslinjer
Kvotientene i kjeden	små, ofte $1$ – $5$
$d=\gcd$	fra $1$ til noen få titall
$c/d$	lite helt tall, typisk $1$ – $10$
Antall inkongruente løsninger	$1$ til $7$ (mer ville vært upraktisk å liste)
Modulus etter forkorting	under $50$

Kort: tidsbudsjettet for sjanger A og B

Eksamen er 4 timer på omtrent 10 likt vektede delpunkt — altså ~24 minutter per delpunkt . Slik fordeler en tredelt oppgave 1 seg når prosedyren sitter: Del Innhold Tid a) Euklid frem + baklengs 5-8 min b) løsbarhet + skalering + løsningsmengde 8-12 min c) «minste positive» eller kongruensen 3-8 min Hele oppgaven 20-30 min Poenget med tallene: du har ~72 minutter til rådighet for tre delpunkt, og bruker 20-30. Sjanger A og B er der du kjøper tid til de dyrere oppgavene senere i settet — Legendre-reduksjonene i Del 4 og bevisoppgavene i Del 6. Og motsatt: bruker du 50 minutter på oppgave 1, har du et problem som ikke handler om oppgave 1. Det handler om at prosedyren ikke er automatisk nok, og det fikses bare med drill.

Del	Innhold	Tid
a)	Euklid frem + baklengs	5–8 min
b)	løsbarhet + skalering + løsningsmengde	8–12 min
c)	«minste positive» eller kongruensen	3–8 min
Hele oppgaven	20–30 min

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.