Kongruenslikninger

Modellere med kongruenslikninger

Eksempel 1:

En jogger løper intervaller på 2 km i ei rundløype som er 5 km lang. Etter hvert intervall tar han en pause. Når han ved en pause er 4 km inn i løypa, hvor mange intervaller på 2 km kan han da ha løpt?

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

2x ≡ 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 ≡ 2 (mod 5).

Antall intervaller må altså være kongruente med 2 modulo 5, med andre ord på formen 2 + k · 5, der k er et helt tall. Joggeren kan ha løpt 2 + 0 · 5 = 2 intervaller, 2 + 1 · 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 joggeren ikke kan ha løpt et negativt antall runder. Men matematisk sett er også 2 + (−1) · 5 = −3 og 2 + (−2) · 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 · 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 løsningen skal være et helt tall. I en kongruenslikning derimot, må løsningene 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 tok pause 3 km inn i løypa, skjønner vi at han ikke kunne løpt et helt antall intervaller på 2 km. For intervallene ville alltid slutte 2 km inn, 4 km inn, og tilbake ved start. Så kongruenslikningen

2x ≡ 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 her bare kongruenslikninger. En lineær kongruenslikning er på formen axb (mod n), der a, b og n er hele tall, a ≠ 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. Hvor hyppig passerer banen deretter på hele klokkeslett?

Se løsningsforslag

Oppgave 2:

Foreslå en situasjon som kan modelleres med kongruenslikningen 4x ≡ 0 (mod 10).

Se løsningsforslag

Kongruenslikner og restklasser

I eksempel 1 hadde vi kongruenslikningen 2x ≡ 4 (mod 5), og fant ut at løsningene var på formen 2 + k · 5, der 5 var modulus. Markerer vi løsningene i en tabell med antall kolonner lik modulus, 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 ≡ 3 (mod 6) ikke hadde løsning. Vi ser nå på et tredje eksempel:

Eksempel 3:

Vi har kongruenslikningen 9x ≡ 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 antall kolonner lik modulus, 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 axb (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) | b. I eksempel 1 hadde vi SFF(2, 5) = 1 | 4 og i eksempel 3 SFF(9, 15) = 3 | 12. Men i eksempel 2 hadde vi SFF(2, 6) = 2 ∤ 3.

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

Vi har altså

$\fbox{$\begin{align} &ax \equiv b \, (mod \; n) \text{ har ingen løsning hvis } SFF(a,n) \nmid b \\
&ax \equiv b \, (mod \; n) \text{ har løsning i } SFF(a,n) \text{ restklasser hvis } SFF(a,n) \mid b \end{align}$}$

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. I eksempel 1 blir det 2, og i eksempel 3 blir det 3, 8 og 13.

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 ≡ 8 (mod 10)
         
      2. 3x ≡ 8 (mod 10)
         
      3. 4x ≡ 9 (mod 10)
         
      4. 84x ≡ 108 (mod 12)

Se løsningsforslag

Metoder for å løse lineære kongruenslikninger

Vi skal nå se hvordan vi 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 ≡ 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, tn eller t < 0 med $ s = t − \lfloor \frac{\displaystyle t}{\displaystyle n} \rfloor \cdot n$, der n er modulus. Vi vil da alltid få 0 ≤ s < n.

Eksempel 5:

Vi skal forenkle kongruenslikningen x ≡ 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 ≡ 3 (mod 7).

 

Vi skal forenkle kongruenslikningen x ≡ −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 ≡ 1 (mod 3).

 

Vi skal forenkle kongruenslikningen 5x ≡ 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 ≡ 3 (mod 4).

 

Vi skal forenkle kongruenslikningen −5x ≡ 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 ≡ 0 (mod 6).

Oppgave 4:

Forenkle kongruenslikningen x + 4 ≡ 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 axb (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 ≡ 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 ≡ 3 (mod 9).

Tidligere i artikkelen har vi sagt at, så fremt en kongruenslikning, axb (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{$\begin{align} &\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 < d \end{align}$}$

Eksempel 7:

I eksempel 6 har vi kommet fram til at en løsning til kongruenslikningen 4x ≡ 12 (mod 18) er x = 3.
Og vi har d = SFF(4, 18) = 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 ≡ 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 xt (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 ≡ 6 (mod 9). Det største tallet vi kan dividere med er SFF(4, 6) = 2.

Og vi får 2x ≡ 3 (mod 9). (Her er d = SFF(2, 9) = 1, så modulus 9 blir uendret)

Vi ser at vi i eksempel 8 ikke har klart å få x alene på venstre side, men står igjen med uttrykket 2x ≡ 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, a, som er slik at a · a ≡ 1 (mod n). Det vil si at hvis vi i en kongruenslikning på formen axb (mod n) multipliserer med a på begge sider, vil vi få (a · a)xb · a (mod n), noe som, siden (a · a) ≡ 1 (mod n), kan forenkles til xb · 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 vi nevnte tidligere på siden, 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 løsbar 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 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.

En liste over multiplikative inverser for modulo n for n mellom 2 og 13 finnes nederst i artikkelen om regneregler for kongruens.

Eksempel 9:

Vi skal få x til å stå alene på venstre side i kongruenslikningen 4x ≡ 7 (mod 9).

Siden SFF(4, 9) = 1, vet vi at 4 har en multiplikativ invers modulo 9. Fra lista nederst i artikkelen om regneregler for kongruens finner vi at en invers til a = 4 modulo 9 er a = 7.

Vi multipliserer med 7 på begge sider av kongruenstegnet og får (4 · 7)x ≡ 7 · 7 (mod 9) ⇒ x ≡ 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 ≡ 4 (mod 9).

Oppgave 6:

x til å stå alene på venstre side i kongruenslikningen 4x ≡ 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 framgangsmåte, for å løse kongruenslikninger, som alltid virker.

En kongruenslikning der leddene er ordnet, er på formen axb (mod n). Siden a og b kan endre seg når vi går gjennom de forskjellige trinnene, gir vi dem et subskript avhengig av hvilket trinn vi er i, for eksempel a1, b1 i trinn 1.

Vi illustrerer med et gjennomgående eksempel.

Eksempel 10:

Vi skal løse kongruenslikningen −5x + 6 ≡ 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 a1xb1 (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 ≡ 46 (mod 14).

Trinn 2:

Hvis ikke 0 ≤ a1 < n, erstatter vi a1 med $a_1 − \lfloor \frac{\displaystyle a_1}{\displaystyle n} \rfloor \cdot n$. Tilsvarende for b1.

Vi har nå likningen a2xb2 (mod n).

Eksempel 10.2:

Vi har a1 = −2 < 0, så vi erstatter −2 med $−2 − \lfloor {\large \frac{−2}{14}} \rfloor \cdot 14 = −2 − (−1) \cdot 14 = 12$.

Vi har b1 = 46 > 14, så vi erstatter 46 med $46 − \lfloor {\large \frac{46}{14}}\rfloor \cdot 14 = 46 − 3 \cdot 14 = 4$.

Resultatet blir 12x ≡ 4 (mod 14).

Trinn 3:

Vi avgjør om likningen har løsning. Vi finner da d = SFF(a2, n). Hvis d | b2, 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 | 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 a4xb4 (mod m).

Eksempel 10.4:

Vi dividerer alle ledd med d = 2 og får 6x ≡ 2 (mod 7).

Trinn 5:

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

Vi har nå likningen a5xb5 (mod m).

Eksempel 10.5:

Vi får c = SFF(6, 2) = 2. Så vi dividerer a4 = 6 og b4 = 2 med 2 og får a5 = 3 og b5 = 1, slik at likningen blir 3x ≡ 1 (mod 7).

Trinn 6:

Vi finner en multiplikativ invers til a5 (mod m) og multipliserer med denne på begge sider av kongruenstegnet.

Vi har nå likningen xb6 (mod m).

Eksempel 10.6

I tabellen nederst i artikkelen om regneregler for kongruens finner vi at en multiplikativ invers til a5 = 3 modulo 7 er a5 = 5.

Vi multipliserer med 5 på begge sider av kongruenstegnet og får (3 · 5)x ≡ 1 · 5 (mod 7) ⇒ x ≡ 5 (mod 7).

Trinn 7:

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

Vi har nå likningen xb7 (mod m).

Eksempel 10.7

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

Trinn 8:

Vi har nå funnet en løsning, t, til likningen xb7 (mod m). Vi finner så de d restklassene med løsninger til den opprinnelige likningen, a1xb1 (mod n), ved å bruke formelen xk = t + k · m, der k er et helt tall slik at 0 ≤ k < d. 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 x0 = 5 + 0 · 7 = 5 og x1 = 5 + 1 · 7 = 12.

Så løsningene er x ≡ 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 ≡ −130 + 14x (mod 44)
         
      2. −108x − 100 ≡ 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 ≡ 22 (mod 4).

Her er både a = 11 og b = 22 større enn n = 4, så løsningsalgoritmen sier at vi skal erstatte a og b med mindre, kongruente tall, noe som resulterer i likningen 3x ≡ 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 ≡ 2 (mod 4).

Eksempel 12:

Vi skal løse kongruenslikningen 7x ≡ −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 ≡ 2 (mod 8), som vi så må arbeide videre med.

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

Oppgave 8:

Løs kongruenslikningen 60x ≡ −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 ≡ 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 ≡ 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 · 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 · 5 = 12, x = 2 + 3 · 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.