Kongruenslikninger

Eksempel 1:

En jogger løper ei rundløype som er 5 km lang. Han løper 2 km før han stopper og hviler, så 2 km til før han stopper og hviler, og så videre til han er utslitt. Han er da 4 km inn i løypa. Hvor mange intervaller på 2 km kan han ha løpt?

Dette er et eksempel på et problem som kan løses ved hjelp av en kongruenslikning. Likningen blir

$2x \equiv 4 \, (mod \; 5)$, der $x$ er antall intervaller.

Likningen sier at $x$ antall intervaller på 2 km må rekke 4 km forbi et antall hele runder på 5 km.

I artikkelen om regneregler for kongruens lærte vi divisjonsregelen, som sier at vi kan dividere med samme tall, $c$, på begge sider av kongruenstegnet, hvis vi samtidig dividerer modulus, $n$, med $SFF(c, n)$.

Siden $SFF(2, 5) = 1$, kan vi dividere med 2 på begge sider av kongruenstegnet uten å endre modulus, og vi får

$x \equiv 2 \, (mod \; 5)$.

Antall intervaller må altså være kongruente med 2 modulo 5, med andre ord på formen $2 + k \cdot 5$, der $k$ er et helt tall. Han kan ha løpt $2 + 0 \cdot 5 = 2$ intervaller, $2 + 1 \cdot 5 = 7$ intervaller, og så videre. Dette er illustrert i figurene under.

Illustrasjon av 2 intervaller på 2 km i 5 km løype

Illustrasjon av 7 intervaller på 2 km i 5 km løype

Her kan ikke $k$ være negativ, siden han ikke kan ha løpte et negativt antall runder. Men matematisk sett er også $2 + (-1) \cdot 5 = -3$ og $2 + (-2) \cdot 5 = -8$ løsninger til kongruenslikningen. Tolker vi disse i forhold til det opprinnelige problemet, representerer løsningene at joggeren har løpt motsatt vei. 

Dette er illustrert i figurene under.

Illustrasjon av -3 intervaller på 2 km i 5 km løype

Illustrasjon av -8 intervaller på 2 km i 5 km løype

Vi er vant med å modellere med vanlige likninger, for eksempel setter vi uten videre opp likningen $8x = 40$, hvis vi skal representere problemet "Hvor mange kg appelsiner til 8 kroner per kg kan vi ha kjøpt når vi betalte 40 kroner?".

Men kongruenslikninger er uvante for de fleste av oss, derfor vil vi slite mer med å formulere problemer i form av kongruenslikninger.

Kongruenslikningen i eksempel 1 hadde uendelig mange løsninger, på formen $2 + k \cdot 5$, mens den vanlige likningen med appelsinene bare hadde én løsning. Videre ser vi at vi at, uansett hva vi hadde betalt for appelsinene, ville kunnet finne en løsning på likningen. Hadde vi betalt 44 kroner, ville det betydd at vi hadde kjøpt 5,5 kg. Det er ikke noe krav at svaret skal være et helt tall. I en kongruenslikning derimot, må svarene være hele tall. Det betyr at ikke alle kongruenslikninger har løsning.

Eksempel 2:

Hvis løypa i eksempel 1 hadde vært 6 km og joggeren var utslitt 3 km inn i løypa, skjønner vi at han ikke kunne løpt et helt antall intervaller på 2 km. For pausene ville alltid kommet 2 km inn, 4 km inn og tilbake ved start. Så kongruenslikningen

$2x \equiv 3 \, (mod \; 6)$.

har ingen løsning.

En kongruenslikning vil enten ikke ha løsning eller ha uendelig mange løsninger.

I denne artikkelen skal vi se nærmere på hvordan vi avgjør om en kongruenslikning har løsning eller ikke, og lære metoder for å systematisk løse kongruenslikninger. Mer presist snakker vi i denne artikkelen om lineære kongruenslikninger, eller første grads kongruenslikninger, fordi den ukjente, $x$, er av første grad. Men for enkelhets skyld sier vi gjerne bare kongruenslikninger. En lineær kongruenslikning er på formen $ax \equiv b \, (mod \; n)$, der $a$, $b$ og $n$ er hele tall, $a \ne 0$$n > 0$.

Men vi skal først øve litt på å modellere med kongruenslikninger.

Oppgave 1:

Modeller problemene under med kongruenslikninger. NB! Du blir ikke bedt om å løse likningene.

  1. En friidrettsutøver løper 300-meters intervaller på en 400-meters bane, og står stille og hviler mellom hvert intervall. Når hun gir seg, har hun passert målstreken med 100 meter. Hvor mange intervaller kan hun ha løpt?
     
  2. En forstadsbane passerer et stoppested første gang klokka 05:00, deretter hvert 12. minutt. Etter hvor mange passeringer passerer banen deretter på hele klokkeslett?

Se løsningsforslag

Oppgave 2:

Foreslå en situasjon som kan modelleres med kongruenslikningen $4x \equiv 0 \, (mod \; 10)$.

Se løsningsforslag

I eksempel 1 hadde vi kongruenslikningen $2x \equiv 4 \, (mod\; 5)$, og fant ut at løsningene var på formen $2 + k \cdot 5$, der $5$ var modulus. Markerer vi løsningene i en tabell med modulus antall kolonner, altså 5, blir det slik:

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 29
21 22 23 24 25

Vi ser at løsningene havner i samme kolonne, de er i samme restklasse, slik vi lærte om i artikkelen om kongruens

I eksempel 2 så vi at likningen $2x \equiv 3 \, (mod \; 6)$ ikke hadde løsning. Vi ser nå på et tredje eksempel:

Eksempel 3:

Vi har kongruenslikningen $9x \equiv 12 \, (mod \; 15)$.

Ved prøving og feiling i et regneark finner vi følgende løsninger: $3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53, 58$.

Markerer vi løsningene i eksempel 3 i en tabell med modulus antall kolonner, altså 15, blir det slik:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

Her ser vi at løsningene havner i tre forskjellige restklasser. Så hva er forskjellen på kongruenslikningene i eksempel 1, 2 og 3?

En lineær kongruenslikning er, som nevnt, på formen $ax \equiv b \, (mod\; n)$. I eksempel 1 hadde vi $SFF(a, n) = SFF(2, 5) = 1$ og i eksempel 3 $SFF(a, n) = SFF(9, 15) = 3$. Så det kan se ut til at $SFF(a, n)$ har noe med antall restklasser å gjøre. Og det er riktig, løsningene til en kongruenslikning havner i $SFF(a, n)$ restklasser.

Men i eksempel 2 hadde vi $SFF(a, n) = SFF(2, 6) = 2$, og den likningen hadde allikevel ingen løsning. Det er fordi en kongruenslikning har løsning hvis og bare hvis $SFF(a, n) \mid b$. I eksempel 1 hadde vi $SFF(2, 5) = 1 \mid 4$ og i eksempel 3 $SFF(9, 15) = 3 \mid 12$. Men i eksempel 2 hadde vi $SFF(2, 6) = 2 \nmid 3$.

Siden 1 går opp i alle tall, har alle kongruenslikninger der $SFF(a, n) = 1$ løsning.

Vi har altså

$\fbox{$\text{La } d = SFF(a, n) \\
ax \equiv b \, (mod \; n) \text{ har ingen løsning hvis } d \nmid b \\
ax \equiv b \, (mod \; n) \text{ har løsning i } d \text{ restklasser hvis } d \mid b$}$

SFF er en kombinasjon av alle felles faktorer, så, sagt på en annen måte, må alle faktorer som er felles for $a$ og $n$ også være faktorer i $b$ for at likningen skal ha løsning. Hvis $a$ og $n$ er innbyrdes primiske, slik at $SFF(a, n) = 1$, vil alle løsningene havne i samme restklasse.

Når vi snakker om å løse en kongruenslikning, mener vi egentlig å finne hvilke restklasser likningen har løsning i. Som representant for klassen velger vi det minste ikke-negative tallet i klassen, for eksempel $3$ blant løsningene i eksempel 3.

Innen hver restklasse finnes det uendelig mange kongruente løsninger, men løsningene fra forskjellige restklasser er ikke kongruente med hverandre. Løsninger fra forskjellige restklasser kaller vi derfor også gjerne innbyrdes inkongruente løsninger.

Oppgave 3:

Avgjør om følgende kongruenslikninger har løsning, og i så fall hvor mange restklasser de har løsninger i:

  1. $4x \equiv 8 \, (mod \; 10)$
     
  2. $3x \equiv 8 \, (mod \; 10)$
     
  3. $4x \equiv 9 \, (mod \; 10)$
     
  4. $84x \equiv 108 \, (mod \; 12)$

Se løsningsforslag

Metoder for å løse lineære kongruenslikninger

Vi skal nå se hvordan vi systematisk kan bruke regneregler for kongruenser til å løse lineære kongruenslikninger. Noen av disse er felles med reglene for å løse vanlige likninger, slik det er beskrevet i algebra-artikkelen om likninger og ulikheter, men ikke alle. Det finnes regler vi bare kan bruke på kongruenslikninger, og regler vi bare kan bruke på vanlige likninger.

De første tre reglene går ut på å rydde i leddene, og å erstatte store/negative tall med mindre/positive tall.

Flytte over ledd og skifte fortegn

I artikkelen om regneregler for kongruens presenterte vi en regel som sier at vi kan addere samme heltall på begge sider av kongruenstegnet. Det betyr at

$\fbox{$ax + c \equiv b + c\, (mod \; n) \text{ har samme løsninger som } ax \equiv b \, (mod \; n)$}$

Dette er helt tilsvarende regelen vi har for vanlige likninger, og vil i praksis si at vi kan flytte et tall over til andre siden av kongruenstegnet hvis vi samtidig skifter fortegn. $x$ representerer et tall, derfor kan vi også flytte ledd med $x$ på samme måte.

Eksempel 4:

Vi skal løse kongruenslikningen $3x + 4 \equiv 7 + 2x \, (mod \; 5)$.

Vi flytter $4$ over til høyre side og $2x$ over til venstre side med fortegnsskifte:

$\begin{align} 3x – 2x &\equiv 7 – 4 \, (mod \; 5) \\
x & \equiv 3 \;\;\;\;\, (mod \; 5) \end{align}$

Erstatte store / negative tall med kongruente tall

I artikkelen om regneregler for kongruens så vi at vi i en kongruens kan erstatte tall med kongruente tall. 

Dette betyr at vi kan erstatte tall som er større eller lik $n$ med kongruente, mindre tall og negative tall med kongruente, positive tall. Siden denne regelen er tett knyttet til kongruensbegrepet, finnes det ingen tilsvarende regel for vanlige likninger.

En praktisk måte å bruke regelen på er, som vi har sett, å erstatte tall, $t \ge n$ eller $t < 0$ med $t – \lfloor \frac{\displaystyle t}{\displaystyle n} \rfloor \cdot n$, der $n$ er modulus. Vi vil da alltid få $0 \le t < n$.

Eksempel 5:

Vi skal forenkle kongruenslikningen $x \equiv 17 \, (mod \; 7)$. Vi kan da erstatte

$17$ med $17 – \lfloor \frac{\displaystyle 17}{\displaystyle 7} \rfloor \cdot 7 = 17 -2 \cdot 7 = 3$.

Og vi får $x \equiv 3 \, (mod \; 7)$.

 

Vi skal forenkle kongruenslikningen $x \equiv -11 \, (mod \; 3)$. Vi kan da erstatte

$-11$ med $-11 – \lfloor \frac{\displaystyle -11}{\displaystyle 3} \rfloor \cdot 3 = -11 -(-4) \cdot 3 = 1$.

Og vi får $x \equiv 1 \, (mod \; 3)$.

 

Vi skal forenkle kongruenslikningen $5x \equiv 3 \, (mod \; 4)$. Vi kan da erstatte

$5$ med $5 – \lfloor \frac{\displaystyle 5}{\displaystyle 4} \rfloor \cdot 4 = 5 – 1 \cdot 4 = 1$.

Og vi får $x \equiv 3 \, (mod \; 4)$.

 

Vi skal forenkle kongruenslikningen $-5x \equiv 12 \, (mod \; 6)$. Vi kan da erstatte

$-5$ med $-5 – \lfloor \frac{\displaystyle -5}{\displaystyle 6} \rfloor \cdot 6 = -5 – (-1) \cdot 6 = 1$.

Og vi kan erstatte $12$ med $12 – \lfloor \frac{\displaystyle 12}{\displaystyle 6} \rfloor \cdot 6 = 12 – 2 \cdot 6 = 0$.

Og vi får $x \equiv 0 \, (mod \; 6)$.

Oppgave 4:

Forenkle kongruenslikningen $x + 4 \equiv 13 – 5x \, (mod \; 5)$.

Se løsningsforslag

Dividere med samme tall på begge sider

I artikkelen om regneregler for kongruens presenterte vi en regel som sier at vi kan dividere med et tall, $c$, på begge sider av kongruenstegnet hvis vi samtidig dividerer modulus, $n$, med $SFF(c, n)$. Det vil si at

$\fbox{$cax \equiv cb\, (mod \; n) \text{ har samme løsninger som } ax \equiv b \, (mod \; \frac{\displaystyle n}{\displaystyle d}), \text{ der } d = SFF(c, n)$}$

Denne regelen minner om den vi har i vanlige likninger, men mens vi i vanlige likninger kan dividere med et vilkårlig tall forskjellig fra $0$ på begge sider av likhetstegnet, kan vi i en kongruenslikning $ax \equiv b\, (mod \; n)$ bare dividere med tall som går opp i både $a$ og $b$, ellers ville vi jo sitte igjen med noe som ikke var heltall. Det største tallet vi kan dividere med er $c = SFF(a, b)$. I tillegg må også modulus divideres med $SFF(c, n)$.

Eksempel 6:

Vi skal løse kongruenslikningen $4x \equiv 12 \, (mod \; 18)$. Vi ser at vi kan forenkle likningen ved å dividere med $SFF(4, 12) = 4$ på begge sider av kongruenstegnet. Det har vi lov til hvis vi samtidig dividerer modulus $18$ med $SFF(4, 18) = 2$. Og vi får
$x \equiv 3 \, (mod \; 9)$.

Tidligere i artikkelen har vi sagt at, så fremt en kongruenslikning, $ax \equiv b \, (mod \; n)$, har løsning, har den løsning i $SFF(a, n)$ restklasser.

Bruker vi denne regelen på eksempel 6, ser vi at likningen vi starter med har løsning i $SFF(4, 18) = 2$ restklasser, mens likningen vi ender opp med bare har løsning i $SFF(1, 9) = 1$ restklasse. Allikevel er det vi har gjort riktig.

Som tidligere nevnt finnes det uendelig mange løsninger til en løsbar kongruenslikning. Ved prøving og feiling i et regneark finner vi at noen av løsningene til den opprinnelige likningen i eksempel 6 er $3, 12, 21, 30, 39, 48$. Disse havner i to restklasser modulo $18$, nemlig $3, 21, 39$ i restklasse $3$, og $12, 30, 48$ i restklasse $12$.

Ved prøving og feiling i likningen vi ender opp med i eksempel 6, finner vi også der de samme løsningene, for eksempel $3, 12, 21, 30, 39, 48$. Men alle havner nå i samme restklasse, restklasse $3$ modulo $9$.

Det vi har gjort er altså riktig, løsningene er beholdt, men restklassene har kollapset inn i én enkelt restklasse. Vi kan imidlertid enkelt rekonstruere de opprinnelige restklassene ved hjelp av følgende regel:

$\fbox{$\text{Hvis } x = t \text{ er en løsning til kongruenslikningen } ax \equiv b\, (mod \; n), \\
\text{vil alle restklasser med løsning mod n være gitt ved } x_k = t + k \frac{\displaystyle n}{\displaystyle d} \\
\text{der } d = SFF(a, n) \text{ og } 0 \le k \le d – 1$}$

Eksempel 7:

I eksempel 6 har vi kommet fram til at en løsning til kongruenslikningen $4x \equiv 12 \, (mod \; 18)$ er $x = 3$. Og vi har $d = 2$. Det vil si at de opprinnelige restklassene er $x_0 = 3 + 0 \cdot \frac{\displaystyle 18}{\displaystyle 2} = 3$ og $x_1 = 3 + 1 \cdot \frac{\displaystyle 18}{\displaystyle 2} = 12$.

Oppgave 5:

Finn alle restklasser som inneholder løsninger til likningen $6x \equiv 12 \, (mod \; 9)$.

Se løsningsforslag

Å finne alle restklasser som inneholder løsninger til en kongruenslikning vil vi for enkelhets skyld heretter bare omtale som å løse kongruenslikningen.

Når vi har brukt de tre reglene nevnt over, har vi forenklet kongruenslikningen så langt det går. I eksemplene og oppgavene så langt har vi da stått igjen med et uttrykk på formen $x \equiv t\, (mod \; n)$, der $t$ er et eller annet tall. Vi har altså endt opp med at den ukjente, $x$, står igjen alene på venstre side av kongruenstegnet, og en løsning til kongruenslikningen er funnet. Imidlertid er det ikke alltid at dette skjer.

Eksempel 8:

Vi skal forenkle kongruenslikningen $4x \equiv 6 \, (mod \; 9)$. Det største tallet vi kan dividere med er $SFF(4, 6) = 2$.

Og vi får $2x \equiv 3 \, (mod \; 9)$. (Her er modulus dividert på $SFF(2, 9) = 1$, så nitallet er blitt stående)

Vi ser at vi i eksempel 8 ikke har klart å få $x$ alene på venstre side, men står igjen med uttrykket $2x \equiv 3 \, (mod \; 9)$.

Vi skal imidlertid se at vi ved hjelp av en siste regel alltid vil kunne isolere $x$ på venstre side.

Multiplisere med invers

I artikkelen om regneregler for kongruens presenterte vi en regel som sier at vi i en kongruens kan multiplisere med samme heltall på begge sider av kongruenstegnet. Det betyr at

$\fbox{$ax \cdot c \equiv b \cdot c\, (mod \; n) \text{ har samme løsninger som } ax \equiv b \, (mod \; n)$}$

I den samme artikkelen presenterer vi en multiplikativ invers til et tall, $a$ modulo $n$ som et tall, $\overline a$, som er slik at $a \cdot \overline a \equiv 1 \, (mod \; n)$. Det vil si at hvis vi i en kongruenslikning på formen $ax \equiv b \, (mod \; n)$ multipliserer med $\overline a$ på begge sider, vil vi få $(a \cdot \overline a)x \equiv b \overline a \, (mod \; n)$, noe som, siden $a \cdot \overline a \equiv 1 \, (mod \; n)$ kan forenkles til $x \equiv b \overline a \, (mod \; n)$, og vi har isolert $x$ på venstre side.

Den eneste haken er at vi vet at ikke alle tall har en multiplikativ invers modulo $n$. I artikkelen om regneregler for kongruens anga vi følgende regel:

$\fbox{$\text{Det finnes en } \overline a \text{ slik at }  a \cdot \overline a \equiv 1 \, (mod \; n) \text{ hvis og bare hvis } SFF(a, n) = 1$}$

Hvis vi imidlertid har brukt forenklingsreglene over, har vi dividert bort alle felles faktorer i $a$ og $n$, slik at vi er garantert at $SFF(a, n) = 1$, og at det derfor vil finnes en multiplikativ invers. Når vi har forenklet en kongruenslikning så langt det går, vil vi derfor alltid kunne isolere $x$ på venstre side ved bruk av en multiplikativ invers.

I en vanlig likning vil det alltid finnes en multiplikativ invers, å multiplisere med $\overline a$ betyr jo det samme som å dividere med $a$. Siden vi kan dividere med alle tall unntatt $0$, vil vi derfor kunne isolere $x$ i likningen $ax = b$ ved å dividere med $a$ på begge sider. I ett trinn gjør vi derved det vi trenger to trinn for å gjøre i en kongruenslikning.

Hvis et tall har multiplikativ invers modulo $n$, kan vi finne en invers ved prøving og feiling blant tallene i intervallet $[1, n-1]$, eller ved å lage multiplikasjonstabeller modulo $n$. For store $n$ kan dette bli tungvint, vi kan da bruke noe som heter Euklids utvidede algoritme.

Dette nettstedet har en app som finner multiplikative inverser ved hjelp av Euklids utvidede algoritme.

For illustrasjonens skyld setter vi allikevel opp multiplikasjonstabeller modulo $n$ for $n$ mellom $2$ og $11$. Ett-tall er markert med gult. For å finne den multiplikative inversen til et tall, $a$ modulo $n$, velger vi tabellen som heter "Modulo n", går inn i raden med $a$ i første kolonne, finner kolonna med det gule feltet, og leser av $\overline a$ øverst i denne kolonna.

Tabeller over multiplikative inverser modulo 2 - modulo 6

Tabeller over multiplikative inverser modulo 7 - modulo 9

Tabeller over multiplikative inverser modulo 10 - modulo 11

Eksempel 9:

Vi skal få $x$ til å stå alene på venstre side i kongruenslikningen $4x \equiv 7 \, (mod \; 9)$.

Siden $SFF(4, 9) = 1$, vet vi at $4$ har en multiplikativ invers modulo $9$. Vi går inn i raden med $a = 4$ i tabellen "Modulo 9" og finner at inversen er $\overline a = 7$.

Vi multipliserer med $7$ på begge sider av kongruenstegnet og får $(4 \cdot 7)x \equiv 7 \cdot 7 \, (mod \; 9) \Rightarrow x \equiv 49 \, (mod \; 9)$.

Nå har vi fått et tall som er større enn modulus på $9$ på høyre side, så vi bruker regelen om å erstatte med kongruente tall og erstatter $49$ med $49 – \lfloor \frac{\displaystyle 49}{\displaystyle 9} \rfloor \cdot 9 = 49 – 5 \cdot 9 = 4$.

Så vi får $x \equiv 4 \, (mod \; 9)$.

Oppgave 6:

$x$ til å stå alene på venstre side i kongruenslikningen $4x \equiv 3 \, (mod \; 7)$.

Se løsningsforslag

Løsningsalgoritme

Mange lærebøker har en nokså springende tilnærming til å løse kongruenslikninger. De trekker fram enkelteksempler og spesialtilfeller, men gir ingen systematisk gjennomgang. Men med de metodene vi har sett på, skal vi nå sette opp en algoritme, det vil si en trinnvis fremgangsmåte, for å løse kongruenslikninger som alltid virker.

En kongruenslikning der leddene er ordnet, er på formen $ax \equiv b \, (mod \; n)$. Siden $a$ og $b$ kan endre seg når vi går gjennom de forskjellige trinnene, gir vi dem en indeks avhengig av hvilket trinn vi er i, for eksempel $a_1$, $b_1$.

Vi illustrerer med et gjennomgående eksempel.

Eksempel 10:

Vi skal løse kongruenslikningen $-5x + 6 \equiv 52 – 3x \, (mod \; 14)$.

Trinn 1:

Vi starter med å, med fortegnsskifte, flytte alle ledd med $x$ over på venstre side, alle konstanter over på høyre side, og trekke sammen like ledd. Når dette er gjort, har vi en likning på formen $a_1x \equiv b_1 \, (mod \; n)$.

Eksempel 10.1:

Vi flytter $-3x$ til venstre side og $6$ til høyre side med fortegnsskifte, trekker sammen og får

$-2x \equiv 46 \, (mod \; 14)$.

Trinn 2:

Hvis ikke $0 \le a_1 < n$, erstatter vi $a_1$ med $a_1 – \lfloor \frac{\displaystyle a_1}{\displaystyle n} \rfloor \cdot n$. Tilsvarende for $b_1$.

Vi har nå likningen $a_2x \equiv b_2 \, (mod \; n)$.

Eksempel 10.2:

Vi har $a_1 = -2 < 0$, så vi erstatter $-2$ med $-2 – \lfloor \frac{\displaystyle -2}{\displaystyle 14} \rfloor \cdot 14 = -2 – (-1) \cdot 14 = 12$.

Vi har $b_1 = 46 > 14$, så vi erstatter $46$ med $46 – \lfloor \frac{\displaystyle 46}{\displaystyle 14} \rfloor \cdot 14 = 46 – 3 \cdot 14 = 4$.

Resultatet blir $12x \equiv 4 \, (mod \; 14)$.

Trinn 3:

Vi avgjør om likningen har løsning. Vi finner da $d = SFF(a_2, n)$. Hvis $d \mid b_2$, har likningen løsninger i $d$ restklasser. I motsatt fall har likningen ikke løsning.

Eksempel 10.3:

Vi får $d = SFF(12, 14) = 2$.

$2 \mid 4$, så likningen har løsninger i 2 restklasser.

Trinn 4:

Hvis likningen er løsbar, dividerer vi alle ledd med $d$ hvis $d > 1$. For enkelhets skyld kaller vi heretter $\frac{\displaystyle n}{\displaystyle d}$ for $m$.

Vi har nå likningen $a_4x \equiv b_4 \, (mod \; m)$.

Eksempel 10.4:

Vi dividerer alle ledd med $d = 2$ og får $6x \equiv 2 \, (mod \; 7)$.

Trinn 5:

For å undersøke om likningen kan forenkles mer, finner vi $c = SFF(a_4, b_4)$. Hvis $c > 1$, dividerer vi $a_4$ og $b_4$ med $c$. Det er ikke nødvendig å gjøre noe med modulus, for vi vet at $SFF(a_4, m) = 1$, siden vi i trinn 4 dividerte bort alle felles faktorer.

Vi har nå likningen $a_5x \equiv b_5 \, (mod \; m)$.

Eksempel 10.5:

Vi får $c = SFF(6, 2) = 2$. Så vi dividerer $a_4 = 6$ og $b_4 = 2$ med $2$ og får $a_5 = 3$ og $b_5 = 1$, slik at likningen blir $3x \equiv 1 \, (mod \; 7)$.

Trinn 6:

Vi finner en multiplikativ invers til $a_5 \, (mod \; m)$ og multipliserer med denne på begge sider av kongruenstegnet.

Vi har nå likningen $x \equiv b_6 \, (mod \; m)$.

Eksempel 10.6

Vi går inn i raden med $a_5 = 3$ i tabellen "Modulo 7" og finner at inversen er $\overline{a_5} = 5$.

Vi multipliserer med $5$ på begge sider av kongruenstegnet og får $(3 \cdot 5)x \equiv 1 \cdot 5 \, (mod \; 7) \Rightarrow x \equiv 5 \, (mod \; 7)$.

Trinn 7:

Dersom ikke $0 \le b_6 < m$, erstatter vi $b_6$ med $b_6 – \lfloor \frac{\displaystyle b_6}{\displaystyle m} \rfloor \cdot m$.

Vi har nå likningen $x \equiv b_7 \, (mod \; m)$.

Eksempel 10.7

Vi har $0 < b_6 = 5< 7$, så det er ikke nødvendig med noen erstatning.

Trinn 8:

Vi har nå funnet en løsning, $t$, til likningen $x \equiv b_7 \, (mod \; m)$. Vi finner så de $d$ restklassene med løsninger til den opprinnelige likningen, $a_1x \equiv b_1 \, (mod \; n)$, ved å bruke formelen $x_k = t + k \cdot m$, der $0 \le k \le d – 1$.   $d$ fant vi i trinn 3.

Eksempel 10.8:

Vi har funnet at $t = 5$. Vi har $d = 2$, så restklassene med løsninger modulo $14$ blir $x_0 = 5 + 0 \cdot 7 = 5$ og $x_1 = 5 + 1 \cdot 7 = 12$.

Så løsningene er $x \equiv 5, 12 \, (mod \, 14)$.

Dette nettstedet har en app som løser kongruenslikninger ved hjelp av denne algoritmen.

Oppgave 7:

Løs kongruenslikningene under hvis de er løsbare:

  1. $270x – 10 \equiv -130 + 14x \, (mod \; 44)$
     
  2. $-108x – 100 \equiv 229 + 10x \, (mod \; 44)$

Se løsningsforslag

Vi har nå presentert en algoritme, en kokebokoppskrift, på å løse en kongruenslikning, såfremt den er løsbar. Fordelen med oppskriften er at den alltid virker. En ulempe er imidlertid at den av og til kan være tungvint fordi det finnes enkle grep vi kan gjøre for å løse likningen på en kjapp måte.

Eksempel 11:

Vi skal løse kongruenslikningen $11x \equiv 22 \, (mod \; 4)$.

Her er både $a = 11$ og $b = 22$ større enn $n = 5$, så løsningsalgoritmen sier at vi skal erstatte $a$ og $b$ med mindre, kongruente tall, noe som resulterer i likningen $3x \equiv 2 \, (mod \; 4)$, som vi så må arbeide videre med.

Imidlertid ser vi at vi kan dividere med $11$ på begge sider av kongruenstegnet. Siden $SFF(a, n) = SFF(11, 4) = 1$, trenger vi ikke endre modulus, og vi får løsningen direkte: $x \equiv 2 \, (mod \; 4)$.

Eksempel 12:

Vi skal løse kongruenslikningen $7x \equiv -6 \, (mod \; 8)$.

Her er $b = -6$ negativ, så løsningsalgoritmen sier at vi skal erstatte $b$ med et positivt, kongruent tall, noe som resulterer i likningen $7x \equiv 2 \, (mod \; 8)$, som vi så må arbeide videre med.

Vi ser imidlertid at $a = 7 \equiv -1 \, (mod \; 8)$, så vi går mot strømmen og erstatter $a = 7$ med $a = -1$ og får $-x \equiv -6 \, (mod \; 8)$. Så er det bare å multiplisere med $-1$ på begge sider, og vi får løsningen direkte: $x \equiv 6 \, (mod \; 8)$.

Oppgave 8:

Løs kongruenslikningen $60x \equiv -50 \, (mod \; 7)$ på en enkel måte.

Se løsningsforslag

Vi avslutter med en klassisk nøtt vi gjerne forsøker å løse ved prøving og feiling, men som kan løses ved hjelp av kongruensregning.

Eksempel 13:

Vi skal finne ut hvordan vi ved hjelp av ei bøtte som tar 5 liter og ei bøtte som tar 3 liter kan måle opp akkurat 1 liter, når bøttene ikke har målestreker.

Det vi lurer på er hvordan vi ved å fylle den store bøtta fra den lille kan stå igjen med en rest på akkurat 1 liter i den lille. Det kan uttrykkes som at vi vil finne en heltallig $x$ slik at $3x \equiv 1 \, (mod \; 5)$, der $3$ er volumet til den lille bøtta, $5$ er volumet til den store bøtta og $x$ er antall ganger vi fyller den lille bøtta.

Vi ser at $SFF(a, n) = SFF(3, 5) = 1$, så likningen har løsning i 1 restklasse.

Fra tabellen med multiplikative inverser modulo 5 ser vi at $2$ er en multiplikativ invers til $3$ modulo $5$, så vi multipliserer med $2$ på begge sider av kongruenstegnet og får $x \equiv 2 \, (mod \; 5)$.

I praksis betyr det at vi fyller den lille bøtta, heller over i den store, fyller den lille en gang til og heller over til den store er full. Da har vi fylt opp totalt 5 liter, og det er det en rest på 1 liter i den lille bøtta.

En annen løsning er $x = 2 + 1 \cdot 5 = 7$.  Vi kan altså også få 1 liter vann ved å helle over i den store 7 ganger. Vi må jo da tømme den store bøtta hver gang den er full, det kan vi tenke på som å erstatte $5$ med $0$, som er kongruent modulo $5$. Operasjonen vil forløpe i trinn som forklart under, tallene i parentes forteller hvor mye det er igjen i bøttene.

Vi heller over 3 liter. (0, 3).

Vi heller over 3 liter, med en pause mens vi tømmer den store bøtta. (0, 1).

Vi heller over 3 liter. (0, 4).

Vi heller over 3 liter, med en pause mens vi tømmer den store bøtta. (0, 2).

Vi heller over 3 liter og tømmer den store bøtta. (0, 0).

Vi har nå gjort en modulus, altså 5, overhellinger av 3 liter, og er tilbake ved utgangspunktet med to tomme bøtter. I løpet av to trinn til er vi derved framme ved samme løsning som før:

Vi heller over 3 liter. (0, 3).

Vi heller over til den store bøtta er full, og har da en rest på 1 liter i den lille bøtta.

Flere løsninger er $x = 2 + 2 \cdot 5 = 12$$x = 2 + 3 \cdot 5 = 17$, og så videre. også. Men særlig praktisk er det ikke, for vi er jo innom riktig løsning flere ganger underveis.

Oppgave 9:

Vi har to bøtter uten målestreker på henholdsvis 5 og 7 liter og skal måle opp akkurat 1 liter.

  1. Sett opp en kongruenslikning som uttrykker dette problemet.
     
  2. Vis at likningen har løsning, og finn den enkleste løsningen.
     
  3. Forklar hvordan løsningen kan omsettes i praksis

Se løsningsforslag

Kilder

  • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
  • Rinvold, A. R. (2009). Visuelle perspektiv.Tallteori.Caspar Forlag.
  • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
  • Gustavsen, T.S., Hinna, T.R.C., Borge, I.C., Andersen, P.S. (2014). QED 5-10, bind 2. Cappelen Damm A/S.
  • Wikipedia